Skip to main content

Convert NFA (q0..q4, 0/1) to DFA

Short answer

Subset construction yields DFA states: A={q0} (start), B={q1,q2,q3}, C={q0,q1,q4} (final), D=∅ (dead). Transitions: A-0->B, A-1->D; B-0->D, B-1->C; C-0->B, C-1->A; D loops on 0,1.

Convert the following NFA to a DFA. [Figure: NFA over {0,1} with start state q0 and final state q4. Transitions: q0 –0→ {q1, q2, q3}; q1 –1→ q0; q2 –1→ q1; q3 –1→ q4.]

NFA transitions (start q0, final q4):

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

Subset construction, starting from {q0}:

  • {q0}: on 0 → {q1, q2, q3}; on 1 → ∅.
  • {q1, q2, q3}: on 0 → ∅; on 1 → {q0} ∪ {q1} ∪ {q4} = {q0, q1, q4}.
  • {q0, q1, q4}: on 0 → {q1, q2, q3} (from q0; q1 and q4 have none); on 1 → {q0} (from q1) = {q0}.
  • ∅ → ∅ on 0 and 1.

No other subsets are reachable. A DFA state is final if it contains q4.

DFA transition table

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

Rename A = {q0}, B = {q1,q2,q3}, C = {q0,q1,q4}, D = ∅ (dead). Final state: C.

          0             1
 ──►[A] ─────► [B] ─────► ((C))
   ▲                         │
   └──────────── 1 ──────────┘
   C --0--> B   (back to B)
   A --1--> D,  B --0--> D,  D loops on 0,1

Edges: A–0→B, B–1→C, C–0→B, C–1→A, plus A–1→D, B–0→D, D–0,1→D.

Check. The NFA accepts 01 (q0 –0→ q3 –1→ q4). In the DFA: A –0→ B –1→ C, final. 011: A, B, C, A, not accepted (the NFA cannot accept 011 either, since q4 has no moves).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →