The Deterministic Finite Automata

What is DFA?

Does DFA stand for Dog Food Association?

😂Nope, not at all. DFA has nothing to do with any dog or association. 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 that has finite states and accepts or rejects a given string by running through several states.

Oof! That’s too much of bookish language.

To make things simpler, let's 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.

Let's say we have a string ‘ba’.

‘b’ is the first alphabet that 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 the 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 let's 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 a minimum of 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 ends 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 check out 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 the string starts with b, it will get into a 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 compliment. 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 the 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 give 2.

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

This is the complete solution to 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.

Let's 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!