NFA, Epsilon-NFA and Subset Construction: short notes (Theory of Computation)

Introduction

A nondeterministic finite automaton (NFA) may have zero, one or many next states for a given state and symbol. It accepts a string if some sequence of choices leads to an accepting state. Allowing $\varepsilon$ -transitions (moves without reading input) gives an $\varepsilon$ -NFA. Despite the extra freedom, NFAs and $\varepsilon$ -NFAs recognize exactly the same languages as DFAs: the regular languages.

The constructive proof is the subset construction (powerset construction): each DFA state is a set of NFA states, recording every place the NFA could be. The working skills are (a) drawing a small NFA, (b) building the subset DFA, and (c) knowing that the DFA may need up to $2^n$ states for an $n$ -state NFA.

Prerequisites

Deterministic Finite Automata: DFA tuple, acceptance, transition diagrams.

Core concepts

NFA without $\varepsilon$

An NFA is $N = (Q, \Sigma, \delta, q_0, F)$ where $\delta: Q \times \Sigma \to 2^Q$ (the power set of $Q$ ). From state $q$ on symbol $a$ , the machine may move to any state in $\delta(q,a)$ . If $\delta(q,a) = \emptyset$ , that branch dies.

Acceptance. Extend $\delta$ to sets of states and to strings: the NFA accepts $w$ if there exists a sequence of states $q_0, q_1, \ldots, q_{|w|}$ with $q_{i+1} \in \delta(q_i, w_{i+1})$ and $q_{|w|} \in F$ . Equivalently, $\hat{\delta}(q_0, w) \cap F \neq \emptyset$ .

NFA versus DFA. Every DFA is an NFA whose $\delta$ values are always singletons. The converse simulation needs the subset construction.

$\varepsilon$ -NFA

An $\varepsilon$ -NFA allows transitions on $\varepsilon$ as well: $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ .

The $\varepsilon$ -closure $\varepsilon\text{-closure}(S)$ of a set of states $S$ is the set of states reachable from $S$ by zero or more $\varepsilon$ -moves (including the states in $S$ themselves). For an epsilon-closed current set $S$ , reading a symbol $a$ goes to the expression below; for arbitrary $S$ , first take its epsilon-closure:

\varepsilon\text{-closure}\bigl(\bigcup_{q \in S} \delta(q,a)\bigr).

Acceptance: after processing $w$ , the resulting $\varepsilon$ -closed set intersects $F$ .

Why nondeterminism helps design

To accept strings ending with 01, an NFA can stay in a looping start state on $0$ and $1$ , and also "guess" that the current $0$ starts the final 01 by moving to a progress state. Here the saving is nothing (the minimal DFA also has 3 states), but for "the $n$ -th symbol from the end is 1" the NFA has $n+1$ states and the minimal DFA $2^n$ .

How it works

Subset construction (no $\varepsilon$ )

Input: NFA $N = (Q, \Sigma, \delta, q_0, F)$ .

Output: DFA $M = (Q_D, \Sigma, \delta_D, q_D, F_D)$ .

States of $M$ are subsets of $Q$ . Only reachable subsets from $\{q_0\}$ are needed.
Start state $q_D = \{q_0\}$ .
$\delta_D(S, a) = \bigcup_{q \in S} \delta(q,a)$ .
$S$ is accepting iff $S \cap F \neq \emptyset$ .

At most $2^{|Q|}$ DFA states; many are often unreachable.

Subset construction with $\varepsilon$

Same, but the start state is $\varepsilon\text{-closure}(\{q_0\})$ , and

\delta_D(S,a) = \varepsilon\text{-closure}\Bigl(\bigcup_{q \in S} \delta(q,a)\Bigr).

Eliminating $\varepsilon$ -transitions alone

An $\varepsilon$ -NFA converts to an ordinary NFA (still nondeterministic) by: for each state $q$ and symbol $a$ , put an $a$ -transition from $q$ to every state in $\varepsilon\text{-closure}(\delta(\varepsilon\text{-closure}(\{q\}), a))$ after adjusting acceptance so that $q$ is accepting if $\varepsilon\text{-closure}(\{q\})$ meets $F$ . The subset construction already folds this in, so separate elimination is optional.

Algorithms and pseudocode

Text

