CLASS 13 : CONSTRUCTION OF FINITE AUTOMATA (FA)

In this post we are going to learn how to construct finite automata (FA). CONSTRUCTION OF FINITE AUTOMATA (FA) means design a machine which can accept a variety of combination of input string i.e 0/1.

Input String such as :10,100,1100,10000,1010110 etc.

Learn More About Finite Automata (FA)

Let we understand by the help of examples:

1. Construct a DFA which accept string of 0's and 1's end with substring 00.


Solution: 

Here string end with 00 means those string whose last two bits are 00 such as 100,1000, 1100, 101100, 110100 etc.

Now For CONSTRUCTION OF FINITE AUTOMATA (FA) we design a machine that can accept the above strings such as 100,1000, 1100, 110100, 100100, etc.

Let first we take Input strings in different cases. 

CASE I: Input Sting =00

 CASE II: Input Sting =000

               

CASE III: Input Sting =1000    OR   1100    OR    111000

                 

CASE IV: Input Sting =110100 

                     

CASE V: Input Sting =100100  

                   

Now this transition graph is final which satisfy all input string ended with 00.

Formal Definition:

Q = {q0, q1, q2}

Σ = {0, 1}

q0 = q0

F = {q2}

δ ( Transition table) =

Now we get final transition table on the basis of above graph. For CONSTRUCTION OF FINITE AUTOMATA (FA) we consider different cases and in CASE V we get final graph that satisfy all type of input strings end with 00.