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.


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


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]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.