Running an NFA
The same language, one arrow too many — watch the machine track every possibility at once.
Skip to the animationA nondeterministic finite automaton may have several arrows out of a state on the same symbol, or none — and it accepts a string if *some* path through it ends in an accepting state.
What nondeterminism actually means
It does not mean random. It means the machine is defined by an existential claim: the string is accepted if there exists an accepting path. Nothing says how to find that path, which is exactly what makes an NFA easy to write down and impossible to run directly.
The machine below has two arrows leaving n0 on a — stay in n0, or move to n1. There is no rule for choosing, and no lookahead. The textbook image is that the machine "guesses" correctly; the honest one is that it explores every option at once.
The animation takes the second view, because it is the one you can implement. The highlighted set is every state the machine could be in right now.
The vocabulary
- Alphabet (Σ)
- The finite set of symbols the machine may read. For everything on this page,
Σ = {a, b}. - String and language
- A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.
- State
- The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.
- Transition function (δ)
- Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.
- Accepting state
- Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.
- Trap or dead state
- A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.
Simulating it honestly
- 1Start with the set containing the start state, plus anything reachable from it on ε-moves.
- 2For each symbol, replace the set with everything reachable from any member of it on that symbol.
- 3Take the ε-closure of the result.
- 4If the set is ever empty, every path has died and the string is rejected.
- 5At the end, accept if the set contains any accepting state.
That set never exceeds the number of states, so simulation costs O(n × |Q|) — polynomial, not exponential. Tracking a *set* of states rather than a *tree* of paths is what avoids the blow-up, and it is the same insight the subset construction turns into a compile-time transformation.
Why write an NFA at all
| DFA | NFA | |
|---|---|---|
| Arrows per state per symbol | exactly one | zero or more |
| ε-moves | not allowed | allowed |
| Accepts when | the single path ends accepting | some path ends accepting |
| States for a given language | sometimes exponentially more | usually far fewer |
| Directly executable | yes | no — needs a set simulation |
NFAs are strictly easier to build, and no more powerful. Converting a regular expression to an NFA is mechanical and produces a machine with about as many states as the expression has symbols; converting it straight to a DFA is not something you would do by hand. So the standard pipeline is regex → NFA → DFA, and the middle step exists purely for human convenience.
Advantages and disadvantages
Advantages
- Far smaller and easier to design than the equivalent DFA.
- Regular expressions convert to NFAs mechanically, with ε-moves gluing the pieces together.
- No more powerful than a DFA, so nothing is lost by using one.
Disadvantages
- Cannot be executed directly — you must track a set of states or backtrack.
- Simulation costs more per symbol than a DFA's single table lookup.
- The equivalent DFA can be exponentially larger in the worst case.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.