---
title: "Differentiate DFA and NFA"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:dfa-vs-nfa-difference"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/dfa-vs-nfa-difference
site: BCT Engineering
---

# Differentiate DFA and NFA

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2069 Bhadra, 2 marks; 2070 Bhadra, 2 marks (asked 2 times)
- Video: [Differences between DFA and NFA || Deterministic Finite Automata || Non Deterministic || Types of](https://www.youtube.com/watch?v=BCgIAQelwo8) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/dfa-vs-nfa-difference
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Differentiate between Deterministic Finite State Automata and Non-Deterministic Finite State Automata.

## Short answer

In a DFA, each state has exactly one transition per input symbol. In an NFA, a state may have zero, one, or multiple transitions, including ε-moves. A DFA can need up to 2^n states to simulate an n-state NFA, but both accept the same regular languages.

## Answer

| Point | DFA | NFA |
|---|---|---|
| Next state | Exactly one for each (state, symbol) | Zero, one or many for each (state, symbol) |
| Transition function | δ : Q × Σ → Q | δ : Q × Σ → 2^Q (set of states) |
| ε-moves | Not allowed | Allowed in the ε-NFA variant |
| Dead state | Needed to make δ total | Missing transitions simply mean rejection |
| Execution | Follows a single path | Many paths possible; accepts if any path ends in a final state |
| Size | The DFA equivalent to an n-state NFA may need up to 2ⁿ states | Usually fewer states, easier to design |
| Power | Accepts regular languages | Accepts the same regular languages |

## Check yourself

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

1. A DFA has how many next states per (state, symbol)?
   A. Exactly one
   B. Zero or more
   C. Always two
   D. At most one but may be none
   Answer: A. δ : Q × Σ → Q is total. (Key point: Next state)

2. An NFA accepts a string when?
   A. Some path ends in a final state
   B. All paths end in final states
   C. The first path ends in a final state
   D. No path is blocked
   Answer: A. One accepting path is enough. (Key point: Acceptance)

3. Which statement is true about power?
   A. DFAs and NFAs accept the same class of languages
   B. NFAs accept more languages
   C. DFAs accept more languages
   D. They accept disjoint classes
   Answer: A. Both accept exactly the regular languages. (Key point: Power)

## Related in Discrete Structure

- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×
- [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×
- [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×
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2

## Related in other subjects

- [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×
- [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×
- [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