NFAs from First Principles: Interactive
Nondeterministic finite automata: what they are, how ε‑moves work, and why they recognize the same languages as DFAs. Includes a runner, a small builder with ε, and a determinize table.
Hover here to see links to related content.
From Words to Machines
Pick an alphabet $\Sigma$ (e.g., $\{a,b\}$). Words are finite strings over $\Sigma$; the set of all words is $\Sigma^*$ and includes the empty word $\varepsilon$. An NFA is a five‑tuple $(Q,\Sigma,\delta,q_0,F)$ like a DFA, except $\delta(q,a)$ returns a set of possible next states, and we may also allow $\varepsilon$ moves that consume no input.
The extended transition to sets and whole words is $$\hat{\delta}(S,\varepsilon)=\varepsilon\text{-closure}(S),\qquad \hat{\delta}(S,aw)=\hat{\delta}(\,\varepsilon\text{-closure}(\bigcup_{q\in S}\delta(q,a)),\,w\,).$$ A word $w$ is accepted when $\hat{\delta}(\{q_0\},w)$ intersects $F$. In plain words: keep all states you could be in, expand along $\varepsilon$ moves for free, then follow the next symbol from all of them at once.
Run Preset NFAs
Pick a simple pattern and watch the NFA process the input. Nondeterminism means “try all possible next steps at once”; accept if at least one path lands in an accepting state after the last symbol.
…
…
Build an NFA (with ε)
Place states, pick a start, toggle accepting, and add transitions. Use 'ε' (or 'e') to add $\varepsilon$ moves. Enter input and step; the highlighted set shows “all places the machine might be now”. Click “Determinize” to see the subset construction table.
…
First principles recap: $\varepsilon$‑closure collects all states you can reach for free. Each input step follows transitions from the whole set, then re‑closes under $\varepsilon$. The determinized DFA has subsets as states; start at $\varepsilon$‑closure($\{q_0\}$) and follow symbols; accept subsets that contain any accepting NFA state.
- Compare with DFAs: Turing Machines & Automata (DFA parity & builder).
- Determinized DFA mirrors subset products from linear algebra (see Toolkit: Linear maps).