# Theory of Computation – Conversion of Nondeterministic Finite Automata to Deterministic Finite Automata

For every nondeterministic finite automaton there exists an equivalent deterministic finite automaton. It means that for every nondeterministic finite automaton accepting a language L there exist a deterministic finite automaton that accepts the same language L. The DFA equivalent of an NFA simulates the moves of the NFA in parallel. To do that the states of the DFA will be a combination of one or more states of NFA. Hence every state of the DFA will be a subset of set of states of the NFA.

Algorithm

Let M2 = {Q2, Σ, δ2, F2, q’0} be NFA that recognizes the language L and M = {Q, Σ, δ, F, q0} be the corresponding DFA. To obtain the DFA we may proceed as follows:

1. Initially Q = Φ.
2. Put q’0 into Q. q’0 is the initial state of the DFA M.
3. Then for each q in Q do the following: add this new state, add δ(q, a) =Upϵq δ2(p, a) to δ. The state added to Q is a subset of states of NFA.
4. 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 M2 in the set of states are final states of the DFA.

Example: Convert the following NFA into DFA

Solution

Add initial state q0 to Q.
δ(q0, 0) = {q0, q1} = A*
δ(q0, 1) = {q1}*
Add states A and q1 to Q.

δ(A, 0) = δ({q0, q1}, 0) = δ(q0, 0) U δ(q1, 0)
= {q0, q1} U {q2} = {q0, q1, q2} = B*
δ(A, 1) = δ({q0, q1}, 1) = δ(q0, 0) U δ(q1, 1)
= {q1, q2} = C*
δ(q1, 0) = q2
δ(q1, 1) = q2
Add B* C* and q2 to Q

δ(B, 0) = δ(q0, 0) U δ(q1, 0) U δ(q2, 0)
= {q0, q1, q2} = B*
δ(B, 1) = δ(q0, 1) U δ(q1, 0) U δ(2, 1)
= {q1, q2} = C*
δ(C, 0) = δ(q1, 0) U δ(q2, 1) = { q2} U {Φ}
= q2
δ(C, 1) = δ(q1, 1) U δ(q2, 1) = {q2} U {q2}
= q2
δ(q2, 0) = Φ
δ(q2, 1) = q2

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

If you find any mistake above, kindly email to [email protected]