Overview of Finite Automata
A finite automaton, also known as a finite state machine, is an imaginary machine which takes input, reads that input step-by-step, and either accepts or rejects the input.
There are two types of finite automata, DFAs (Deterministic Finite Automata) and NFAs (Non-deterministic Finite Automata).
Basic Information:
A finite automaton is a combination of five different parts.
- Q = The finite set of states of the automaton.
- Σ = The alphabet accepted by the automaton.
- δ = The transition function.
- q_{0} = The starting state.
- F = The set of accept states.
The Alphabet:
The alphabet of an automaton is a set of characters that the automaton recognizes.
An alphabet can be {0, 1}, which allows the automaton to work with ones and zeroes, or {a, b, c} which allows it to work with 'a's 'b's and 'c's. The characters could even be entire words such as {one, two, three}.
There is one special character that can be used. It is the null or empty character, ε.
The Input String:
A finite automaton can process any input created using the alphabet.
For example, let's say our alphabet is {0, 1}. We would be able to process the strings "0", "1", "00", "01", "10", "11", "100", etc...
If our alphabet was {a, b, c, d, e}, then we could process "a", "b", "c", "d", "e", "abcde", "adec", etc...
Say we alter the previous alphabet to accept the "empty" character {a, b, c, d, e, ε}. We would then be able to process "", "a", "b", "c", "e", etc... Notice how the first string is actually nothing.
The length of the string doesn't matter, the order of characters doesn't matter, but what does matter is that the string contains only characters of the alphabet.
The Language:
The language of a finite automaton is the set of all strings that, after being processed, are accepted by the automaton.
Anything that is rejected by the automaton, or cannot be processed by it, is not in the language of the automaton.
Deterministic Finite Automata:
All DFA diagrams will look similar to the image below. They begin at a starting state (red), transition to other states as input is read, and eventually end up on an accept (green) or reject state. The DFA below will accept both the strings "01" and "11".
When drawing a DFA, you should remember the following:
- The starting state is clearly marked or shown by an arrow coming from nowhere towards it, see the arrow on the far left in the above image for an example of this.
- It is assumed that all transitions (the arrows) that are not shown lead to a reject state. This means that you do not need to draw your reject states.
- All accept states should be clearly shown with a double-circle, see the green state in the image above for an example of this.
How A Transition Works:
Say, for example, a user inputs the string "0101" to the finite automaton in the image above.
- The transition between the starting/first state (red) and the second state (white) allows us to read either a zero or a one. In this case, the character at the front of the input string "0101" is a zero, so we are allowed to transition.
- We still need to read the remaining characters "101".
- T he transition between the second state (white) and the accept/third state (green) allows us to read a one. In this case, the character at the front of the input that we haven't finished reading "101" is a one, so we are allowed to transition.
- We still need to read the remaining characters "01".
- There are no transitions from the accept/third state (green), so we can only transition to a reject state. Therefore the input is rejected.
As a secondary example, a user inputs the string "100" to the finite automaton.
- The transition between the starting/first state (red) and the second state (white) allows us to read either a zero or a one. In this case, the character at the front of the input string "100" is a one, so we are allowed to transition.
- We still need to read the remaining characters "00".
- The transition between the second state (white) and the accept/third state (green) allows us to read a one. In this case, the character at the front of the input that we haven't finished reading "101" is a zero, so we cannot transition.
- There are no more transitions that can be done, so our input cannot be fully processed. Therefore the input is rejected.
As a final example, a user inputs the string "01" to the finite automaton.
- The transition between the starting/first state (red) and the second state (white) allows us to read either a zero or a one. In this case, the character at the front of the input string "01" is a zero, so we are allowed to transition.
- We still need to read the remaining character "1".
- The transition between the second state (white) and the accept/third state (green) allows us to read a one. In this case, the character at the front of the input that we haven't finished reading "1" is a one, so we are allowed to transition.
- We are finished processing the input and we have finished on an accept state, therefore the input is accepted.
Non-deterministic Finite Automata:
The first thing to note about NFAs is that all DFAs are NFAs, but not all NFAs are DFAs.
All NFA diagrams will look similar to the image of an DFA from the previous section. The key differences between NFAs and DFAs are as follows:
- Multiple transitions of the same type can be used to transition from one state to multiple others. Notice how there are two possible transitions on the input "1" from the starting state (red) to both of the possible second states (white).
- Episilon "ε" transitions which allow for a transition without reading/using any of the input to be processed. Notice how if the NFA below is given the input "1" it can reach the lower second state (white) where it can then consume no input and instantly move to the accept state (green).
- If there is any possible set of transitions that result in an input being fully read and ending on an accept state, then the input is accepted.