DFA vs NFA: Formal Differences and NFA-to-DFA Conversion

Verified Sources

Sep 12, 2026

In automata theory, Deterministic Finite Automaton (DFA) and Non-Deterministic Finite Automaton (NFA) are two equivalent models for recognizing Regular Languages.

A key contrast is the Transition Function:

DFA transitions are deterministic: from a given state and input symbol, there is exactly one next state.
NFA transitions are non-deterministic: from a given state and input symbol, there may be multiple next states (and possibly via ε-transitions).

Visual intuition

Note: Both DFA and NFA recognize exactly the same class of languages (the regular languages), despite their different operational semantics.

Wikipedia — Deterministic finite automaton (DFA) and equivalence with NFA via regular languages. https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Explains DFA formal model and that DFAs recognize regular languages, same as NFAs. ↩

Core formal definitions (transition behavior)

Let $Q$ be the set of states and $\Sigma$ the input alphabet.

DFA has a transition function: $\delta: Q \times \Sigma \to Q$ so each pair $(q,a)$ yields a single next state.
NFA has a transition function: $\delta: Q \times \Sigma \to 2^{Q}$ so each pair $(q,a)$ yields a set of next states. If the NFA also allows ε-transitions, transitions may additionally be: $\delta: Q \times \{\epsilon\} \to 2^Q$

Because an NFA’s current “configuration” is effectively a set of possible states, converting an NFA to a DFA typically builds DFA states that correspond to these subsets.

Wikipedia — Subset construction (NFA to DFA / power set construction). https://en.wikipedia.org/wiki/Powerset_construction - Describes constructing a DFA whose states are subsets of NFA states, and the transition/acceptance logic. ↩

DFA vs NFA: Key Operational Differences (Conceptual Scale)

Higher is more characteristic of the model’s behavior.

Side-by-side comparison (what you can and must remember)

Aspect	DFA	NFA
Determinism	Exactly one next state for each $(q,a)$	Potentially many next states for each $(q,a)$
Current “status” while processing input	A single current state	A set of possible current states
Computation model	Single path simulation	Branching computation; acceptance if any branch accepts
Acceptance	Reach an accepting state	Reach an accepting state along at least one nondet branch
Typical conversion to other model	NFA $\to$ DFA via subset construction	DFA is a special case of NFA

These are consistent with the formal language equivalence between DFA and NFA models.

Wikipedia — Deterministic finite automaton (DFA) and equivalence with NFA via regular languages. https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Explains DFA formal model and that DFAs recognize regular languages, same as NFAs. ↩

Pro Tip: Acceptance for NFA

For an NFA, an input string is accepted if there exists at least one nondeterministic sequence of choices that ends in an accepting state.

Warning: DFA construction can blow up in size

Subset construction may produce up to $2^{|Q|}$ DFA states because each DFA state is a subset of NFA states. This affects practical efficiency.

Subset Construction (NFA → DFA) Lifecycle

Start state

Use the ε-closure of NFA start state(s) as the DFA start subset."

Transitions

For each DFA subset S and symbol a, compute move(S,a) then take ε-closure."

Accepting states

Mark any DFA subset containing an NFA accepting state as accepting."

Repeat

Process newly discovered subsets until no new subsets appear."

Procedure: Convert an NFA (with or without ε) to an equivalent DFA (Subset Construction)

1
Step 1
Let the NFA be $(Q, \Sigma, \delta, q_0, F)$ . If ε-transitions exist, treat them explicitly. (DFA will use the same alphabet $\Sigma$ .)
2
Step 2
For each state $q$ , compute $\text{ε-closure}(q)$ = set of states reachable from $q$ using only ε-transitions.
3
Step 3
Let the DFA start state be $S_0 = \text{ε-closure}(\{q_0\})$ (or just $\{q_0\}$ if no ε).
4
Step 4
For a DFA state represented by subset $S \subseteq Q$ and symbol $a \in \Sigma$ , compute:

$\text{move}(S,a) = \bigcup_{q \in S}\delta(q,a)$

If ε exists, take closure: $T = \text{ε-closure}(\text{move}(S,a))$ Then set $\delta_{DFA}(S,a) = T$ .
5
Step 5
A DFA subset $S$ is accepting iff $S \cap F eq \emptyset$ .
6
Step 6
Repeat for each discovered subset $S$ and each input symbol $a$ until no new subsets are generated.
7
Step 7
The constructed DFA recognizes the same language as the original NFA.

Footnotes

Wikipedia — Deterministic finite automaton (DFA) and equivalence with NFA via regular languages. https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Explains DFA formal model and that DFAs recognize regular languages, same as NFAs. ↩

Worked example (NFA → DFA) without ε-transitions

Consider an NFA $N$ with:

$Q = \{q_0, q_1, q_2\}$
$\Sigma = \{a,b\}$
Start state: $q_0$
Accepting states: $F = \{q_2\}$
Transitions:
- $\delta(q_0,a)=\{q_0,q_1\}$
- $\delta(q_0,b)=\{q_1\}$
- $\delta(q_1,a)=\{q_2\}$
- $\delta(q_1,b)=\emptyset$
- $\delta(q_2,a)=\emptyset$
- $\delta(q_2,b)=\{q_2\}$

We convert to a DFA whose states are subsets of $Q$ .

Step A: Start subset

DFA start state: $S_0=\{q_0\}$

Step B: Compute transitions