EPSILON-CLOSURE(N, S)
1  T <- set(S);  stack <- list(S)
2  while stack not empty
3      q <- pop(stack)
4      for each p in N.delta[q][eps]
5          if p not in T
6              add p to T; push p
7  return T

SUBSET-CONSTRUCT(N)
1  qD <- EPSILON-CLOSURE(N, {N.q0})
2  QDmark <- {qD};  work <- queue(qD);  deltaD <- empty map
3  while work not empty
4      S <- dequeue(work)
5      for each a in Sigma
6          T <- EPSILON-CLOSURE(N, union of N.delta[q][a] for q in S)
7          deltaD[S][a] <- T
8          if T not in QDmark
9              add T to QDmark; enqueue T
10 FD <- { S in QDmark | S intersects N.F }
11 return DFA(QDmark, Sigma, deltaD, qD, FD)

Correctness: by induction on $|w|$ , the DFA state after $w$ equals the set of NFA states reachable on $w$ . Hence the languages coincide.

Mathematical explanation

Worst-case blow-up

For $n\ge1$ , the language over $\{0,1\}$ whose $n$ -th symbol from the end is 1 has an $n+1$ -state NFA: a looping start state guesses that 1, then uses $n$ states to count through the remaining $n-1$ symbols to acceptance. Its minimal reachable subset DFA has $2^n$ states, remembering the last $n$ bits (with appropriate leading-zero padding for short strings). This witness proves exponential worst-case growth; the general $2^{|Q|}$ subset upper bound remains valid.

Equivalence chain

\mathrm{DFA} \subseteq \mathrm{NFA} \subseteq \varepsilon\text{-NFA} \subseteq \mathrm{DFA}

(the last inclusion via subset construction), so all three models define the regular languages.

Worked examples

Example 1: NFA for strings ending with `01`

States $q_0,q_1,q_2$ with $q_2$ accepting.

$\delta(q_0,0) = \{q_0,q_1\}$ , $\delta(q_0,1) = \{q_0\}$ .
$\delta(q_1,1) = \{q_2\}$ , $\delta(q_1,0) = \emptyset$ .
$\delta(q_2,0)=\delta(q_2,1)=\emptyset$ .

For a cleaner total NFA that continues matching, send $q_2$ on $0$ to $\{q_0,q_1\}$ and on $1$ to $\{q_0\}$ . The extra edges change nothing: $q_0$ is active after every prefix and already offers the same moves.

Example 2: subset construction

Using the NFA above (with or without the continuation edges from $q_2$ ), the reachable subsets are exactly $\{q_0\}$ , $\{q_0,q_1\}$ and $\{q_0,q_2\}$ . Accepting subsets are those containing $q_2$ , here only $\{q_0,q_2\}$ . The subset $\{q_0,q_1,q_2\}$ is never reached: the only way into $q_2$ is on 1, and no state moves to $q_1$ on 1. The resulting 3-state DFA is already minimal and accepts exactly the strings ending in 01.

NFA for strings ending with 01 and the DFA from subset construction — Figure 1. Left: NFA with states q0, q1, q2 accepting strings ending in 01. Right: reachable subset DFA with exactly three states, {q0}, {q0,q1} and {q0,q2}; the subset {q0,q1,q2} is never reached, and the accepting subset is {q0,q2}.

Example 3: $\varepsilon$ -NFA for $a+b$

Start $s$ , accept $f$ . Edges: $s \xrightarrow{\varepsilon} p$ , $s \xrightarrow{\varepsilon} r$ , $p \xrightarrow{a} f$ , $r \xrightarrow{b} f$ . Then $\varepsilon\text{-closure}(\{s\}) = \{s,p,r\}$ . On $a$ the DFA moves to $\varepsilon\text{-closure}(\{f\})$ . Language $\{a,b\}$ .

Example 4: exponential lower bound sketch for $n=2$

Language: second bit from the end is $1$ . NFA with 3 states guesses; minimal DFA needs 4 states (all length-2 binary memories). For general $n$ , DFA needs $2^n$ states.

Example 5: step-by-step subset table for a 3-state NFA

Take the NFA with transitions from q0 on 0 to {q0,q1}, from q0 on 1 to {q0}, from q1 on 1 to {q2}, and continuation from q2 on 0 to {q0,q1}, from q2 on 1 to {q0}; accept {q2}.

Subset S	on 0	on 1	Accept?
{q0}	{q0,q1}	{q0}	no
{q0,q1}	{q0,q1}	{q0,q2}	no
{q0,q2}	{q0,q1}	{q0}	yes

Start at {q0}. String 01 visits {q0} then {q0,q1} then {q0,q2} (accept). String 010 continues to {q0,q1} (reject). Only these 3 subsets are reachable; a subset such as {q0,q1,q2} can be written down but no input leads to it, so it is not part of the DFA. Listing unreachable subsets gives a wrong state count.

Example 6: subset construction with $\varepsilon$ -moves

The $\varepsilon$ -NFA has states 0, 1, 2 (only state 2 accepts) with $0 \xrightarrow{a} 0$ , $0 \xrightarrow{\varepsilon} 1$ , $1 \xrightarrow{b} 1$ , $1 \xrightarrow{\varepsilon} 2$ , $2 \xrightarrow{c} 2$ . It accepts $a^* b^* c^*$ .

Closures first: $\varepsilon\text{-closure}(\{0\}) = \{0,1,2\}$ , $\varepsilon\text{-closure}(\{1\}) = \{1,2\}$ , $\varepsilon\text{-closure}(\{2\}) = \{2\}$ .

DFA state	on a	on b	on c	Accept?
$A = \{0,1,2\}$ (start)	$A$	$B$	$C$	yes
$B = \{1,2\}$	$\emptyset$	$B$	$C$	yes
$C = \{2\}$	$\emptyset$	$\emptyset$	$C$	yes
$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	no

Four DFA states including the dead set. The start state accepts because its closure already contains 2, so $\varepsilon$ is accepted. abc goes $A, A, B, C$ and is accepted; ba goes $A, B, \emptyset$ and is rejected.

Example 7: the blow-up family, exactly

$L_n = \{ w \in \{0,1\}^* \mid \text{the } n\text{-th symbol from the end is } 1 \}$ . The NFA loops on $q_0$ , guesses the critical 1 by moving to $q_1$ , then reads any $n-1$ symbols through $q_2, \ldots, q_n$ : $n+1$ states. Subset construction reaches exactly $2^n$ subsets (each records which of the last $n$ positions held a 1), and all $2^n$ are pairwise distinguishable: if $x$ and $y$ of length $n$ differ at position $i$ , append any $i-1$ symbols and the $i$ -th position becomes the $n$ -th from the end. For $n = 1, 2, 3, 4$ : NFA 2, 3, 4, 5 states; minimal DFA 2, 4, 8, 16 states.

Different count: the reverse language. "The $n$ -th symbol from the start is 1" needs only $n+2$ DFA states (count to $n$ , then an accepting sink or a dead state). Reversal can change DFA size exponentially, which is why the reversal construction goes through an NFA.

Related material. Alternating finite automata and two-way NFAs also recognize only regular languages; they are not required for GATE CSE.

Important properties and observations

Acceptance is existential ("some path"), not universal.
$\varepsilon$ -closure must be applied after every real symbol move and at the start.
Empty transition sets are legal in NFAs; they just kill that branch.
The subset DFA may include a sink $\emptyset$ if some NFA moves die.
NFAs do not accept "more languages" than DFAs; they accept more succinctly.

Constructions that stay inside NFAs.

Operation	NFA construction	Extra states
Union $L_1 \cup L_2$	new start with $\varepsilon$ to both starts	1
Concatenation $L_1 L_2$	$\varepsilon$ from every accept of $N_1$ to the start of $N_2$ ; only $N_2$ 's accepts remain	0
Star $L^*$	new accepting start with $\varepsilon$ to the old start; $\varepsilon$ from old accepts back to the old start	1
Reversal $L^R$	reverse every edge, old start becomes the only accept, new start with $\varepsilon$ to every old accept	1
Complement	not available directly: determinize first, complete, then swap	up to $2^n$
Intersection	product of the two NFAs (pairs of states)	$n_1 n_2$ total

Swapping accept states of an NFA is not complement. Take the 3-state NFA for "ends with 01" and make $q_0, q_1$ accepting and $q_2$ non-accepting. On input 01 the run that stays in $q_0$ still accepts, so the swapped NFA accepts a string that is in $L$ . It actually accepts every string, since $q_0$ is always active. An NFA accepts if some run accepts; complement needs every run to reject, which only a DFA expresses by a single run.

