NDFA to DFA Conversion

NDFA to DFA Conversion :

To understand the conversion from NDFA to DFA, considers the following numerical.

Ex. 1  construct the DFA equivalent to where transition function is                                                                                                            given by :

                                      (NDFA table )

Solution:  DFA corresponding to above NDFA is given in the below table-

                                         (DFA table)

          

Here [q0] = initial state

[q0] [q0,q1] = final states ,because these are the only states containing q0.

[Trick : First of all take the first row of the NDFA table and put in the DFA table. then check the states in "0" and "1" column in the first row. if state is already used in "state" column. then no problem otherwise take the new state that appeared in the "0" or "1" column as a new row. and check the entry in NDFA column. same process is repeated until there is no new state appeared in the "0" and "1" column. ]

Ex. 2  Find a DFA corresponding to following NDFA -

          

transition function is given by

Solution: DFA corresponding to above NDFA is :

here [q0] is the initial state. [q2] [q1,q2] are final states,because these are the only states containing q0.

Ex. 3  Find a DFA corresponding to following NDFA -

     transition function is given by

        

Solution: DFA corresponding to above NDFA is :

here [q0] is the initial state. [q0,q1,q3] [q0,q1,q2,q3] are final states, because these are the only states containing q3.

Exercises

1.   Find a DFA corresponding to following NDFA, where transition function is given by:

2.   Find a DFA corresponding to following NDFA, where transition function is given by: