NFA — formal definition, epsilon transitions: Exercises

We use one small example NFA repeatedly. Meet it once, on paper, so no symbol is a surprise later.

Figure — NFA — formal definition, epsilon transitions

Level 1 — Recognition

Recall Solution

True. In an NFA $δ$ outputs a set of states ( $P (Q)$ ). The empty set $\emptyset$ is a perfectly legal set — it just means "this branch dies here." Other branches may still reach $F$ . Contrast with a DFA, where a missing edge really is a modelling gap.

Recall Solution

$ECLOSE (q_{0})$ : start at $q_{0}$ (include it — zero ε-moves allowed). One ε-arrow $q_{0} ε q_{1}$ . From $q_{1}$ there are no ε-arrows. So $ECLOSE (q_{0}) = {q_{0}, q_{1}}$ .
$ECLOSE (q_{1})$ : start at $q_{1}$ , no outgoing ε-arrows. So $ECLOSE (q_{1}) = {q_{1}}$ .

Recall Solution

$δ : Q \times (Σ \cup {ε}) ⟶ P (Q)$ Two differences from a DFA's $δ : Q \times Σ \to Q$ :

Output is a set ( $P (Q)$ ) → allows many/zero targets.
Domain includes $ε$ → allows free moves.

Level 2 — Application

Recall Solution

Base: $\hat{δ} (q_{0}, ε) = ECLOSE (q_{0}) = {q_{0}, q_{1}}$ . Why? Before reading anything, ε-arrows already carry us to $q_{1}$ for free.
Read 1 from set ${q_{0}, q_{1}}$ :
- $δ (q_{0}, 1) = {q_{0}}$
- $δ (q_{1}, 1) = {q_{2}}$
- union $= {q_{0}, q_{2}}$ , then $ECLOSE ({q_{0}, q_{2}}) = {q_{0}, q_{1}, q_{2}}$ (ε-arrow from $q_{0}$ re-adds $q_{1}$ ).
${q_{0}, q_{1}, q_{2}} \cap F = {q_{2}} \neq = \emptyset$ ⇒ accept ✅ (1 ends in 1).

Recall Solution

