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

Source: https://skills101.in/learn/theory-of-computation/nfa-to-dfa-subset-construction — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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:

![NFA for strings whose third symbol from the end is 1: q0 loops on 0 and 1 and on a 1 may also move to q1; then any symbol moves q1 to q2 and q2 to the accepting state q3](https://skills101.in/learn-img/theory-of-computation/nfa-third-last.svg)

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:

```python
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)
```

```text
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` (0**1**10) → 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).

```python
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"})))
```

```text
ε-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ⁿ).

![Subset construction: DFA states are sets of NFA states; starting from the set containing q0, each symbol leads to the union of the NFA moves, and any set containing the accepting state q2 becomes accepting](https://skills101.in/learn-img/theory-of-computation/subset-construction.svg)

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

| NFA state | a | b |
|---|---|---|
| → q0 | {q0, q1} | {q0} |
| q1 | ∅ | {q2} |
| * q2 | ∅ | ∅ |

```python
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)")
```

```text
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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/nfa-to-dfa-subset-construction