CLASS 10 : NDFA TO DFA CONVERSION

Let we understand the conversion of NDFA TO DFA.

We have a graph given below :

Note :
           Consider each element of power set of Q Non Deterministic Automata (NDFA) as a single state of deterministic automata (DFA).

Things to be remember :

{ q0 q1}→ curly braces are used for saperate elements.
[ q0 , q1]→ This is an single elements and formed by one or more state so here we use square bracket.

Formal Definition :

Q  = {q0, q1, q2 }
       i.e 2^Q = {[φ] , [q0] , [q1] , [q2] , [q0,q1] , [q0,q2] , [q1,q2] , [q0,q1,q2]}
Σ   = {0,1}
q0 = q0
F   = {q2}

Construct a graph on the basis of above transition table :

In the above graph we will discard / reject some states because they are unreachable. such as [φ] , [q1] ,  [q0,q2] , [q0,q1,q2] we get new graph.

Now write formal definition according to above graph and transition table.

Formal Definition :

Q = {[φ] , [q0] , [q1] , [q2] , [q0,q1] , [q0,q2] , [q1,q2] , [q0,q1,q2] }

Σ = {0,1}

q0 = q0

F = {[q2] , [q0,q2] , [q1,q2] , [q0,q1,q2]}   because each state contain final state i.e q2

Now do some modification in above diagram explain below :

Step 1. Discard those state which are unusable such as [φ] , [q1] ,  [q0,q2] , [q0,q1,q2] show in the above diagram shown by (X) sign.
[φ] is rejected state. 
We discard these states because we can not reach in these states in any condition. i.e unreachable state.There is no input symbol.
In this step we get following graph:

Step 2. Then we can change the level of state. But direction and input symbol can not be change.
We get following graph:

Q = ( A, B, C, D )
E is just like dummy edge.

Note: Edge is represented as capital letters. and Input is represented as small letters.