From Words to Machines

Here is an idea that should stop you in your tracks: what if a machine could be in multiple states at the same time? Not broken, not confused, but genuinely exploring every possible path through a computation simultaneously. That is exactly what a nondeterministic finite automaton does. Think of it like navigating a maze by cloning yourself at every fork. Each clone walks a different corridor. If any single clone reaches the exit, you win.

The formal setup starts simply. Pick an alphabet $\Sigma$ (e.g., $\{a,b\}$). Words are finite strings over $\Sigma$; the set of all words is $\Sigma^*$, which includes the empty word $\varepsilon$. An NFA is a five-tuple $(Q,\Sigma,\delta,q_0,F)$, just like a DFA, except for one crucial difference: $\delta(q,a)$ returns a set of possible next states rather than a single one. We may also allow $\varepsilon$-moves, which let the machine jump between states without consuming any input at all.

How does the machine process an entire word? The following formula says: first, collect all the states reachable via free $\varepsilon$-moves. Then, for each symbol, follow every possible transition from every current state and close under $\varepsilon$ again. $$\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: if even one of your clones ends up in an accepting state, the whole string is accepted. The machine is an optimist; it only needs one successful path.

Try It Yourself: Run Preset NFAs

Pick a pattern from the dropdown, type an input string, and step through it. Watch how the set of active states splits and merges as the machine explores every possibility in parallel. Remember: the string is accepted if even one path ends in an accepting state. Try different inputs and see what gets through.