NFA — formal definition, epsilon transitions: Worked examples

The scenario matrix

Before any examples, let us enumerate the classes of situations an NFA computation can land in. Each row is one distinct behaviour; the examples below are labelled with the cell they cover.

#	Case class	What is special about it	Covered by
A	All branches survive, one is final	Multiple guesses alive at once, acceptance is existential	Ex 1
B	A branch dies ( $δ = \emptyset$ on part of the set)	A guess becomes invalid but others continue	Ex 1, Ex 2
C	Every branch dies (empty set)	Whole computation collapses → reject	Ex 2
D	ε-move BEFORE reading any symbol	ε-closure of the start decides the empty string	Ex 3
E	ε-move AFTER a symbol reaches a final state	Skipping closure would wrongly reject	Ex 4
F	The empty string $ε$ itself	Degenerate input, length-zero	Ex 3
G	A chain of ε-moves ( $q \to r \to s$ for free)	ε-closure must be transitive, not one hop	Ex 4
H	Real-world word problem	Modelling a spec as an NFA	Ex 5
I	Exam twist: "some path" vs "all paths"	The classic trap of universal vs existential accept	Ex 6
J	Limiting / longest-guess behaviour	A guess that must be delayed as long as possible	Ex 7

Example 1 — all branches alive, then one dies (cells A, B)

Forecast: it ends in 1, so I expect... accept. But watch which branches live and die.

Look at the machine and the trace of state-sets below.

Figure — NFA — formal definition, epsilon transitions

Start set $= ECLOSE (q_{0}) = {q_{0}}$ . Why this step? Before reading anything we sit at $q_{0}$ , and there are no ε-arrows, so nothing is reachable for free.
Read 1: $δ (q_{0}, 1) = {q_{0}, q_{1}}$ . Set $= {q_{0}, q_{1}}$ . Why this step? This is the nondeterministic guess (cell A): the machine keeps both possibilities — "this 1 is the last symbol" ( $q_{1}$ ) and "it is not" ( $q_{0}$ ).
Read 1: from $q_{0} \to {q_{0}, q_{1}}$ , from $q_{1} \to \emptyset$ . Union $= {q_{0}, q_{1}}$ . Why this step? The old $q_{1}$ guess dies (cell B) because $q_{1}$ has no outgoing edge — but a fresh $q_{1}$ guess is born from $q_{0}$ .
Read 0: from $q_{0} \to {q_{0}}$ , from $q_{1} \to \emptyset$ . Union $= {q_{0}}$ . Why this step? A 0 can never be the ending 1, so the $q_{1}$ branch dies again; only the "not yet finished" branch $q_{0}$ survives.
Read 1: from $q_{0} \to {q_{0}, q_{1}}$ . Set $= {q_{0}, q_{1}}$ . Why this step? Final symbol; the guess "this is the end" is reborn as $q_{1}$ .

Verify: final set ${q_{0}, q_{1}}$ , and ${q_{0}, q_{1}} \cap F = {q_{1}} \neq = \emptyset$ ⇒ accept ✅. Sanity check: 1101 does end in 1, matching the forecast.

Example 2 — the whole set empties out (cell C)

Forecast: it ends in 0, so I expect reject — and I bet the state-set becomes empty.

Start $= {q_{0}}$ . Why? Same reason as before.
Read 1: ${q_{0}, q_{1}}$ . Why? Guess spawned.
Read 1: ${q_{0}, q_{1}}$ . Why? Old $q_{1}$ dies, new one born.
Read 0: from $q_{0} \to {q_{0}}$ , $q_{1} \to \emptyset$ ⇒ ${q_{0}}$ . Why? The end-guess dies on a 0.
Read 0: from $q_{0} \to {q_{0}}$ ⇒ ${q_{0}}$ . Why? $q_{0}$ loops on 0.

Verify: final set ${q_{0}}$ , and ${q_{0}} \cap F = \emptyset$ ⇒ reject ✅.

Example 3 — the empty string, decided by ε-closure of the start (cells D, F)

Forecast: $0^{*}$ includes zero copies of 0, i.e. the empty string — so I expect accept, purely from the start's ε-closure.

Apply the base case: $\hat{δ} (s, ε) = ECLOSE (s)$ . Why this step? The extended transition for the empty string is defined as the ε-closure of the start — that is literally rule "before reading anything, slide along all free arrows."
Compute $ECLOSE (s)$ : start with ${s}$ , follow ε to $a$ and $b$ ⇒ ${s, a, b}$ . Why this step? ε-closure collects everything reachable by zero or more ε-moves, including $s$ itself (cell D).

