NFA to DFA Conversiation

DFA by definition forms a subset of NFA. A language accepted by NFA can be accepted by DFA.

NFA can be converted to DFA and vice versa. Therefore, Both DFA & NFA are equivalent in powers. As every DFA is NFA, thus we give more emphasis on conversion of NFA to DFA.  There are several ways to perform but the final answer should not vary.

If L is a set accepted by NFA M, then L can be accepted by a DFA M’ where M’= (Q’, ∑, ∆', q0’, F’) where Q’ = 2Q(If there are 3 states in NFA, then we can have 8 states in DFA).

Conversion from NFA to DFA.

  • Draw the initial state.       
  •  From initial state draw the reachable states on getting inputs.
  • Consider the reachable states and fill new row accordingly.

EXAMPLE 1  Convert NFA to DFA for all strings ending with “a”.

L={aa,aba,aaa,abbaa,…….}

Q={A,B}

∑={a,b}

F= [B ]

In this NFA, A is the initial state and B is the final state. In state A, after receiving input a, as it is Non-deterministic; it has options to choose, either it can go to state A or it can go to state B.

 

STATE TRANSITION TABLE for above NFA which contains Rows as states and columns as inputs.

 

   a

      b

 

    A

 

 {A,B}

 

    {A}

 

B(final state)

 

  {}               

 

      {}

 

Using the state transition table of NFA, further draw state transition table of DFA.

How to draw

  • Draw the initial state
  • From initial state further, draw the reachable states on input.
  • From every state which is reachable, consider it as state and fill the rows accordingly

STATE TRANSITION TABLE OF DFA.

 

    

      a

      

       

        b

 

      A

 

   [AB]

 

     [A]

 

      AB

 

   [AB]

 

      [A]

STEP-1 State A by getting the input a going to newly formed state AB (as in DFA it can go only to a particular state) and in input b, it is going to state A.

STEP-2  Include that newly formed state AB, after getting input a, it is going to state AB again(using NFA state diagram, union of both states A and B → {A, B}U{} we get [AB] ); after getting input as b, it is going state A(using NFA state diagram, union of both states A and B → {A}U{} we get [A] );

 

NOTE:- For denoting single states we are using [] brackets whereas {} are used to represent sets.

STATE DIAGRAM FOR DFA

∑={a,b}

Q'={A,AB}

F'={AB} 

 

Even though 22 = 4 states are possible but they will not be useful and unreachable, therefore, only 2 states are used.

 

EXAMPLE-2: Conversion of NFA TO DFA for the language “ all strings starting with a”.

∑={a,b}

L1 ={starts with a….a,aa,aab,abbb,abaab…..}

Q={A,B}

 

STATE TRANSITION TABLE for above NFA which contains Rows as states and columns as inputs.

 

 

a

 

b

 

A

 

B

 

Ø

 

B

 

       B

 

B

 

 

 

After receiving input a, state A goes to state B  whereas, in input b, State A is going to Ø which means no move.

 

 after receiving input a and b, state B is going to state B respectively.

 

For constructing DFA, draw a state transition table where Ø becomes the dead state in DFA, hence one more state gets increased as the concept of dead state only appears in DFA.

DEAD STATE-   Once a machine enters the dead state, there is no way to reach the final state. A machine may have several dead states but at most only one dead state is needed by a machine(DFA).

 

STATE TRANSITION TABLE for  DFA which contains Rows as states and columns as inputs.

 

 

        a                        

 

         B

 

      A

 

       B                        

 

        D(Dead State)

 

      B(Final state)

      

       B

      

        B

 

      D(Dead State)

 

       D(Dead State)            

 

      D(Dead State)                   

 

STATE TRANSITION DIAGRAM for DFA.

∑={a,b}

Q={A,AB}

F={AB} 

 

Even though 22 = 4 states are possible but they will not be useful and unreachable, therefore, only 3 states are used.

We can clearly see, in this problem No. of states in DFA is greater than No. of states in NFA due to dead state.

If NFA is able to solve a problem in "n" states, the maximum no. of states required by DFA to solve the problem will be 2n . Therefore, we can conclude that no. of states in DFA is greater than or equal to the no. of states in NFA.

 

 

 

Contributor's Info

Created: Edited:
0Comment