Star needs a new start state. Making the old start state accepting and adding $\varepsilon$ -edges back to it can accept extra strings when the old start has incoming edges. For example, with an NFA for $a^* b$ whose start state loops on $a$ , that shortcut accepts a, which is not in $(a^* b)^*$ .

NFA versus DFA counts. Same language class; state complexity can differ exponentially.

Common misconceptions.

"Nondeterminism means the machine randomly rejects." In language theory it means existence of an accepting computation, not probability.
" $\varepsilon$ -transitions read the empty symbol as input consuming time." They consume no input symbol.
"Subset construction always produces $2^n$ states." Only reachable subsets matter; often far fewer.

GATE examination perspective

BUILD THE SUBSET TABLE. Rows = subsets found so far; columns = symbols; close under $\varepsilon$ if present.
MARK ACCEPTING SUBSETS. Any subset meeting $F$ , not only $\{f\}$ .
EXPONENTIAL EXAMPLE. " $n$ -th from end is 1" is the standard blow-up witness.
DESIGN WITH GUESSING. NFAs for "contain substring $w$ " or "end with $w$ " are often easier than DFAs; convert if a DFA is required.
DEAD EMPTY SET. If the powerset DFA has $\emptyset$ , it is a rejecting sink, and it counts as a state of the complete DFA.
REACHABLE ONLY. "How many states does the subset construction produce" means reachable subsets from the start closure; never answer $2^n$ unless every subset is reached.
START CLOSURE. With $\varepsilon$ -moves the DFA start is $\varepsilon\text{-closure}(\{q_0\})$ , not $\{q_0\}$ . If the closure meets $F$ , $\varepsilon$ is accepted.
COMPLEMENT TRAP. Flipping accept states of an NFA does not complement it.
STATE BOUNDS. NFA to DFA: at most $2^n$ states and the bound is reached; DFA to NFA: no increase.

Summary

Deterministic Finite Automata: prerequisite.
Equivalence of Regular Expressions and Finite Automata: dependent. Thompson $\varepsilon$ -NFAs from REs.
Pushdown Automata: dependent. Nondeterminism with a stack.

NFA, Epsilon-NFA and Subset Construction

Introduction

Prerequisites

Core concepts

NFA without $\varepsilon$

$\varepsilon$ -NFA

Why nondeterminism helps design

How it works

Subset construction (no $\varepsilon$ )

Subset construction with $\varepsilon$

Eliminating $\varepsilon$ -transitions alone

Algorithms and pseudocode

Mathematical explanation

Worst-case blow-up

Equivalence chain

Worked examples

Example 1: NFA for strings ending with `01`

Example 2: subset construction

Example 3: $\varepsilon$ -NFA for $a+b$

Example 4: exponential lower bound sketch for $n=2$

Example 5: step-by-step subset table for a 3-state NFA

Example 6: subset construction with $\varepsilon$ -moves

Example 7: the blow-up family, exactly

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

NFA without ε\varepsilonε

ε\varepsilonε-NFA

Why nondeterminism helps design

How it works

Subset construction (no ε\varepsilonε)

Subset construction with ε\varepsilonε

Eliminating ε\varepsilonε-transitions alone

Algorithms and pseudocode

Mathematical explanation

Worst-case blow-up

Equivalence chain

Worked examples

Example 1: NFA for strings ending with 01

Example 2: subset construction

Example 3: ε\varepsilonε-NFA for a+ba+ba+b

Example 4: exponential lower bound sketch for n=2n=2n=2

Example 5: step-by-step subset table for a 3-state NFA

Example 6: subset construction with ε\varepsilonε-moves

Example 7: the blow-up family, exactly

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

NFA without $\varepsilon$

$\varepsilon$ -NFA

Subset construction (no $\varepsilon$ )

Subset construction with $\varepsilon$

Eliminating $\varepsilon$ -transitions alone

Example 1: NFA for strings ending with `01`

Example 3: $\varepsilon$ -NFA for $a+b$

Example 4: exponential lower bound sketch for $n=2$

Example 6: subset construction with $\varepsilon$ -moves