Verify: ${s, a, b} \cap F = {a, b} \neq = \emptyset$ ⇒ accept ✅. This confirms cell F: the empty string's fate is settled entirely by $ECLOSE (q_{0})$ — no symbol is ever read.

Example 4 — ε-chain reached only AFTER a symbol (cells E, G)

Forecast: after reading a I land on $p_{1}$ , which is not final — a careless reader would say reject. Let's not be careless.

Start set $= ECLOSE (p_{0})$ . $p_{0}$ has no ε-edge, so $= {p_{0}}$ . Why this step? Base case again.
Read a: collect $⋃_{r \in {p_{0}}} δ (r, a) = δ (p_{0}, a) = {p_{1}}$ . Why this step? Consume the symbol from every current state.
Now take ε-closure of the result (this is the step people skip — cell E): $ECLOSE ({p_{1}})$ : from $p_{1} ε p_{2} ε p_{3}$ , so the closure is ${p_{1}, p_{2}, p_{3}}$ . Why this step? ε-moves are free; after consuming a the machine may silently slide forward, and it must be allowed to do so transitively through the whole chain (cell G), not just one hop.

Verify: final set ${p_{1}, p_{2}, p_{3}}$ , and $\cap F = {p_{2}} \neq = \emptyset$ ⇒ accept ✅. Had we forgotten the post-symbol closure (stopping at ${p_{1}}$ ) we would have wrongly rejected. And had we taken only one ε-hop (stopping at ${p_{1}, p_{2}}$ ) we'd still be fine here — but a machine whose only final state was reachable via two ε-hops would break. Always close fully.

Example 5 — real-world word problem (cell H)

Forecast: 0123 contains 123, so the machine should accept. Substring-detection is the textbook place where NFAs shine, because you get to guess where the pattern starts.

Machine: $Q = {r_{0}, r_{1}, r_{2}, r_{3}}$ , start $r_{0}$ , $F = {r_{3}}$ .

$r_{0}$ loops on every symbol: $δ (r_{0}, x) = {r_{0}}$ for all $x \in Σ$ ; plus $δ (r_{0}, 1) = {r_{0}, r_{1}}$ .
$δ (r_{1}, 2) = {r_{2}}$ , $δ (r_{2}, 3) = {r_{3}}$ .
$r_{3}$ loops on every symbol: $δ (r_{3}, x) = {r_{3}}$ .

Why this design? $r_{0}$ "waits and guesses" — on a 1 it may either keep waiting ( $r_{0}$ ) or bet that this is the start of 123 ( $r_{1}$ ). $r_{1} \to r_{2} \to r_{3}$ then checks the exact sequence. $r_{3}$ is a sink that stays accepting.

Start $= {r_{0}}$ .
Read 0: $δ (r_{0}, 0) = {r_{0}}$ ⇒ ${r_{0}}$ . Why? No pattern yet; keep waiting.
Read 1: $δ (r_{0}, 1) = {r_{0}, r_{1}}$ ⇒ ${r_{0}, r_{1}}$ . Why? Guess "the pattern starts here" spawns $r_{1}$ , while $r_{0}$ hedges.
Read 2: $r_{0} \to {r_{0}}$ , $r_{1} \to {r_{2}}$ ⇒ ${r_{0}, r_{2}}$ . Why? The bet is paying off — $r_{1}$ advances to $r_{2}$ .
Read 3: $r_{0} \to {r_{0}}$ , $r_{2} \to {r_{3}}$ ⇒ ${r_{0}, r_{3}}$ . Why? Pattern completed on the winning branch.

Verify: final set ${r_{0}, r_{3}}$ , $\cap F = {r_{3}} \neq = \emptyset$ ⇒ accept ✅. Cross-check: 0123 literally contains 123, matching the forecast.

Example 6 — exam twist: "some path" vs "all paths" (cell I)

Forecast: 0110 does not contain 123, so the correct answer is reject — regardless of how many branches stay alive.

