The Deterministic Finite Automata

What is DFA?

Does DFA stand for Dumb Faced Aunty?

😂Nope, not at all. DFA has nothing to do with any aunty. In fact, it is a very sophisticated machine.

DFA in fact is the acronym for — Deterministic Finite Automata.

What is Deterministic Finite Automata?

Firstly, automata is a mathematical model or abstract model which is used to determine if a string is accepted by a language or not.

The DFA is an automata which has finite states and accepts or rejects a given string by running through a number of states.

Oof! That’s too much of bookish language.

To make things simpler, lets take an example.

Consider a machine that accepts strings over the alphabets a and b which contain at least one a.

This machine can be diagrammatically represented as:

Here, the state q0 is the state we are starting from and qf is the final state of the machine i.e. the state where we understand if the string is accepted or not.

Lets say we have a string ‘ba’.

b’ being the first alphabet goes into the system first.

As we can see from the above diagram, when b enters the system i.e. the initial state q0, it is accepted by q0 and stays there. Now when we give the symbol a to the machine, as we can see that when q0 accepts a, it goes to qf which is the final state.(The double circles indicate final state).

With a being accepted by the machine and since the string is over, we can conclude that the string is accepted by the DFA.

Now lets consider the string “bbb”.

The first b is accepted by the string q0.

Then comes the second b. We are at q0 currently and the second b is again accepted by q0, thanks to the self-loop that we have shown.

So, by the end of the string we stay on the state q0 and do not reach the final state. Hence the string “bbb” is not accepted by the machine. Also, the condition we had laid was that the string should contain minimum one “a”.

So, obviously, the string “bbb” should not be accepted.

This was a very easy example where one could easily predict if the string would be accepted or not without the DFA. But in some cases it is really difficult for a person to determine that.

Formally, the DFA is defined using 5 tuples:

(Q , Σ , 𝛿 , q0 , F )

where:

Q : Set of finite states (for eg: {q0,q1,q2,……,qf})

Σ : Set of symbols (for eg: a,b....1,0…..)

𝛿 : Transition Function (function applied/ condition applied onto the string)

q0 : Initial/start state

F : Set of final states (here, qf but there can be multiple final states)

For every state, each input symbol has to have one transition

Let’s solve some examples now:

  • Example 1:

Design a DFA over the input alphabets {a,b} which accepts all strings that end with a

— Consider the strings {a,aa,ba,aba,bba………}

All these end with a ,so all of them should be accepted by the DFA.

From the example above, we can infer that there can be any number of alphabets before a.

Considering that, we can design the dfa as:

As you can see, according to the given question we need a machine to accept strings ending with a. Since our condition involves only one symbol, we have only one necessary transition and hence we take two states. Here, the string can start with any symbol but should end in a. Hence, any occurrence of b is directed towards q0 but a’s are directed towards the final state qf.

Test it out with other strings ending with a.

  • Example 2:

Design a DFA over the input alphabets {a,b} which accepts all strings that start with a and end with b

If you have understood the concept, why not give your brain a little exercise?

Try this one on your own and then scroll down to check your answer.

.

.

.

I hope you could solve it. If you couldn’t no worries, you could checkout my solution:

Consider strings such as:{ab ,aabb ,aab ,abb ,abab,…… }

These strings should be accepted by the DFA. Hence, the DFA can be designed as:

D is the dead state that accepts all the strings not suitable for our machine.

Here, if string starts with b, it will get into dead state and will never reach the final state.

Did you get it right? Do let me know in the comments.

Another one,

  • Example 3:

Design a DFA over the input alphabets {a,b} which accepts all strings that do not start with a or d not end with b.

Try this on your own!

.

.

.

Hope you got this one!

Here's a little trick to solve this one. Take the complement of the problem statement. The complement would be:

……………..which accepts all strings that start with a and end with b.

Design a DFA for the complement. That would be:

Now, take the complement of this DFA. i.e. make the final states non final and the non final states final. This would give us:

This is the solution to our problem statement.

Consider the examples: {ε, a ,b ,ba , bbaa, aaa, aba,…..}

ε is a null/empty string

These are a few strings that do not start with a or do not end in b.

These are accepted by the above DFA.

On the other hand if you try the strings like {ab ,aabb ,aab ,abb ,abab,…. }, they won’t be accepted.

  • Example 4:

Design a DFA over the input alphabets {0,1} where 2nd symbol should 0 and 4th should be 1.

.

.

.

Got the answer?…..Check it with the one I got:

Consider input strings : {0011, 0001, 1001 ,1011,…}

Wasn’t it easy?

Now let’s take a look at the last but very very interesting example.

  • Example 5:

Design a DFA over the input alphabets {0,1} which should accept all numbers divisible by 3.

This is a bit tricky question, but let’s solve it step by step.

Firstly, if a number is divided by 3, the possible remainders are: 0,1 and 2.

Hence, our DFA will have 3 states.

Now binary equivalents of these remainders are:

0 -> 0

1->01

2->10

These combinations, when occur, should lead to the respective state.

Also, we want to target strings divisible by 3, so the expected remainder is 0 and hence, the final state is q0.

So, until now we have this.

Now, the next step is to consider other strings like:

3->011

4 ->100

5-> 101

6-> 110

7 ->111

From these, 3 and 6 give a remainder of 0;

4 and 7 give 1 ; 5 gives 2.

If we handle all these conditions and complete our DFA this is what we get:

This is the complete solution of our problem.

For example, consider 15 (1111), which is divisible by 3. Hence we should get 0 as output. Let’s verify:

When we give 1111 to this DFA, the path followed is: q0->q1->q0->q1->q0 which brings us back to q0 which is our final state. Hence, 15 is accepted as expected.

Similarly, for 21(10101), the path is: q0->q1->q2->q2->q1->q0.

Hence,21 is also accepted.

Consider 14(1110), which is not divisible by 3 and leaves a remainder of 2 i.e. should end up at q2 .

Lets verify.

The path obtained is: q0->q1->q0->q1->q2.

Hence verified.

I hope things are much clearer now. I have tried my best to explain the concept and tried to take as many examples as possible.

Let me know if it helped you and also you can post your questions in the comments below.

Have a nice day!

Technology enthusiast, coder, designer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store