Base: ${q_{0}, q_{1}}$ .
Read 1: union ${q_{0}, q_{2}}$ → ECLOSE ${q_{0}, q_{1}, q_{2}}$ .
Read 0 from ${q_{0}, q_{1}, q_{2}}$ :
- $δ (q_{0}, 0) = {q_{0}}$
- $δ (q_{1}, 0) = \emptyset$ (that guess dies — a 0 can't be preceded straight into $q_{2}$ )
- $δ (q_{2}, 0) = \emptyset$
- union $= {q_{0}}$ , ECLOSE $= {q_{0}, q_{1}}$ .
${q_{0}, q_{1}} \cap F = \emptyset$ ⇒ reject ✅ (10 ends in 0).

Recall Solution

$Q = {p_{0}, p_{1}, p_{2}}$ , start $p_{0}$ , $F = {p_{2}}$ .

$δ (p_{0}, a) = {p_{0}, p_{1}}$ , $δ (p_{0}, b) = {p_{0}}$
$δ (p_{1}, b) = {p_{2}}$ , $δ (p_{1}, a) = \emptyset$
$δ (p_{2}, a) = {p_{2}}$ , $δ (p_{2}, b) = {p_{2}}$

Why nondeterminism helps: at $p_{0}$ on a we guess "this a starts the ab" (go to $p_{1}$ ) while also keeping the "not yet" branch alive at $p_{0}$ . If a b follows, the guess pays off ( $p_{2}$ ) and $p_{2}$ loops forever, so acceptance sticks. The DFA would need explicit bookkeeping of each partial match — the NFA gets it for free.

Level 3 — Analysis

Recall Solution

Reachability of $q_{2}$ : The only way into $q_{2}$ is $δ (q_{1}, 1)$ . The only way into $q_{1}$ is the ε-arrow from $q_{0}$ . And $q_{0}$ is reachable after reading any prefix (it loops on 0 and 1). So the accepting path is: sit in $q_{0}$ through the whole prefix, ε-slide to $q_{1}$ , read a final 1 → $q_{2}$ .

( $\Rightarrow$ ) If $N_{1}$ accepts $w$ , that path required a last consumed symbol equal to 1 (the $q_{1} 1 q_{2}$ step). Hence $w$ ends in 1.

( $\Leftarrow$ ) If $w = u 1$ ends in 1: read $u$ staying in $q_{0}$ (loops absorb everything), ε-slide to $q_{1}$ , read the final 1 → $q_{2} \in F$ . Accept.

Empty string $w = ε$ : $\hat{δ} (q_{0}, ε) = ECLOSE (q_{0}) = {q_{0}, q_{1}}$ . Intersect with $F = {q_{2}}$ : empty ⇒ reject. Correct — the empty string does not "end in 1."

Recall Solution

ECLOSE( $r_{0}$ ): follow ε-chain $r_{0} \to r_{1} \to r_{2}$ . So $ECLOSE (r_{0}) = {r_{0}, r_{1}, r_{2}}$ . Why chain fully? "zero or more" ε-moves means we follow the arrows transitively until nothing new appears.

$w = ε$ : $\hat{δ} (r_{0}, ε) = {r_{0}, r_{1}, r_{2}}$ , contains $r_{2} \in F$ ⇒ accept.
$w = a$ : from ${r_{0}, r_{1}, r_{2}}$ read a: only $δ (r_{2}, a) = {r_{2}}$ fires; union ${r_{2}}$ ; ECLOSE ${r_{2}}$ ; contains $r_{2}$ ⇒ accept. This machine accepts $a^{*}$ .

Recall Solution

Number of subsets of a 3-element set $= 2^{3} = 8$ : namely $\emptyset, {q_{0}}, {q_{1}}, {q_{2}}, {q_{0}, q_{1}}, {q_{0}, q_{2}}, {q_{1}, q_{2}}, {q_{0}, q_{1}, q_{2}}$ . Why it matters: the subset construction makes each DFA state one subset of NFA states (the set the NFA "is in"). Hence a $3$ -state NFA yields a DFA with at most $2^{3} = 8$ states — that power-set blow-up is the price of removing nondeterminism, and it links directly to Regular Languages being closed under this conversion.

Level 4 — Synthesis

Recall Solution

Reuse the union pattern from the parent note. $Q = {s, a, b}$ , start $s$ , $F = {a, b}$ .

$δ (s, ε) = {a, b}$ (split into both branches for free)
$δ (a, 0) = {a}$ , $δ (a, 1) = \emptyset$
$δ (b, 1) = {b}$ , $δ (b, 0) = \emptyset$

Trace 11:

Base: $ECLOSE (s) = {s, a, b}$ .
Read 1: $s \to \emptyset$ , $a \to \emptyset$ , $b \to {b}$ ; union ${b}$ ; ECLOSE ${b}$ .
Read 1: $b \to {b}$ ⇒ ${b}$ . Contains $b \in F$ ⇒ accept ✅.

Trace 01:

Base: ${s, a, b}$ .
Read 0: only $a \to {a}$ ; set ${a}$ .
Read 1: $a \to \emptyset$ ; set $\emptyset$ . Empty ⇒ reject ✅ (mixed string).

Why ε makes this clean: the single free split at $s$ is the union construction — a hallmark of Closure Properties of Regular Languages. Compare with the Regular Expressions 0*|1*: the | mirrors the ε-branch.

Recall Solution

Guess the 1: $Q = {t_{0}, t_{1}, t_{2}, t_{3}}$ , start $t_{0}$ , $F = {t_{3}}$ .

$δ (t_{0}, 0) = {t_{0}}$ , $δ (t_{0}, 1) = {t_{0}, t_{1}}$ (guess: this 1 is 3rd-from-end)
$δ (t_{1}, 0) = {t_{2}}$ , $δ (t_{1}, 1) = {t_{2}}$
$δ (t_{2}, 0) = {t_{3}}$ , $δ (t_{2}, 1) = {t_{3}}$
$t_{3}$ : no outgoing edges (must be the end).

Trace 100:

Base: ${t_{0}}$ (no ε-arrows here, ECLOSE is trivial).
Read 1: ${t_{0}, t_{1}}$ (kept the "not yet" branch and the guess).
Read 0: $t_{0} \to {t_{0}}$ , $t_{1} \to {t_{2}}$ ; union ${t_{0}, t_{2}}$ .
Read 0: $t_{0} \to {t_{0}}$ , $t_{2} \to {t_{3}}$ ; union ${t_{0}, t_{3}}$ .
${t_{0}, t_{3}} \cap F = {t_{3}} \neq = \emptyset$ ⇒ accept ✅ (in 100, third-from-end is the 1).

Level 5 — Mastery

Recall Solution

Effect of the new arrow $q_{2} \to q_{0}$ : $q_{2}$ is accepting, $q_{0}$ is not, and $q_{0}$ was already reachable on every prefix. The new arrow only adds $q_{0}$ (and via its ε-arrow $q_{1}$ ) to any set already containing $q_{2}$ . It never removes states, and it never adds $q_{2}$ to a set that lacked it.

So a string previously accepted (reached a set containing $q_{2}$ ) still reaches a set containing $q_{2}$ (nothing is deleted) ⇒ still accepted.
A string previously rejected reached a set without $q_{2}$ ; the new arrow fires only from $q_{2}$ , so it cannot manufacture a $q_{2}$ where none existed ⇒ still rejected. Conclusion: $L (N_{1})$ is unchanged — still "ends in 1." Silent arrows only matter when they open a new route into $F$ .

Recall Solution

Bound: at most $2^{n}$ DFA states (one per subset of $Q$ ). Tight in the worst case; often far fewer after removing unreachable subsets. Why $\emptyset$ is a legit DFA state: when all NFA branches die on some symbol, the "current set" becomes $\emptyset$ . In the DFA this is a non-accepting dead state that loops to itself on every symbol (since $\hat{δ}$ of the empty set is empty). It is the DFA's honest bookkeeping of "no NFA branch survives." This ties to DFA — formal definition, where every transition must be total — the $\emptyset$ state supplies the missing edges.

Recall Solution

Concept: Intersection of two regular languages is regular — a Closure Properties of Regular Languages result, realised by the product construction (run both machines' state-sets in parallel, accept when both accept). You would take $N_{1}$ (ends in 1) and a 2-state parity NFA (even length), form the product, and mark states final only where both components are final. Verify $N_{1}$ on 01:

Base: $ECLOSE (q_{0}) = {q_{0}, q_{1}}$ .
Read 0: $q_{0} \to {q_{0}}$ , $q_{1} \to \emptyset$ ; union ${q_{0}}$ ; ECLOSE ${q_{0}, q_{1}}$ .
Read 1: $q_{0} \to {q_{0}}$ , $q_{1} \to {q_{2}}$ ; union ${q_{0}, q_{2}}$ ; ECLOSE ${q_{0}, q_{1}, q_{2}}$ .
Contains $q_{2} \in F$ ⇒ accept ✅. (01 ends in 1; its length is even, so it would also survive the intersection.)

Recap

Recall One-line reminders (hide answers)

Output type of NFA $δ$ ? ::: $P (Q)$ — a set of states.
When accept? ::: $\hat{δ} (q_{0}, w) \cap F \neq = \emptyset$ .
Meaning of $δ (q, a) = \emptyset$ ? ::: that branch dies, not an error.
DFA states from an $n$ -state NFA (worst case)? ::: $2^{n}$ .
How to get intersection of two regular languages? ::: product construction (AND of both machines).