Introduction
A DFA has exactly one move for each state and symbol. A nondeterministic finite automaton (NFA) relaxes that rule: a state may have several moves for the same symbol, no move at all, or ε-moves that change state without reading anything.
How can a machine "choose"? Think of it as guessing, or as running every possible choice in parallel. An NFA accepts a string if at least one way of reading it ends in an accepting state. This makes many machines far easier to design. "The third symbol from the end is a" needs eight states as a DFA, but only four as an NFA: the NFA simply guesses when the third-to-last symbol arrives.
How it works
An NFA is (Q, Σ, δ, q0, F), like a DFA, except that δ(q, a) is a set of states, which may be empty. With ε-moves, δ(q, ε) is also allowed.
To simulate an NFA without guessing, track every state it could be in:
- Start with the set {q0}, plus everything reachable by ε-moves (its ε-closure).
- For each symbol c, collect every state reachable from the current set on c, then take the ε-closure again.
- At the end, accept if the set contains any accepting state.
If the set ever becomes empty, every path has died, and the string is rejected.
The ε-closure is a small graph search: start from the given states and keep following ε-moves until nothing new appears.
eps = {"p": {"q"}, "q": {"r"}, "r": set(), "s": {"p"}}
def closure(states):
seen = set(states)
stack = list(states)
while stack:
s = stack.pop()
for t in eps[s]:
if t not in seen:
seen.add(t)
stack.append(t)
return seen
print("closure of {p}:", sorted(closure({"p"})))
print("closure of {s}:", sorted(closure({"s"})))A path that gets stuck (no move for a symbol) simply stops counting; it does not make the whole machine reject, as long as another path is still alive. That is the difference from an incomplete DFA.
Syntax
delta = {(0, "a"): {0, 1}, (0, "b"): {0}, ...} # δ gives a set
current = {start}
for c in word:
current = set().union(*(delta.get((q, c), set()) for q in current))
accepted = bool(current & accept) # some state accepts
Example
delta = {
(0, "a"): {0, 1}, (0, "b"): {0},
(1, "a"): {2}, (1, "b"): {2},
(2, "a"): {3}, (2, "b"): {3},
}
start, accept = 0, {3}
def run(word):
current = {start}
trail = [sorted(current)]
for c in word:
current = set().union(*(delta.get((q, c), set()) for q in current))
trail.append(sorted(current))
return bool(current & accept), trail
for w in ["abb", "bab", "aaba"]:
ok, trail = run(w)
print(w, "accept" if ok else "reject", trail)Line by line
- State 0 loops on every symbol, and on
ait may also move to 1: that is the guess "this a is the third from the end". - States 1, 2 and 3 count the two symbols that follow; 3 is accepting.
runkeeps the set of all states the NFA could be in, andtrailrecords that set after each symbol.- For
abb, the set ends as {0, 3}, which contains 3, so it accepts. Forbabit ends as {0, 2}, so it rejects: its third symbol from the end is b. set().union(...)combines the moves of every current state, and a missing move contributes nothing.
Expected result
abb accept [[0], [0, 1], [0, 2], [0, 3]]
bab reject [[0], [0], [0, 1], [0, 2]]
aaba accept [[0], [0, 1], [0, 1, 2], [0, 2, 3], [0, 1, 3]]
In the real world
Regular-expression engines such as those in grep and many editors run patterns as NFAs, keeping a set of states and so never needing exponential time. Network intrusion detection systems match thousands of patterns at once with NFAs. Designers often sketch a protocol or a lexer as an NFA first, because it is easier to get right, and convert it later.
Common mistakes
- Rejecting as soon as one path gets stuck: only reject if every path fails.
- Forgetting the ε-closure, at the start or after a move.
- Treating an NFA as more powerful than a DFA: it is more convenient, but recognises exactly the same languages.
- Changing the set while looping over it; build the next set separately.
Best practices
- Represent δ as a dictionary from (state, symbol) to a set, and use
.get(..., set())for missing moves. - Write the ε-closure once as a function and call it everywhere.
- Print the set of states after each symbol when debugging; it shows every live path at once.
Summary
An NFA may have many moves, no move, or ε-moves for a state, and accepts if some path accepts. Simulating it means tracking the set of possible states, with ε-closures after each step. NFAs are easier to design and often much smaller than equivalent DFAs, yet they recognise exactly the same languages.
Quick check
Key takeaways
- An NFA accepts when at least one way of reading the input ends in an accepting state.
- Simulating an NFA means tracking the set of all states it could be in.
- NFAs are often much smaller and easier to design than DFAs for the same language.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.