We compute $\text{move}(S,a)$ by unioning NFA transitions from each state in $S$ .

From $S_0=\{q_0\}$ :

on $a$ $a$ : $\text{move}(\{q_0\},a)=\delta(q_0,a)=\{q_0,q_1\}$ $move ({q_{0}}, a) = δ (q_{0}, a) = {q_{0}, q_{1}}$
- so $\delta_{DFA}(S_0,a)=\{q_0,q_1\}$
on $b$ $b$ : $\text{move}(\{q_0\},b)=\delta(q_0,b)=\{q_1\}$ $move ({q_{0}}, b) = δ (q_{0}, b) = {q_{1}}$
- so $\delta_{DFA}(S_0,b)=\{q_1\}$

From $S_1=\{q_0,q_1\}$ :

on $a$ $a$ :
- $\delta(q_0,a)=\{q_0,q_1\}$
- $\delta(q_1,a)=\{q_2\}$
- union $\Rightarrow \{q_0,q_1,q_2\}$
on $b$ $b$ :
- $\delta(q_0,b)=\{q_1\}$
- $\delta(q_1,b)=\emptyset$
- union $\Rightarrow \{q_1\}$

From $S_2=\{q_1\}$ :

on $a$ : $\delta(q_1,a)=\{q_2\}$
on $b$ : $\delta(q_1,b)=\emptyset$

From $S_3=\{q_0,q_1,q_2\}$ :

on $a$ $a$ :
- $\delta(q_0,a)=\{q_0,q_1\}$
- $\delta(q_1,a)=\{q_2\}$
- $\delta(q_2,a)=\emptyset$
- union $\Rightarrow \{q_0,q_1,q_2\}$
on $b$ $b$ :
- $\delta(q_0,b)=\{q_1\}$
- $\delta(q_1,b)=\emptyset$
- $\delta(q_2,b)=\{q_2\}$
- union $\Rightarrow \{q_1,q_2\}$

From $S_4=\{q_1,q_2\}$ :

on $a$ $a$ :
- $\delta(q_1,a)=\{q_2\}$
- $\delta(q_2,a)=\emptyset$
- union $\Rightarrow \{q_2\}$
on $b$ $b$ :
- $\delta(q_1,b)=\emptyset$
- $\delta(q_2,b)=\{q_2\}$
- union $\Rightarrow \{q_2\}$

From $S_5=\{q_2\}$ :

on $a$ : $\delta(q_2,a)=\emptyset$
on $b$ : $\delta(q_2,b)=\{q_2\}$

Include the empty subset $S_\emptyset=\emptyset$ if it appears:

on any symbol, $\text{move}(\emptyset,a)=\emptyset$

Step C: Accepting subsets

Accepting condition: subset contains $q_2$ . So accepting DFA states are:

$\{q_0,q_1,q_2\}$
$\{q_1,q_2\}$
$\{q_2\}$

Summary transition table

DFA subset (state)	on $a$	on $b$	Accepting?
$\{q_0\}$	$\{q_0,q_1\}$	$\{q_1\}$	No
$\{q_0,q_1\}$	$\{q_0,q_1,q_2\}$	$\{q_1\}$	No
$\{q_1\}$	$\{q_2\}$	$\emptyset$	No
$\{q_0,q_1,q_2\}$	$\{q_0,q_1,q_2\}$	$\{q_1,q_2\}$	Yes
$\{q_1,q_2\}$	$\{q_2\}$	$\{q_2\}$	Yes
$\{q_2\}$	$\emptyset$	$\{q_2\}$	Yes
$\emptyset$	$\emptyset$	$\emptyset$	No

This illustrates how an NFA’s branching behavior is simulated deterministically by tracking subsets of states.

Wikipedia — Subset construction (NFA to DFA / power set construction). https://en.wikipedia.org/wiki/Powerset_construction - Describes constructing a DFA whose states are subsets of NFA states, and the transition/acceptance logic. ↩

FAQ: Common Pitfalls

Knowledge Check

Question 1 of 4

Q1Single choice

In a DFA, the transition function satisfies:

$\delta: Q\times\Sigma \to Q$

$\delta: Q\times\Sigma \to 2^Q$

$\delta: Q\to\Sigma$

$\delta: 2^Q\times\Sigma \to 2^Q$

Explore Related Topics

Pushdown Automata (PDA): Short Note + Core Formalism

Alphabet, Language, Grammar, and Derivation: Definitions and Relationships in Formal Language Theory

DFA to Regular Expression via State Elimination (State Elimination Technique)

Browse all research articles

DFA vs NFA: Formal Differences and NFA-to-DFA Conversion

Visual intuition

Footnotes

Core formal definitions (transition behavior)

Footnotes

DFA vs NFA: Key Operational Differences (Conceptual Scale)

Side-by-side comparison (what you can and must remember)

Footnotes

Pro Tip: Acceptance for NFA

Warning: DFA construction can blow up in size

Subset Construction (NFA → DFA) Lifecycle

Start state

Transitions

Accepting states

Repeat

Procedure: Convert an NFA (with or without ε) to an equivalent DFA (Subset Construction)

Footnotes

Worked example (NFA → DFA) without ε-transitions

Step A: Start subset

Step B: Compute transitions

Step C: Accepting subsets

Summary transition table

Footnotes

FAQ: Common Pitfalls

Knowledge Check

Explore Related Topics