# Automata Conversion from NFA to DFA

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.