---
title: "Convert ε-NFA (q0..q4) to DFA"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:nfa-to-dfa-epsilon-q4"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/nfa-to-dfa-epsilon-q4
site: BCT Engineering
---

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

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2071 Chaitra
- Video: [How to Convert NFA to DFA: Dealing with Epsilon Transitions](https://www.youtube.com/watch?v=qfVTXwuxEOY) — Mohammad Tanvir Irfan
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/nfa-to-dfa-epsilon-q4
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

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.]

## Answer

**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
| State | a | b |
|---|---|---|
| → A = {q0,q2} | B | C |
| *B = {q1,q4} | D | B |
| C = {q3} | E | B |
| D = {q2} | ∅ | C |
| *E = {q3,q4} | E | B |
| ∅ (dead) | ∅ | ∅ |

```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the DFA start state?
   A. {q4}
   B. The ε-closure of q0, {q0, q2}
   C. {q0, q1}
   D. {q0}
   Answer: B. Subset construction starts from the ε-closure of the NFA start. (Key point: Start state)

2. From {q0,q2} on a, what is the DFA state?
   A. {q1, q4}, the closure of {q1}
   B. {q3}
   C. {q2}
   D. {q1}
   Answer: A. q0 –a→ q1 and ε-closure(q1) = {q1, q4}. (Key point: Closure after move)

3. Which DFA states are final?
   A. Those containing q4: B and E
   B. Every state
   C. Only {q4}
   D. Those containing q0
   Answer: A. A subset is final if it contains an NFA final state. (Key point: Final states)

4. What happens from D = {q2} on a?
   A. It goes to {q3}
   B. It stays at {q2}
   C. It goes to {q1,q4}
   D. It goes to ∅ (dead), as q2 has no a-transition
   Answer: D. q2 has only a b-move. (Key point: Dead state)

## Close variants set in other exams

- [Convert NFA (q0..q4, 0/1) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-five-states) — Theory of Computation, chapter 2, asked 2×

## Related in Theory of Computation

- [Convert NFA (q0,q1,q2) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-01-q0q2) — Theory of Computation, chapter 2