Start $= {r_{0}}$ .
Read 0: ${r_{0}}$ .
Read 1: ${r_{0}, r_{1}}$ . Why? Guess spawned.
Read 1: $r_{0} \to {r_{0}, r_{1}}$ , $r_{1} \to \emptyset$ (there is no $δ (r_{1}, 1)$ ). Union $= {r_{0}, r_{1}}$ . Why? The old $r_{1}$ dies (it needed a 2), a new $r_{1}$ is born.
Read 0: $r_{0} \to {r_{0}}$ , $r_{1} \to \emptyset$ . Union $= {r_{0}}$ . Why? End-of-pattern guesses all fail.

Verify: final set ${r_{0}}$ , $\cap F = \emptyset$ ⇒ reject ✅.

Example 7 — limiting behaviour: the guess that must be delayed (cell J)

Forecast: the third-from-last symbol of 1 1 0 0 is the 1 at position 2 → so accept. The interesting part: the machine must delay its guess to exactly the right 1.

Why this design (cell J)? $t_{0}$ loops forever, so it can absorb any prefix. The branch $t_{1} \to t_{2} \to t_{3}$ counts exactly three more symbols. The nondeterminism guesses "the 1 I am reading right now sits three-from-the-end" — the machine must hold all such guesses simultaneously and let the wrong ones die at the end.

Start $= {t_{0}}$ .
Read 1: $δ (t_{0}, 1) = {t_{0}, t_{1}}$ ⇒ ${t_{0}, t_{1}}$ . Why? First guess: "this 1 is 3-from-end."
Read 1: $t_{0} \to {t_{0}, t_{1}}$ , $t_{1} \to {t_{2}}$ ⇒ ${t_{0}, t_{1}, t_{2}}$ . Why? Old guess advances ( $t_{1} \to t_{2}$ ); a fresh guess spawns from the second 1.
Read 0: $t_{0} \to {t_{0}}$ , $t_{1} \to {t_{2}}$ , $t_{2} \to {t_{3}}$ ⇒ ${t_{0}, t_{2}, t_{3}}$ . Why? Each pending count steps forward; one guess reaches the accepting $t_{3}$ .
Read 0: $t_{0} \to {t_{0}}$ , $t_{2} \to {t_{3}}$ , $t_{3} \to \emptyset$ ⇒ ${t_{0}, t_{3}}$ . Why? $t_{3}$ has no outgoing edge, so that guess dies — but another guess just completed its count of three and lands in $t_{3}$ .

Verify: final set ${t_{0}, t_{3}}$ , $\cap F = {t_{3}} \neq = \emptyset$ ⇒ accept ✅. Cross-check by hand: 1100, three from the end = the symbol before the last two = the second 1 = 1. ✅

How the cells connect back

These behaviours are exactly what makes the Subset Construction (NFA to DFA) necessary: each set of states you saw above ( ${q_{0}, q_{1}}$ , ${r_{0}, r_{3}}$ , ${t_{0}, t_{2}, t_{3}}$ ...) becomes a single DFA state. The empty set becomes the DFA's dead state. Because every NFA reduces this way, they accept precisely the Regular Languages, the same class captured by Regular Expressions and preserved under Closure Properties of Regular Languages — no more, no less than a DFA.

Recall Which cell was which? (hide answers)

Where does an empty final set come from? ::: All branches died (Ex 2 / Ex 6) — a clean reject, not a crash.
What single step do people skip, and where? ::: ε-closure after reading a symbol (Ex 4, cell E).
What decides acceptance of $ε$ ? ::: $ECLOSE (q_{0})$ (Ex 3, cells D/F).
Why must ε-closure be transitive? ::: ε-chains (Ex 4, cell G): $p_{1} \to p_{2} \to p_{3}$ for free.
"A branch stayed alive so accept" — true? ::: No; only a branch ending in $F$ counts (Ex 6, cell I).

Trace of "ends in 1" NFA on 1101 — final state-set?

{q_{0}, q_{1}}

, which meets

F

, so accept.

Does the

0^{*} ∣ 1^{*}

NFA accept the empty string, and why?

Yes —

ECLOSE (s) = {s, a, b}

contains the final state

a

In the ε-chain NFA (

p_{1} \to p_{2} \to p_{3}

free), does a accept?

Yes — after reading a you reach

{p_{1}}

, whose ε-closure

{p_{1}, p_{2}, p_{3}}

contains

p_{2} \in F

"Some branch stayed alive, so the NFA accepts." True or false?

False — acceptance needs a branch that ends in a final state, i.e.

\hat{δ} (q_{0}, w) \cap F \neq = \emptyset