A nondeterministic finite automaton (NFA) can be in multiple states at once. It guesses which path to take, and accepts if any path reaches an accepting state. NFAs are not more powerful than DFAs: the subset construction converts any NFA to an equivalent DFA.
NFA: multiple paths at once
An NFA is the same 5-tuple as a DFA, except the transition function maps to sets of states: δ : Q × (Σ ∪ {ε}) → P(Q). At each step the machine can follow any transition, including ε-transitions that consume no input.
Simulating an NFA
Track all possible states simultaneously. The NFA accepts if the final set of states contains at least one accepting state.
Scheme
; NFA that accepts "ab" or "a" (epsilon from q0 to q2); States: q0=0, q1=1, q2=2, q3=3 (accept); q0 --a--> q1, q0 --eps--> q2; q1 --b--> q3, q2 --a--> q3
(define (epsilon-closure states)
; q0 has epsilon to q2
(if (member 0 states)
(if (member 2 states) states (cons 2 states))
states))
(define (nfa-step states symbol)
(define (transitions s)
(cond
((and (= s 0) (equal? symbol "a")) (list 1))
((and (= s 1) (equal? symbol "b")) (list 3))
((and (= s 2) (equal? symbol "a")) (list 3))
(else (list))))
(let ((next (apply append (map transitions states))))
(epsilon-closure next)))
(define (run-nfa input)
(define (step states i)
(if (= i (string-length input))
states
(step (nfa-step states (substring input i (+ i 1)))
(+ i 1))))
(let ((final (step (epsilon-closure (list 0)) 0)))
(not (null? (filter (lambda (s) (= s 3)) final)))))
(display "ab: ") (display (run-nfa "ab")) (newline)
(display "a: ") (display (run-nfa "a")) (newline)
(display "b: ") (display (run-nfa "b")) (newline)
(display "aa: ") (display (run-nfa "aa"))
Python
# NFA simulation: track all possible statesdef run_nfa(input_str):
def eps_closure(states):
s = set(states)
if0in s: s.add(2) # epsilon: q0 -> q2return s
transitions = {
(0, 'a'): {1}, (1, 'b'): {3}, (2, 'a'): {3},
}
states = eps_closure({0})
for ch in input_str:
next_states = set()
for s in states:
next_states |= transitions.get((s, ch), set())
states = eps_closure(next_states)
return3in states # q3 is acceptingfor s in ["ab", "a", "b", "aa"]:
print(s + ": " + str(run_nfa(s)))
Subset construction: NFA to DFA
Every NFA can be converted to a DFA. Each DFA state represents a set of NFA states. The number of DFA states can be exponential (up to 2n), but in practice most subsets are unreachable.
Scheme
; Subset construction: convert the NFA above to a DFA.; NFA states: 0,1,2,3. Accepting: 3.; Epsilon: 0 -> 2; DFA states are sets of NFA states.; Start: eps-closure(0) = (0,2); (0,2) --a--> eps-closure(1,3) = (1,3) [accept]; (0,2) --b--> eps-closure() = () [dead]; (1,3) --a--> eps-closure() = () [dead]; (1,3) --b--> eps-closure(3) = (3) [accept]; (3) --a--> () [dead], (3) --b--> () [dead]
(display "DFA states from subset construction:") (newline)
(display " start: (0,2)") (newline)
(display " (0,2) --a--> (1,3) [accept]") (newline)
(display " (0,2) --b--> dead") (newline)
(display " (1,3) --b--> (3) [accept]") (newline)
(display " (1,3) --a--> dead") (newline)
(display " (3) is a sink (no outgoing to live states)") (newline)
(newline)
(display "The NFA had 4 states.") (newline)
(display "The DFA has 4 reachable states (including dead).")
Python
# Subset construction: NFA to DFA (same NFA as above)# NFA: 0 --a--> 1, 0 --eps--> 2, 1 --b--> 3, 2 --a--> 3def eps_closure(states):
s = frozenset(states) | ({2} if0in states elseset())
return s
nfa_delta = {(0, 'a'): {1}, (1, 'b'): {3}, (2, 'a'): {3}}
accepting = {3}
start = eps_closure({0})
worklist = [start]
dfa_states = {}
while worklist:
state_set = worklist.pop()
for symbol in ['a', 'b']:
next_nfa = set()
for s in state_set:
next_nfa |= nfa_delta.get((s, symbol), set())
next_set = eps_closure(next_nfa)
dfa_states[(state_set, symbol)] = next_set
if next_set notin [v for v in dfa_states.values()] and next_set notin worklist:
worklist.append(next_set)
print("DFA transitions:")
for (src, sym), dst insorted(dfa_states.items(), key=lambda x: str(x)):
is_acc = " [accept]"if dst & accepting else""print(f" {set(src)} --{sym}--> {set(dst)}{is_acc}")
NFA = DFA in power
The subset construction proves that NFAs and DFAs recognize the same class of languages: the regular languages. Nondeterminism is a convenience for design, not an increase in power. The trade-off is state count: the DFA may need exponentially more states.
Neighbors
🤖 ML Ch.10 — sequence models: RNNs are nondeterministic automata trained by gradient descent