Skip to main content

Convert ε-NFA (q0..q4) to DFA

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

Method. Subset construction with ε-closures. DFA start state = ε-closure(q0).

ε-closures: ε-closure(q0) = {q0, q2}; ε-closure(q1) = {q1, q4}; every other state is its own closure.

Transitions of the NFA (a, b), with closure applied after each move:

  • q0: a → q1; q1: a → q2; q2: b → q3; q3: a → {q3, q4}, b → q1; q4: b → q1.

Construction

  • A = {q0, q2} (start)
    • on a: q0 → q1, q2 has none → {q1}; closure {q1, q4} = B
    • on b: q2 → q3 → {q3} = C
  • B = {q1, q4}
    • on a: q1 → q2 → {q2} = D
    • on b: q4 → q1; closure {q1, q4} = B
  • C = {q3}
    • on a: {q3, q4} = E
    • on b: q3 → q1; closure {q1, q4} = B
  • D = {q2}
    • on a: ∅ (dead)
    • on b: {q3} = C
  • E = {q3, q4}
    • on a: q3 → {q3, q4}; q4 has none → E
    • on b: q3 → q1, q4 → q1; closure {q1, q4} = B

Final states of the DFA are those that contain q4: B and E.

DFA transition table

Stateab
→ A = {q0,q2}BC
*B = {q1,q4}DB
C = {q3}EB
D = {q2}∅C
*E = {q3,q4}EB
∅ (dead)∅∅
 A = {q0,q2}  B = {q1,q4}  C = {q3}
 D = {q2}     E = {q3,q4}

          a              a              a
 ──► (A) ─────► ((B)) ─────► (D) ─────► ∅ (dead)
      │          ↻ b          │
    b │                       │ b
      ▼                       │
     (C) ◄────────────────────┘
      │ └──── b ────► ((B))
    a │
      ▼
    ((E)) ↻ a        E ──b──► ((B))

Simplified edge list: A–a→B, A–b→C, B–a→D, B–b→B, C–a→E, C–b→B, D–a→∅, D–b→C, E–a→E, E–b→B. The dead state ∅ may be omitted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →