A finite automaton is a simple machine that is used to recognize patterns within input taken from some alphabet. An alphabet is a finite set of symbols that is used to represent the input of a machine. These symbols can be letters, digits, characters, signs, punctuation and more.
∑ is the symbol that is used to represent a specific alphabet. For example, we could say ∑ = {a, b}, this would make our alphabet the lowercase letters “a” and “b”.
The job of a finite automaton is to either reject or accept an input depending on whether or not a specific pattern was recognized within the input. Finite automata are made up of states which change depending on the inputs received and the specific rules for each state.
Finite automata have no memory except for knowing which state the machine is currently in. Now that we are familiar with finite machines, let’s take a look at deterministic finite automata.
DFA
Deterministic Finite Automata is a type of deterministic algorithm (an algorithm that is purely determined by its inputs, where no randomness is involved in the model) based on a state that changes with inputs.
DFA can only change states if an input is given, no null values will work with DFA. There can be many DFA’s meant to detect a single pattern, however the DFA with the least number of states is usually the preferred DFA.
Why Is It Called Deterministic Finite Automata?
In DFA one can always determine which state the machine will be in next based on the input it is given, this is why it’s called deterministic. It is called finite because the number of states is finite. And automaton is essentially another word for machine.
The 5-Tuples of DFA
DFA can be represented using the 5 tuples, a finite set of mathematical objects, definition (Q, ∑ , δ, q0, F) where:
Q is the finite set of all states
∑ is the finite set of accepted symbols, called the alphabet
δ is the transition function where 𝛿: Q * Σ → Q
q0 is the start state, and
F is the set of all accept states
For example, we could have a DFA that is defined as:
Q: {q0, q1}
∑: {a, b}
δ:
q0: q0, starting state.
F: {aa, aba, aab, bba, bb, bbab, bab, abb, ababa…}
This DFA can be drawn in a state diagram as follows:
In this state diagram the start state is the circle with an empty arrow pointing into it, which is q0. Our final (or accept) state is represented with 2 circles around it.
And each transition that is described in the transition function is shown with the arrows labeled with an input and pointing to where the input moves the state to.
With the diagram above, work out what would happen if the input to the DFA was the string “bbaba”… Will the string be accepted or rejected by this DFA.
I hope that was easy enough for you and you saw that this DFA will reject the string “bbaba”, in fact it will reject all inputs that do not end in “b”.
Now that you have a good understanding of DFA’s, let’s work through a challenge problem.
Challenge Problem
Design a DFA whose alphabet is {0, 1} and accepts all inputs ending in 00 or 11. Also define the DFA with the 5 tuple definition.
Try and tackle this problem on your own before we work it out together.
To start this problem we should break it into smaller more manageable parts. Let’s first create a DFA that accepts inputs ending in 00, with at least length 4.
Before we move on, let’s test the DFA with a few inputs to be sure it’s accepting strings ending with 00 and rejecting all others.
101011 = q0, rejected
110001010 = q1, rejected
000000 = q2, accepted
00100100 = q2, accepted
Now that we know we have a working DFA that accepts all strings ending in 00 we can move on to our next step, accepting 11 as well. We aren’t going to create another DFA that only accepts strings ending in 11 because it would be the same as the one above just with the inputs switched.
Again, I encourage you to try and work this out on your own before looking at how I solved the problem.
As you can see, the DFA has not changed too much, the original one we created to accept inputs ending in 00 is still visibly there with a few changes.
What we had to change was how the machine handled receiving 1 as an input since we now also accept strings ending in 11. This was done by adding two more states, q3 and q4, which work the same as q1 and q2.
One thing you might notice is when q1 now receives 1 as an input, instead of going back to the start state it goes to q3. This is because we want to accept strings ending in 11 and if q1 receives an input of 1, then we only need one more input of 1 to be an acceptable string.
In q3 if you receive a 1 you get sent to the final state, q4, and the string is accepted. However if you were to send the q1 to q0 on an input of 1, then the next input of 1 will only get you to q3 which is not a final state.
Now to define the DFA using the 5 tuples:
Q: {q0, q1, q2, q3, q4}
Σ: {0, 1}
𝛿:
q0: q0, start state.
F: {q2, q4}
I hope you were able to solve that problem on your own and that DFA’s are starting to make sense to you. Before I finish this article I would like to briefly talk about some of the real world applications of DFA’s.
Real World Applications of DFA
DFA’s are useful because they are simple and efficient in recognizing regular languages (a language, or set of strings chosen from an alphabet, that is accepted by some finite state machine).
For this reason they are used in many areas of computer science such as compilers, lexical analysis, pattern matching and many more. DFA’s are also very useful in applications which require switching from valid to invalid states.
This can be things like password recognition, text analysis and many more. Some everyday applications you are likely familiar with are vending machines, traffic lights, and parking meters.
I hope you learned a lot in this article and will be back for the many more to come. Thanks for reading.