Again, this post is meant specifically for the undergraduate students (the first timers into the automata theory) – a very brief introduction of FSA: Finite State Automaton (Automata when plural). This post is in four parts: this part covers an elementary introductions to FSA and DFA (Deterministic Finite Automaton), Part II encompasses some common examples illustrating design-strategies for constructing DFA, Part III provides an introduction to NFA (Nondeterministic Finite Automaton) and its equivalence with DFA, and Part IV introduces Pumping Lemma and its usage in the context of FSA.
Finite State Automaton:
A Finite State Automaton (FSA) is a computational model that can be seen as a central control which has a set of states associated with it. The word ‘finite‘ in the name depicts that the set of states is finite. The control is given an input – a sequence of symbols from a set called alphabet – and is expected to answer whether the input-sequence is ‘VALID‘ or ‘INVALID‘ after reading the input.
The computational model works as follows: It reads the input starting from the first, until the last – one symbol at a time. At each instant, the control is in one of its possible states; the particular state in which the control is just when it starts reading the input, is called an initial state. With each symbol of the input read, the control makes a transition (switch) from its current state to another state; the new state does not necessarily have to be a different one i.e. it may switch back to the same state. There is a subset of states, called final states, representing a ‘valid‘ input; if the control is in one of the final states when it finishes reading the input then it denotes that the input is valid, otherwise not (i.e. invalid).
Transition Diagram –
An FSA can be represented graphically by a transition diagram that makes it simpler to visualise and emulate its working. The associated transition diagram of a FSA can be drawn as follows:
- A sate is represented by a circle.
- An initial state by a wedge ‘>’ attached to it.
- A final state by a double circle.
- A transition from one state to another on reading a symbol (say a) by an arc (edge) from the current state to the new one with the symbol as the label of the edge.
Motivation –
A transition of an FSA depends only on the current state and the symbol of the input-sequence being read. In other words, since a symbol read makes an FSA change its state, the sequence of changes of states corresponds to some property of the input it has read until now. Abstractly, each state of an FSA can be seen to memorise some information about the input it has seen so far. Since, the number of states of an FSA is finite, it is said to have a finite ‘memory‘.
Although its finite memory makes the model quite restrictive, yet there are many systems that be modelled using an FSA: A lexer (lexical analyser in a compiler) is one such system. Unix/Linux grep command is another utility that makes use of the FSA. Find facility of a text-editor – finding a set of strings (sequence of letters) in a longer string (text) — is usually implemented using FSA.
Apart from the direct applications, studying FSA makes it easier to understand and appreciate the more powerful computational models such as Push Down Automaton (PDA) and Turing Machine.
Classification –
An FSA can be classified as being deterministic or nondeterministic.
Deterministic Finite Automaton (DFA): Behaviour is deterministic as we can go to only one state (defined by the transition) from the current state on reading a specific symbol (i.e. there is exactly one edge from the current state labelled with a particular symbol). We will be covering DFA in the next section.
Nondeteministic Finite Automaton(NFA): Behaviour is nondeterministic in the sense that on reading a symbol, transitions to many states are defined (i.e. more than one edges are defined from the current state labelled with the same symbol); control can be in any of the defined states after this transition. In addition empty-transitions (ε-transitions) are also possible which correspond to changing state without reading a symbol. We shall have a detailed look on NFA in the next post.
DFA:
Mathematical description –
Mathematically a DFA can be represented as a 5-tuple ℳ = (Q, Σ, s, F, δ) where
Q is finite set of states,
Σ is an alphabet (set of symbols of the input),
s ∈ Q is the initial state,
F ⊆ Q is the set of the final states,
δ , the transition function, is a function from Q × Σ to Q
A simple example
Designing an automaton is to define each element of the tuple. Consider a simple example – An automaton that accepts a string “aab”. Let us assume that the alphabet is {a, b}. It implies that the valid input sequence is exactly “a” followed by “b” which is followed by another “a”, after which the input should finish. Anything else is an invalid input. Note that as soon as some symbol making the input invalid is encountered/read, symbols in the remaining input do not matter as the whole input will be invalid anyway.
For this example,we have to remember that we have seen “a” or “ab”, or “aba”. Also, we should have at least two states – a final state (representing that any given input is valid) to which we should reach only after reading an “aba”; a trap-state (representing an invalid input) to which we should go to as soon we read any symbol that makes the input invalid and should stay there until the input ends. Once we are in the final state, input should end. What if it does not? We should go to the trap-state, on reading any symbol after we have reached the final state.
When we start reading the input, we are in an initial state. We are expecting an “a”. If we read an “a”, we are one step closer to the input being valid => we go to state that remembers that we have read the first “a”. What if we get a “b” at the beginning? It makes the input invalid, we should go to the trap-state.
Now , after reading the first “a”, we are expecting a “b”. If we get a “b”, we are one more step close to the final state; ab we should remember reading an “ab”. If we get an “a” as the second symbol (i.e the input starts from “aa”), it is an invalid input.
The third expected symbol is an “a”, getting which we should reach the final state. If we get a “b” instead, it makes the valid input.
After reaching the final state, any additional symbol will lead to the trap-state state and control will be trapped there until the end of the input. As the trap-state is not final, it will indicate that the input is invalid. On the other hand, if the input finishes as soon as we reach the state representing “aba”, it will indicate a valid input as this state is final.
Mathematically, the DFA can be expressed as follows:
ℳ = (Q, Σ, s, F, δ) where
Q is {0, a, ab, aba, trap-state} (naming initial state to be 0),
Σ is {“a”, “b”},
s is 0,
F is {aba}
δ is given as the following transition table:
| input symbol → state ↓ |
“a” | “b” |
|---|---|---|
| 0 | a | trap-state |
| a | trap-state | ab |
| ab | aba | trap-state |
| aba | trap-state | trap-state |
| trap-state | trap-state | trap-state |
Working of the FSA for some input sequences are shown in the following (current symbol being considered is shown in red; current state in green; edge taken and the next state in red):
- A valid sequence
- An invalid seqeunce: does not end after “aba”
- An invalid sequence: not equal to “aba”
Epilogue:
Please pardon the verbosity, oversimplification, and baby-steps. This particular part of the post is more relevant to undergraduate students. Move onto the next parts .🙂
Cheers!