NFA — formal definition, epsilon transitions

1. What is nondeterminism, really?

2. The formal 5-tuple (built from scratch)

We want to nail down "machine with guessing + free moves." What pieces do we minimally need?

A finite collection of memory states → call it $Q$ .
The alphabet of input symbols → $\Sigma$ .
A rule saying where we can go → the transition function $\delta$ .
A place to start → $q_0$ .
A way to say "you win" → accepting states $F$ .

The only twist vs DFA is the output type of $\delta$ .

3. ε-closure (the tool that handles free moves)

Because ε-moves are free, before/after reading a symbol the machine can silently slide along ε-arrows. We must collect everything reachable for free.

Why "including $q$ itself"? Zero ε-moves is allowed — you can always "stay put for free."

4. Extended transition $\hat\delta$ (running a whole string)

$\delta$ handles one symbol. We derive the rule for a full string $w$ , folding in ε-moves correctly.

Base case: before reading anything, you're wherever ε-moves take you from the start. $\hat\delta(q,\varepsilon)=\text{ECLOSE}(q)$

Inductive step: to process $w=xa$ (string $x$ then symbol $a$ ):

Let $R=\hat\delta(q,x)$ — the set of states after reading $x$ .
From each $r\in R$ , read $a$ : collect $\bigcup_{r\in R}\delta(r,a)$ .
Then take ε-closure (free slides after consuming $a$ ).

Figure — NFA — formal definition, epsilon transitions

5. Worked examples

Worked example Example 1 — multiple targets, no ε

Language: strings over $\{0,1\}$ that end in 1. $Q=\{q_0,q_1\}$ , start $q_0$ , $F=\{q_1\}$ .

$\delta(q_0,0)=\{q_0\}$ , $\delta(q_0,1)=\{q_0,q_1\}$
$\delta(q_1,0)=\varnothing$ , $\delta(q_1,1)=\varnothing$

Trace 101:

Start: $\{q_0\}$ . Why? ECLOSE( $q_0$ )= $\{q_0\}$ (no ε-arrows).
read 1: $\delta(q_0,1)=\{q_0,q_1\}$ . Why this step? The NFA guesses: maybe this 1 is the last one ( $q_1$ ), maybe not ( $q_0$ ).
read 0: from $q_0\to\{q_0\}$ ; from $q_1\to\varnothing$ . So $\{q_0\}$ . Why? The $q_1$ guess died (a 0 can't be the end), but $q_0$ survives.
read 1: from $q_0\to\{q_0,q_1\}$ . Result $\{q_0,q_1\}$ .
$\{q_0,q_1\}\cap F=\{q_1\}\neq\varnothing$ ⇒ accept ✅

Worked example Example 2 — ε-transitions (union made easy)

Language: strings of the form $0^*$ or $1^*$ (all 0's or all 1's, empty allowed). States: a fresh start $s$ ; an all-0 loop $a$ ; an all-1 loop $b$ . $F=\{a,b\}$ .

$\delta(s,\varepsilon)=\{a,b\}$ ← split for free into both branches
$\delta(a,0)=\{a\}$ , $\delta(a,1)=\varnothing$
$\delta(b,1)=\{b\}$ , $\delta(b,0)=\varnothing$

Trace 00:

Start: $\hat\delta(s,\varepsilon)=\text{ECLOSE}(s)=\{s,a,b\}$ . Why? ε-arrows carry $s$ into both $a$ and $b$ for free.
read 0: from $s\to\varnothing$ , $a\to\{a\}$ , $b\to\varnothing$ ; union $=\{a\}$ ; ECLOSE $=\{a\}$ .
read 0: from $a\to\{a\}$ ⇒ $\{a\}$ .
$\{a\}\cap F\neq\varnothing$ ⇒ accept ✅ Trace 01: after first 0 we're in $\{a\}$ ; read 1 ⇒ $\delta(a,1)=\varnothing$ . Set empties ⇒ reject ✅ (mixed string correctly rejected).

6. Common mistakes (steel-manned)

7. Active recall

Recall Test yourself (hide answers)

What is the output type of an NFA's $\delta$ ? → $\mathcal{P}(Q)$ , a set of states.
What makes an NFA accept $w$ ? → some path: $\hat\delta(q_0,w)\cap F\neq\varnothing$ .
Why include $q$ in $\text{ECLOSE}(q)$ ? → zero ε-moves is allowed.
Is $\varepsilon\in\Sigma$ ? → No.
Are NFAs more powerful than DFAs? → No; same language class (regular).

What is the formal 5-tuple of an NFA?

(Q,\Sigma,\delta,q_0,F)

with

\delta:Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)

