Skip to main content

Convert NFA (q0,q1,q2) to DFA

Short answer

DFA: A={q0}, B={q0,q1}, C={q2}, D={q1,q2}, dead E. Start A. A-0→B, A-1→C; B-0→B, B-1→D; C-0→E, C-1→B; D-0→A, D-1→B; E loops. Finals C, D. Example: '01' goes A→B→C accepted.

Convert the following NDFA to its DFA. [Figure: NDFA over {0,1} with start state q0 and final state q2. Transitions: q0 –0→ {q0, q1}; q0 –1→ q2; q1 –0→ q0; q1 –1→ q1; q2 –1→ {q0, q1}; q2 has no transition on 0.]

NFA transitions (start q0, final q2):

State01
→ q0{q0, q1}{q2}
q1{q0}{q1}
*q2∅{q0, q1}

Method. Subset construction, starting from {q0}. A DFA state is final if it contains q2.

  • {q0}: on 0 → {q0, q1}; on 1 → {q2}.
  • {q0, q1}: on 0 → δ(q0,0) ∪ δ(q1,0) = {q0, q1} ∪ {q0} = {q0, q1}; on 1 → {q2} ∪ {q1} = {q1, q2}.
  • {q2}: on 0 → ∅; on 1 → {q0, q1}.
  • {q1, q2}: on 0 → {q0} ∪ ∅ = {q0}; on 1 → {q1} ∪ {q0, q1} = {q0, q1}.
  • ∅: on 0, 1 → ∅.

DFA transition table

State01
→ {q0}{q0,q1}{q2}
{q0,q1}{q0,q1}{q1,q2}
*{q2}∅{q0,q1}
*{q1,q2}{q0}{q0,q1}
∅∅∅

Rename: A = {q0}, B = {q0,q1}, C = {q2}, D = {q1,q2}, E = ∅. Final states: C and D.

 A --0--> B        B --0--> B (loop)
 A --1--> (C)      B --1--> (D)
 (C) --0--> E      (C) --1--> B
 (D) --0--> A      (D) --1--> B
 E --0,1--> E (dead state)

 Start: A.   Finals: C, D.

Edge list: A–0→B, A–1→C, B–0→B, B–1→D, C–0→E, C–1→B, D–0→A, D–1→B. E (dead) loops on 0, 1.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →