**Algorithm **

Let M_{2} = {Q_{2}, Σ, δ_{2}, F_{2}, q’_{0}} be NFA that recognizes the language L and M = {Q, Σ, δ, F, q_{0}} be the corresponding DFA. To obtain the DFA we may proceed as follows:

- Initially Q = Φ.
- Put q’
_{0}into Q. q’_{0}is the initial state of the DFA M. - Then for each q in Q do the following: add this new state, add δ(q, a) =U
_{pϵq}δ_{2}(p, a) to δ. The state added to Q is a subset of states of NFA. - Repeat step 3 till new states are there to add in Q, the process terminates when there is no new state after step 3.

**Note:**The states added to Q with the final state of M_{2} in the set of states are final states of the DFA.

**Example:** Convert the following NFA into DFA

Solution

_{0}to Q.

δ(q

_{0}, 0) = {q

_{0}, q

_{1}} = A*

δ(q

_{0}, 1) = {q

_{1}}*

Add states A and q

_{1}to Q.

δ(A, 0) = δ({q_{0}, q_{1}}, 0) = δ(q_{0}, 0) U δ(q_{1}, 0)

= {q_{0}, q_{1}} U {q_{2}} = {q_{0}, q_{1}, q_{2}} = B*

δ(A, 1) = δ({q_{0}, q_{1}}, 1) = δ(q_{0}, 0) U δ(q_{1}, 1)

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

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

δ(q_{1}, 1) = q_{2}

Add B* C* and q_{2} to Q

δ(B, 0) = δ(q_{0}, 0) U δ(q_{1}, 0) U δ(q_{2}, 0)

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

δ(B, 1) = δ(q_{0}, 1) U δ(q_{1}, 0) U δ(_{2}, 1)

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

δ(C, 0) = δ(q_{1}, 0) U δ(q_{2}, 1) = { q_{2}} U {Φ}

= q_{2}

δ(C, 1) = δ(q_{1}, 1) U δ(q_{2}, 1) = {q_{2}} U {q_{2}}

= q_{2}

δ(q_{2}, 0) = Φ

δ(q_{2}, 1) = q_{2}

No new states were generated so we stop the procedure. The star after the state represents the final state in Q. The DFA generated by the above procedure:

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.