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

# Convert NFA (q0,q1,q2) to DFA

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2074 Asoj
- Video: [Theory of Computation: NFA to DFA conversion Example](https://www.youtube.com/watch?v=n_5wgW10ZYU) — Anita R
- 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-01-q0q2
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

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

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

## Answer

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

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

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

## Check yourself

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

1. How is a DFA state's transition computed?
   A. Intersection of the members' transitions
   B. Only the first member's
   C. Sum of the member indices
   D. Union of NFA transitions of its members
   Answer: D. δ({q0,q1},0) = {q0,q1} ∪ {q0}. (Key point: Subset construction)

2. Which DFA states are final?
   A. Those containing q2
   B. Only {q2}
   C. Those containing q0
   D. Those containing q1
   Answer: A. q2 is the NFA's final state, so {q2} and {q1,q2} are final. (Key point: Final states)

3. Why is ∅ needed?
   A. To add a final state
   B. q2 has no 0-transition
   C. q0 has no transitions
   D. To make the DFA nondeterministic
   Answer: B. A DFA needs a total δ. (Key point: Dead state)

4. What is {q0,q1} on 1?
   A. {q0,q1}
   B. {q2}
   C. {q1,q2}
   D. {q0}
   Answer: C. {q2} ∪ {q1}. (Key point: Computation)

## Related in Theory of Computation

- [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×
- [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×
- [Difference between DFA and NFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-nfa-difference) — Theory of Computation, chapter 2, asked 2×