---
title: "Difference between DFA and NFA"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-nfa-difference"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-nfa-difference
site: BCT Engineering
---

# Difference between DFA and NFA

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2071 Chaitra; 2074 Asoj (asked 2 times)
- Video: [Lec-19: DFA vs NFA in TOC in Hindi with examples | Must Watch](https://www.youtube.com/watch?v=4BDz876IJBc) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-nfa-difference
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Differentiate between DFA and NFA (NDFA).

## Short answer

A DFA has exactly one transition per symbol from each state and no ε-moves, while an NFA may have multiple or zero transitions and can include ε-moves. NFAs are often more compact and easier to design, but DFAs are simpler to implement. Both recognize the same class of regular languages, convertible via the subset construction.

## Answer

Both DFA and NFA accept exactly the regular languages, but they differ in how they move.

| Point | DFA | NFA (NDFA) |
|---|---|---|
| Transition function | δ : Q × Σ → Q | δ : Q × (Σ ∪ {ε}) → 2^Q |
| Moves on a symbol | exactly one next state | zero, one or many next states |
| ε-moves | not allowed | allowed (ε-NFA) |
| Computation | a single path for each input | a tree of paths; accept if some path ends in a final state |
| Dead state | needed to make δ total | missing transitions are allowed (the path simply dies) |
| Acceptance | δ*(q₀, w) ∈ F | δ*(q₀, w) ∩ F ≠ ∅ |
| Design | harder, more states | easier, usually fewer states |
| Implementation | simple and fast, one table lookup per symbol | needs backtracking or tracking a set of states |
| Number of states | n | an NFA with n states may need up to 2ⁿ states as a DFA |

**Formal tuple:** both are 5-tuples (Q, Σ, δ, q₀, F); only the type of δ differs.

**Equivalence.** Every NFA can be converted to a DFA by the subset construction, so the two models accept the same class of languages (regular languages).

## Check yourself

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

1. How does an NFA's δ differ from a DFA's?
   A. NFA: Q × (Σ ∪ {ε}) → 2^Q
   B. NFA: Q → Σ
   C. NFA: Q × Σ → Q
   D. NFA has no transition function
   Answer: A. NFA moves go to a set of states and may use ε. (Key point: Transition function)

2. When does an NFA accept w?
   A. The first path ends in a final state
   B. Every path ends in a final state
   C. Some path ends in a final state
   D. The path with fewest states ends in a final state
   Answer: C. Acceptance requires δ*(q0, w) ∩ F ≠ ∅. (Key point: Acceptance)

3. How do DFA and NFA compare in language power?
   A. NFAs accept only finite languages
   B. They accept exactly the same class: regular languages
   C. NFAs accept more languages
   D. DFAs accept more languages
   Answer: B. The subset construction converts any NFA to a DFA. (Key point: Power)

4. What is the worst-case state cost of converting an n-state NFA to a DFA?
   A. Up to n+1 states
   B. Up to 2^n states
   C. Always n states
   D. Up to n^2 states
   Answer: B. Each DFA state is a subset of NFA states. (Key point: State blowup)

## 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
- [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×
- [NDFA importance; two consecutive a or b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Andfa-importance-consecutive) — Theory of Computation, chapter 2

## Related in other subjects

- [Differentiate DFA and NFA](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adfa-vs-nfa-difference) — Discrete Structure, chapter 2, asked 2×
- [NFA and DFA from grammar σ→bσ|aC](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-bsigma-ac) — Discrete Structure, chapter 2, asked 4×
- [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2×
- [NFA and DFA from grammar with A, B rules](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-with-a-b-productions) — Discrete Structure, chapter 2, asked 2×