The NFA to DFA conversion is based on subset construction. If a non-deterministic finite state machine consists of three states.

Q = (**q**_{0}, **q**_{1}, **q**_{2},)

The machine could form a power set on Q, which in given by 2^{Q} .

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 {q_{0}} is the first subset.

0 – successor of q_{0} is q_{2} δ(q_{0}, 0 ) ⇒ q_{2}.

1 – successor of q_{0} is Ф δ(q_{0}, 0 ) ⇒ Ф.

**Step – 2:**

A new subset {q_{2}} is generated. Successor of the subset {q_{2}} are generated.

0 – successor of {q_{2}} are {q_{0}, q_{1}} .

1 – successor of {q_{2}} are {q_{0}}.

**Step – 3:**

A new subset {q_{0}, q_{1}} is generated. Successor of the subset {q_{0}, q_{1}} are generated.

0 – successor of {q_{0}, q_{1}} = δ ({q_{0}, q_{1}}, 0)

= δ (q_{0}, 0) **∪** (q_{1}, 0)

= {q_{2}}**∪** Ф

= {q_{2}}

1 – successor of {q_{0}, q_{1}} = δ ({q_{0}, q_{1}}, 1)

= δ (q_{0}, 1) **∪** (q_{1}, 1)

= Ф **∪** {q_{0}, q_{2}}

= {q_{0}, q_{2}}

**Step – 4:**

A new subset {q_{0}, q_{2}} is generated successors of the subset {q_{0}, q_{2}} are generated.

0 – successor of {q_{0}, q_{2}} = δ ({q_{0}, q_{2}}, 0)

= δ (q_{0}, 0) **∪** (q_{2}, 0)

= {q_{2}} **∪** {q_{2}, q_{1}}

= {q_{0}, q_{1}, q_{2}}

1 – successor of {q_{0}, q_{2}} = δ ({q_{0}, q_{2}}, 1)

= δ (q_{0}, 1) **∪** (q_{2}, 1)

= Ф **∪** {q_{0}}

= {q_{0}}

**Step – 5:**

A new subset {q_{0}, q_{1}, q_{2}} is generated successors of the subset {q_{0}, q_{1}, q_{2}} are generated.

0 – successor of {q_{0}, q_{1}, q_{2}} = δ ({q_{0}, q_{1}, q_{2}}, 0)

= δ ({q_{0}, q_{1}}, 0) **∪** (q_{2}, 0)

= {q_{2}} **∪** {q_{0}, q_{1}}

= {q_{0}, q_{1}, q_{2}}

1 – successor of {q_{0}, q_{1}, q_{2}} = δ ({q_{0}, q_{1}, q_{2}}, 1)

= δ ({q_{0}, q_{1}}, 1) **∪** (q_{2}, 1)

= {q_{0} ,q_{1} } **∪** {q_{0}}

= {q_{0}, q_{2}}

**Step – 6:**

q_{2} is the final state in NFA of the diagram Every subset containing q_{2} 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