Nondeterministic finite automata (NFA)

Intermediate

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:

  1. Start with the set {q0}, plus everything reachable by ε-moves (its ε-closure).
  2. For each symbol c, collect every state reachable from the current set on c, then take the ε-closure again.
  3. 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"})))
Open in compiler

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)
Open in compiler

Line by line

  1. State 0 loops on every symbol, and on a it may also move to 1: that is the guess "this a is the third from the end".
  2. States 1, 2 and 3 count the two symbols that follow; 3 is accepting.
  3. run keeps the set of all states the NFA could be in, and trail records that set after each symbol.
  4. For abb, the set ends as {0, 3}, which contains 3, so it accepts. For bab it ends as {0, 2}, so it rejects: its third symbol from the end is b.
  5. 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

1. When does an NFA accept a string?
2. What is the ε-closure of a set of states?
3. After reading a prefix, an NFA's set of possible states is empty. What happens?
4. Which languages can NFAs recognise that DFAs cannot?

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.