Nondeterministic Finite Automata

A Nondeterministic Finite Automaton is a 5-tuple ``` N = (Q, Σ, δ, q0, F) ``` where `Q` is a finite set of states, `Σ` is a finite alphabet, `q0 ∈ Q` is the start state, `F ⊆ Q` is the set of accept states, and the transition function has signature ``` δ : Q × (Σ ∪ {ε}) → P(Q) ``` Here `P(Q)` denotes the power set of `Q` — the set of all subsets of `Q`. This single change in the codomain, compared to a DFA's `δ : Q × Σ → Q`, is what gives an NFA its extra flexibility in three distinct ways. First, `δ(q, a)` may be the empty set, meaning the machine simply has no move and that branch dies. Second, `δ(q, a)` may contain more than one state, meaning the machine can nondeterministically branch into multiple simultaneous possibilities. Third, `δ` is defined on the special symbol `ε` (the empty string), allowing ε-transitions: silent moves the automaton can take without consuming any input at all. Because a single input symbol can lead to many states, and ε-moves can chain together silently, we must be careful about what a "computation" even means. The clean way to do this is the ε-closure of a set of states — everything reachable using only ε-transitions — and an extended transition function `δ̂` describing where the automaton can be after reading a whole string. A string `w` is accepted if `δ̂(q0, w) ∩ F ≠ ∅`, i.e., if some reachable state after consuming all of `w` is an accepting state. This "exists a path" semantics — as opposed to a DFA's single deterministic path — is the entire conceptual difference between the two models, and it is why NFAs are best pictured not as a single token moving through states but as a whole set of tokens moving in parallel, splitting at branches and vanishing when a branch has no valid move.

Step 1 — ε-closure. For a state `q`, define `E(q)` (the ε-closure of `q`) as the set of all states reachable from `q` using zero or more ε-transitions. This extends to a set of states `S` by `E(S) = ⋃_{q∈S} E(q)`. Computing `E(q)` is just a graph reachability search (BFS/DFS) over the subgraph of ε-edges.

Step 2 — the extended transition function. Define `δ̂ : Q × Σ → P(Q)` recursively: ``` δ̂(q, ε) = E({q}) δ̂(q, wa) = E( ⋃_{r ∈ δ̂(q,w)} δ(r, a) ) for w ∈ Σ, a ∈ Σ ``` In words: to process the string `wa`, first find every state reachable after reading `w` (that's `δ̂(q,w)`), take every ordinary `a`-transition out of each of those states, union the results, and then close under ε again (since new ε-moves may now be available). Note the base case already closes under ε, so an NFA can accept `ε` itself by starting in an accept state or reaching one via silent moves.

Step 3 — acceptance. The language recognized by `N` is ``` L(N) = { w ∈ Σ* | δ̂(q0, w) ∩ F ≠ ∅ } ``` A string is in the language exactly when at least one of the (possibly many) states the machine could be in after reading it is an accepting state.

The simulation algorithm. In practice you never enumerate all computation paths individually — that would be exponential in the length of the string in the worst case if done naively. Instead you track the set of currently-possible states, exactly mirroring `δ̂`. This is the "breadth-first, keep a frontier set" simulation: ``` function NFA-ACCEPTS(N = (Q, Σ, δ, q0, F), w = a1 a2 ... an): current ← EPSILON-CLOSURE({q0}) for i in 1..n: next ← ∅ for each state q in current: next ← next ∪ δ(q, a_i) current ← EPSILON-CLOSURE(next) if current = ∅: return REJECT // no branch survives; can short-circuit if current ∩ F ≠ ∅: return ACCEPT else: return REJECT function EPSILON-CLOSURE(S): stack ← S copied into a worklist closure ← S while stack not empty: pop q from stack for each r in δ(q, ε): if r ∉ closure: add r to closure push r onto stack return closure ``` This algorithm processes each of the `n` input symbols by advancing an entire subset of `Q` at once — never more than `|Q|` states are tracked simultaneously, regardless of how many nondeterministic branches conceptually exist. This is precisely the idea that will later be formalized as the subset construction, turning an NFA into an equivalent DFA whose states are subsets of `Q`. The following state diagram shows a small NFA over `Σ = {a, b}` recognizing strings that end in `ab`, built with a deliberately nondeterministic guess about "where the suffix ab begins":

Here `δ(q0, a) = {q0, q1}` — on reading an `a`, the machine forks: one copy stays in `q0` (in case this `a` is not the start of the final `ab`), another moves to `q1` (guessing that it is). Only the branch that correctly guesses the last occurrence of `a` before a final `b` survives to `q2`. No single DFA state can encode "maybe this is the start of the suffix" without extra bookkeeping — which is exactly why the DFA for this same language needs more states (tracking how much of the suffix `ab` has been matched most recently) than this compact 3-state NFA.

Time complexity of simulation. Processing a string of length `n` with the frontier-set algorithm above costs, per symbol, an ε-closure computation and a union over at most `|Q|` states' transition sets. Each ε-closure is a graph traversal over `|Q|` states and at most `|Q|²` ε-edges (worst case a complete ε-graph), costing `O(|Q| + |Q|²) = O(|Q|²)`. So each of the `n` steps costs `O(|Q|²)` in the worst case (or `O(|Q| · |δ|)` counting actual transitions), giving ``` Total time = O(n · |Q|²) Space = O(|Q|) (just the current frontier set) ``` This is polynomial and in fact comparable to DFA simulation up to the constant factor of `|Q|` versus 1 — you are simulating up to `|Q|` deterministic "threads" at once, not an exponential number of individual paths. This matters: naively trying every nondeterministic path separately (a literal computation tree with branching factor up to `|Q|` at each step) would cost `O(|Q|^n)` in the worst case, but tracking the set of reachable states collapses all of that redundancy, since many paths merge into the same state.

Correctness of the simulation. The invariant maintained by the loop is: > After processing `a1 ... ai`, the variable `current` equals `δ̂(q0, a1...ai)` exactly. Base case: before any symbols are read, `current = E({q0}) = δ̂(q0, ε)` by definition of `δ̂` on the empty string. Inductive step: assume `current = δ̂(q0, a1...ai)` holds before processing `a_{i+1}`. The algorithm computes `next = ⋃_{q ∈ current} δ(q, a_{i+1})`, then sets `current ← E(next)`. By the recursive definition of `δ̂`, ``` δ̂(q0, a1...ai a_{i+1}) = E( ⋃_{r ∈ δ̂(q0, a1...ai)} δ(r, a_{i+1}) ) = E( ⋃_{r ∈ current} δ(r, a_{i+1}) ) ``` which is exactly what the algorithm computes. By induction the invariant holds after all `n` symbols, so `current = δ̂(q0, w)`, and checking `current ∩ F ≠ ∅` correctly decides membership by the definition of `L(N)`. ∎

Equivalence with DFAs (stated, not proved here). Every NFA can be converted to an equivalent DFA whose states are subsets of the NFA's states — precisely the sets `current` computed above, reified as first-class states rather than transient variables. This is the subset construction, and it shows NFAs and DFAs are equally expressive: both classes capture exactly the regular languages. The catch is size: the subset-construction DFA can have up to `2^{|Q|}` states, and this blow-up is sometimes unavoidable (there exist NFA families whose minimal equivalent DFA really does grow exponentially). So the tradeoff is real: NFAs buy you succinct, modular descriptions (especially when built compositionally from regular expressions) at the cost of needing a conversion step — or a slower simulation — to run them deterministically at high speed.

Honesty about the model. Nondeterminism here is not parallelism in the sense of extra computational power (unlike, say, nondeterministic Turing machines and the P vs NP question); it is a closed, provably eliminable convenience for finite automata. This is a crucial contrast to keep in mind, and it is one of the cleanest "nondeterminism costs you nothing in the limit, but can cost you exponentially in representation size" stories in the theory of computation.

Consider an NFA recognizing all strings over `{0,1}` containing `01` or ending in `1` — chosen deliberately non-symmetric so guessing genuinely matters and no trivial shortcut trace hides a bug. ``` Q = {s, p, q, r} Σ = {0, 1} q0 = s F = {q, r} δ(s, 0) = {s, p} δ(s, 1) = {s, r} δ(s, ε) = {} δ(p, 1) = {q} δ(p, 0) = {} δ(p, ε) = {} δ(q, 0) = {q} δ(q, 1) = {q} δ(q, ε) = {} δ(r, 0) = {} δ(r, 1) = {r} δ(r, ε) = {} ``` Reading: from `s` the machine always keeps a "stay in `s`" branch alive (to keep scanning for a future `01` or trailing `1`), while also guessing when a `0` might be the start of a `01` (branch to `p`), or when a `1` might be the final symbol (branch to `r`, which only survives on more `1`s). State `q` is a sink accept state reached once an actual `01` has been confirmed; state `r` is an accept state that survives only on trailing `1`s. Trace input `w = 1001`:

After all 4 symbols, `current = {s, r, q}`. Since `q ∈ F` (indeed also `r ∈ F`), `current ∩ F = {q, r} ≠ ∅`, so ACCEPT. This is correct: `1001` contains the substring `01` (positions 2–3) — the `p → q` branch is confirming exactly that — and it also ends in `1`, confirmed independently by the `r` branch surviving. Both "reasons" to accept are witnessed simultaneously as two live states in the frontier, illustrating that acceptance needs only one surviving accepting branch, even when several exist. Contrast with `w = 100`: after symbol `1`, `current = {s, r}`; after the first `0`, `current = {s, p}` (the `r` branch dies since `δ(r,0)=∅`); after the second `0`, `current = {s, p}` again (`p` cannot survive a `0`). Final `current = {s, p}`, and `{s,p} ∩ F = ∅`, so REJECT — correctly, since `100` neither contains `01` nor ends in `1`.

Compiler front-ends build NFAs directly from the regular-expression grammar of a lexical specification (Thompson's construction), then convert to DFAs via subset construction for fast, table-driven scanning — this pipeline underlies tools like `lex`/`flex` and the tokenizers inside virtually every production compiler and interpreter. Text-search utilities and regex engines (`grep`, `ripgrep`, the regex libraries embedded in scripting languages) either compile patterns to NFAs and simulate them with the frontier-set algorithm described here, or convert to DFAs for raw speed at the cost of memory. Network intrusion detection systems and deep-packet-inspection hardware use automaton-based pattern matchers — often NFA-like structures compiled into specialized hardware or bytecode — to scan traffic for signatures without backtracking. XML and JSON schema validators, protocol parsers, and even some game-AI dialogue systems use NFA-style branching state machines whenever "several interpretations of the input are simultaneously plausible" is a natural way to specify behavior. Understanding NFAs is also the essential stepping stone to the NFA-to-DFA Subset Construction, and more broadly to the Equivalence of Regular Expressions and Finite Automata, the theorem that ties together three independently motivated formalisms — regex syntax, deterministic machines, and nondeterministic machines — into one unified notion of "regular language."

Ask the tutor: How exactly does the subset construction turn the frontier-set simulation of an NFA into a full DFA, and why can that DFA sometimes require exponentially many states?