NFA and ε-NFA — Nondeterminism, Epsilon Moves and NFA to DFA Conversion (Subset Construction)

A DFA must know exactly where to go next. A Nondeterministic Finite Automaton (NFA) is allowed to guess: from one state, the same symbol may lead to several states (or none), and ε-moves let it jump without reading anything. Surprisingly, this extra freedom doesn't add power — every NFA has an equivalent DFA — but it makes machines much easier to design.

1. NFA definition

N = (Q, Σ, δ, q₀, F) where δ: Q × (Σ ∪ {ε}) → P(Q) — a set of next states (possibly empty).

A string is accepted if at least one possible path ends in an accepting state.

Example: binary strings whose third symbol from the end is 1. The NFA simply guesses when that 1 arrives:

Four states. A DFA for the same language needs 8 states (it must remember the last three symbols) — and for "k-th from the end" an NFA needs k + 1 states while a DFA needs 2ᵏ. Nondeterminism can be exponentially more compact.

2. Simulating an NFA: track a set of states

Instead of guessing, follow all possibilities at once:

from itertools import product

nfa = {("q0", "0"): {"q0"}, ("q0", "1"): {"q0", "q1"},
       ("q1", "0"): {"q2"}, ("q1", "1"): {"q2"},
       ("q2", "0"): {"q3"}, ("q2", "1"): {"q3"}}
start, accepting = "q0", {"q3"}

def nfa_run(w, trace=False):
    current = {start}
    for ch in w:
        current = set().union(*(nfa.get((s, ch), set()) for s in current))
        if trace:
            print(f"  after '{ch}': {sorted(current)}")
    return bool(current & accepting)

print("0110:"); print("accepted:", nfa_run("0110", trace=True))
ok = all(nfa_run("".join(t)) == (len(t) >= 3 and t[-3] == "1")
         for n in range(11) for t in product("01", repeat=n))
print("matches definition on all strings up to length 10:", ok)

0110:
  after '0': ['q0']
  after '1': ['q0', 'q1']
  after '1': ['q0', 'q1', 'q2']
  after '0': ['q0', 'q2', 'q3']
accepted: True
matches definition on all strings up to length 10: True

0110: the third symbol from the end is 1 (0110) → accepted.

3. ε-NFA and ε-closure

An ε-move changes state without consuming input — handy for gluing machines together (union, concatenation, star — next lesson).

ε-closure(q) = all states reachable from q using only ε-moves (including q itself). To simulate an ε-NFA, take the ε-closure after every step (and at the start).

eps = {"A": {"B", "D"}, "B": {"C"}}          # A -ε-> B, A -ε-> D, B -ε-> C

def eps_closure(states):
    stack, closure = list(states), set(states)
    while stack:
        s = stack.pop()
        for t in eps.get(s, set()):
            if t not in closure:
                closure.add(t); stack.append(t)
    return closure

print("ε-closure(A) =", sorted(eps_closure({"A"})))
print("ε-closure(B) =", sorted(eps_closure({"B"})))

ε-closure(A) = ['A', 'B', 'C', 'D']
ε-closure(B) = ['B', 'C']

4. Subset construction: NFA → DFA

Each DFA state is a set of NFA states. Start from {q₀} (its ε-closure), and for each symbol compute where the set goes. Any set containing an NFA accepting state is accepting. Only reachable sets are created (at most 2ⁿ).

Worked example (classic exam style): NFA for strings over {a, b} ending in ab:

nfa2 = {("q0", "a"): {"q0", "q1"}, ("q0", "b"): {"q0"}, ("q1", "b"): {"q2"}}
nfa2_accept = {"q2"}

def subset_construction(delta, start, accept, alphabet):
    start_set = frozenset([start])
    dfa, todo, seen = {}, [start_set], {start_set}
    while todo:
        S = todo.pop(0)
        for c in alphabet:
            T = frozenset().union(*(delta.get((s, c), set()) for s in S))
            dfa[(S, c)] = T
            if T not in seen:
                seen.add(T); todo.append(T)
    name = lambda S: "{" + ",".join(sorted(S)) + "}" if S else "∅"
    print(f"{'DFA state':12} {'a':12} {'b':12}")
    for S in sorted(seen, key=lambda x: (len(x), sorted(x))):
        mark = "*" if S & accept else " "
        print(f"{mark}{name(S):11} {name(dfa[(S, 'a')]):12} {name(dfa[(S, 'b')]):12}")
    return dfa, seen

dfa2, states = subset_construction(nfa2, "q0", nfa2_accept, "ab")
print("DFA states created:", len(states), "(out of 2^3 = 8 possible)")

DFA state    a            b           
 {q0}        {q0,q1}      {q0}        
 {q0,q1}     {q0,q1}      {q0,q2}     
*{q0,q2}     {q0,q1}      {q0}        
DFA states created: 3 (out of 2^3 = 8 possible)

Only 3 of the 8 possible subsets are reachable — that's typical in practice.

5. Why NFAs matter

• Equivalent power: DFA, NFA and ε-NFA all recognise exactly the regular languages.
• Design: NFAs are often far simpler to draw ("guess the right moment").
• Regex engines: Thompson's construction turns a regex into an ε-NFA (next lesson); some engines simulate the NFA directly (set of states, guaranteed linear time), others convert to a DFA for speed.
• Trade-off: NFA = fewer states but more work per symbol; DFA = possibly exponentially many states but one lookup per symbol.

Common mistakes

• Forgetting the ε-closure at the start and after each transition.
• Treating "no transition" in an NFA as an error — it just means that path dies.
• In subset construction, forgetting the ∅ state (it becomes the dead state of the DFA).
• Marking a DFA set accepting only if all its states accept — one is enough.

Quick recap

• NFA: δ gives a set of states; accept if some path accepts; ε-moves allowed in ε-NFAs.
• Simulate with a set of current states (+ ε-closure).
• Subset construction: DFA states = sets of NFA states; at most 2ⁿ, usually far fewer.
• DFA = NFA = ε-NFA in power (regular languages); NFAs can be exponentially smaller.