The NFA to DFA conversion is based on subset construction. If a non-deterministic finite state machine consists of three states.
Q = (q0, q1, q2,)
The machine could form a power set on Q, which in given by 2Q .
The procedure for finding whether a given string is accepted by the NFA, involves:
- Tracing the various paths followed by the machine for the given string.
- Finding the set of states reached from the starting state by applying the symbols of the string.
- If the set of states obtained in step (2), contains a final state, the given string is accepted by the NFA.
The above procedure can be applied to any string by constructing a successor table.

Algorithm for contraction of successor table for the NFA of diagram is being explained, steps:
Step – 1:
Starting state {q0} is the first subset.
0 – successor of q0 is q2 δ(q0, 0 ) ⇒ q2.
1 – successor of q0 is Ф δ(q0, 0 ) ⇒ Ф.



Step – 2:
A new subset {q2} is generated. Successor of the subset {q2} are generated.
0 – successor of {q2} are {q0, q1} .
1 – successor of {q2} are {q0}.



Step – 3:
A new subset {q0, q1} is generated. Successor of the subset {q0, q1} are generated.
0 – successor of {q0, q1} = δ ({q0, q1}, 0)
= δ (q0, 0) ∪ (q1, 0)
= {q2}∪ Ф
= {q2}
1 – successor of {q0, q1} = δ ({q0, q1}, 1)
= δ (q0, 1) ∪ (q1, 1)
= Ф ∪ {q0, q2}
= {q0, q2}



Step – 4:
A new subset {q0, q2} is generated successors of the subset {q0, q2} are generated.
0 – successor of {q0, q2} = δ ({q0, q2}, 0)
= δ (q0, 0) ∪ (q2, 0)
= {q2} ∪ {q2, q1}
= {q0, q1, q2}
1 – successor of {q0, q2} = δ ({q0, q2}, 1)
= δ (q0, 1) ∪ (q2, 1)
= Ф ∪ {q0}
= {q0}



Step – 5:
A new subset {q0, q1, q2} is generated successors of the subset {q0, q1, q2} are generated.
0 – successor of {q0, q1, q2} = δ ({q0, q1, q2}, 0)
= δ ({q0, q1}, 0) ∪ (q2, 0)
= {q2} ∪ {q0, q1}
= {q0, q1, q2}
1 – successor of {q0, q1, q2} = δ ({q0, q1, q2}, 1)
= δ ({q0, q1}, 1) ∪ (q2, 1)
= {q0 ,q1 } ∪ {q0}
= {q0, q2}



Step – 6:
q2 is the final state in NFA of the diagram Every subset containing q2 should be taken as a final state.



Recommended:
- Introduction to Finite Automata
- Deterministic Finite Automata (DFA)
- Number of 1’s is a multiple of 3 on {0,1} using DFA
- Number of 1’s is not multiple of 3 on {0,1} using DFA
- DFA for Number of 1’s is even/odd and number of 0’s is even/odd
- DFA for number of 0’s divisible by five and 1’s divisible by 3
- DFA for All string of length at most five
- DFA for All strings ending with abb
- DFA for strings in which leftmost symbol differ from rightmost
- Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
- Design DFA which accept a binary number divisible by 3
- Non-Deterministic finite Automata
- Design NFA that accepts string ending with aab
- Design NFA to accept string containing the substring 0101
- Differentiate between NFA and DFA
- Design NFA that start with 01 and end with 10