How does an NFA's

\delta

differ from a DFA's?

NFA returns a set (

\mathcal{P}(Q)

) and allows

\varepsilon

in its domain; DFA returns a single state and has no

\varepsilon

Define ε-closure of a state

q

All states reachable from

q

by zero or more ε-transitions, including

q

itself.

When does an NFA accept a string

w

When

\hat\delta(q_0,w)\cap F\neq\varnothing

— at least one reachable state is accepting.

What is the base case of

\hat\delta

\hat\delta(q,\varepsilon)=\text{ECLOSE}(q)

Write the inductive step of

\hat\delta

\hat\delta(q,xa)=\text{ECLOSE}\big(\bigcup_{r\in\hat\delta(q,x)}\delta(r,a)\big)

\varepsilon

a member of

\Sigma

No; ε only appears in

\delta

's domain as

\Sigma\cup\{\varepsilon\}

What does

\delta(q,a)=\varnothing

mean in an NFA?

That branch dies on

a

; it is not an error, other branches may still accept.

Are NFAs strictly more powerful than DFAs?

No — both recognize exactly the regular languages.

Recall Feynman: explain to a 12-year-old

Imagine you're playing a maze game and at some doors you can clone yourself and send copies down several hallways at once. Some doors are even secret slides that move a clone instantly without using up a step (that's the ε-move). You win if any copy of you reaches the treasure room. You don't need all of them — just one lucky clone. An NFA is a machine that plays exactly this game with letters of a word as steps.

Connections

DFA — formal definition — the deterministic special case ( $\delta$ returns singletons, no ε).
Subset Construction (NFA to DFA) — proves NFA = DFA in power.
Regular Languages — exactly the languages NFAs/DFAs accept.
Regular Expressions — Thompson's construction builds ε-NFAs from regexes.
Closure Properties of Regular Languages — union/concat/star designed easily with ε-NFAs.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, DFA bahut strict hota hai: har state se, har symbol par, exactly ek hi next state. NFA thoda chill cousin hai — ek state se ek symbol par tum multiple states me ja sakte ho, ya kahin nahi (empty set), ya bina koi symbol padhe hi free me move kar sakte ho. Yeh free move hi epsilon transition hai. Soch lo jaise tum maze me apne clones bana rahe ho aur sab hallways try kar rahe ho — agar koi ek bhi clone treasure (final state) tak pahunch gaya, to string accept ho gayi. Sabhi clones ko pahunchna zaroori nahi.

Formal definition same 5-tuple hai $(Q,\Sigma,\delta,q_0,F)$ , bas ek twist: $\delta$ ka output ek single state nahi, balki ek set of states ( $\mathcal{P}(Q)$ ) hai, aur input me $\varepsilon$ allowed hai. Yahi do changes poora khel hain. Epsilon ko $\Sigma$ ke andar mat daalna — woh sirf $\delta$ ke domain me $\Sigma\cup\{\varepsilon\}$ ke roop me aata hai, kabhi string ka actual symbol nahi banta.

Jab string run karte ho, har symbol padhne ke baad ECLOSE (epsilon-closure) lena nahi bhulna — matlab jitne states free epsilon arrows se reach ho sakte hain, sab add kar do. Yeh step log aksar miss kar dete hain aur galti se reject kar dete hain. Acceptance ka rule: $\hat\delta(q_0,w)\cap F\neq\varnothing$ — yaani kam se kam ek reachable state final hona chahiye.

Important baat: NFA, DFA se zyada powerful nahi hai. Dono exactly same languages (regular languages) recognize karte hain — subset construction se NFA ko DFA me convert kar sakte ho. NFA ka faayda sirf yeh hai ki design karna aasaan ho jaata hai, especially union, concatenation, aur star jaise operations ke liye epsilon transitions bahut handy hote hain.

NFA — formal definition, epsilon transitions

1. What is nondeterminism, really?

2. The formal 5-tuple (built from scratch)

3. ε-closure (the tool that handles free moves)

4. Extended transition $\hat\delta$ (running a whole string)

5. Worked examples

6. Common mistakes (steel-manned)

7. Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections