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

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

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Kartik
- Video: [Conversion of NFA to DFA](https://www.youtube.com/watch?v=--CSVsFIDng) — Neso Academy
- 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-five-states
- 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 {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.]

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

## Answer

**NFA transitions** (start q0, final q4):

| State | 0 | 1 |
|---|---|---|
| → 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
| State | 0 | 1 |
|---|---|---|
| → {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.

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

## Check yourself

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

1. In the subset construction, what is the DFA start state?
   A. The set of all NFA states
   B. {q0}, the set containing the NFA start state
   C. The set of final states
   D. ∅
   Answer: B. The DFA starts at the singleton set containing the NFA start state. (Key point: Subset construction start)

2. What is the DFA move from {q1,q2,q3} on input 1?
   A. {q0}
   B. {q4}
   C. {q0,q1,q4}
   D. ∅
   Answer: C. Take the union: q1 on 1 gives q0, q2 gives q1, q3 gives q4, so {q0,q1,q4}. (Key point: Computing a transition)

3. Which DFA states are final?
   A. Those that contain the NFA start state
   B. Those that contain q4
   C. All non-empty subsets
   D. Only singleton sets
   Answer: B. A subset is final if it contains at least one NFA final state, here q4. (Key point: Final DFA states)

4. Why does the DFA include the state ∅?
   A. It is the start state
   B. It is a final state
   C. It is needed to make the transition function total, as a dead state
   D. It represents ε
   Answer: C. Moves with no NFA transition lead to the empty set, which traps non-accepted input. (Key point: Dead state)

## Close variants set in other exams

- [Convert ε-NFA (q0..q4) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-epsilon-q4) — 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