Finite automata and nondeterminism

The simplest machine worth studying has no memory except its current state. It reads its input once, from left to right, one symbol at a time, and at each step moves to a new state determined only by its current state and the symbol it has just read. When the input ends, it accepts or rejects according to the state it is in. This is a finite automaton. Despite the extreme limitation, finite automata are everywhere: in the lexical analyzers of compilers, in network packet filters, in text search tools such as grep, in hardware controllers, in protocol specifications and in the input validators of web forms. This lesson defines them precisely, shows how to design them, introduces nondeterminism and proves that nondeterminism adds convenience but not power.

Deterministic finite automata

A deterministic finite automaton (DFA) is a 5-tuple \(M = (Q, \Sigma, \delta, q_0, F)\), where Q is a finite set of states, \(\Sigma\) is the input alphabet, \(\delta : Q \times \Sigma \to Q\) is the transition function, \(q_0 \in Q\) is the start state and \(F \subseteq Q\) is the set of accepting states. The word deterministic refers to \(\delta\) being a function: from each state, each symbol leads to exactly one next state. To describe what M does on a whole string we extend \(\delta\) to strings by induction: \(\hat\delta(q, \varepsilon) = q\) and \(\hat\delta(q, wa) = \delta(\hat\delta(q, w), a)\). M accepts w if \(\hat\delta(q_0, w) \in F\), and the language of M is \(L(M) = \{w : \hat\delta(q_0, w) \in F\}\). A language is regular if some DFA recognizes it.

Two things in that definition deserve attention. First, \(\delta\) must be total: every state needs a transition on every symbol. In diagrams we often omit transitions to a dead state, a non-accepting state that loops to itself on every symbol, but it is still part of the machine. Second, a DFA always halts after exactly \(|w|\) steps, so it decides its language; there is no looping and no distinction between recognizing and deciding. Running a DFA takes linear time and constant memory, which is why automata are the workhorse of fast text processing.

The figure shows a classic DFA. It reads a binary number from the most significant bit and accepts if the number is divisible by 3. The key design insight is to ask what the machine must remember. It does not need the whole number, only the number modulo 3, because appending a bit b to a number v gives \(2v + b\), and \((2v + b) \bmod 3\) depends only on \(v \bmod 3\). So three states suffice, one per remainder, with \(\delta(q_r, b) = q_{(2r + b) \bmod 3}\). The program below builds exactly this machine, traces several inputs, and checks it against ordinary arithmetic on every binary string up to length 12.

# A DFA for binary numbers divisible by 3. States remember the value read so far, mod 3.
# Reading bit b from state r moves to (2r + b) mod 3, because appending b doubles the value and adds b.
DELTA = {(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"}
START, ACCEPT = 0, {0}

def run(w):
    q, trace = START, [START]
    for c in w:
        q = DELTA[(q, c)]
        trace.append(q)
    return q in ACCEPT, trace

for r in range(3):
    print(f"delta(q{r}, 0) = q{DELTA[(r, '0')]}   delta(q{r}, 1) = q{DELTA[(r, '1')]}")
for w in ["0", "11", "110", "1001", "10101", "111111", "1000000"]:
    ok, trace = run(w)
    print(f"{w:>8} = {int(w, 2):3d}  states {' '.join('q%d' % s for s in trace):28s} {'accept' if ok else 'reject'}")
# exhaustive check against arithmetic for every string up to length 12
from itertools import product
bad = sum(run("".join(t))[0] != (int("".join(t), 2) % 3 == 0)
          for n in range(1, 13) for t in product("01", repeat=n))
print("mismatches on all 8190 strings of length 1..12:", bad)

delta(q0, 0) = q0   delta(q0, 1) = q1
delta(q1, 0) = q2   delta(q1, 1) = q0
delta(q2, 0) = q1   delta(q2, 1) = q2
       0 =   0  states q0 q0                        accept
      11 =   3  states q0 q1 q0                     accept
     110 =   6  states q0 q1 q0 q0                  accept
    1001 =   9  states q0 q1 q2 q1 q0               accept
   10101 =  21  states q0 q1 q2 q2 q1 q0            accept
  111111 =  63  states q0 q1 q0 q1 q0 q1 q0         accept
 1000000 =  64  states q0 q1 q2 q1 q2 q1 q2 q1      reject
mismatches on all 8190 strings of length 1..12: 0

Designing automata

Designing a DFA is mostly a matter of deciding what finite information about the prefix read so far determines the answer for every possible continuation. For 'contains the substring 101' the machine must remember how much of 101 it has matched at the end of the prefix: nothing, 1, or 10, plus a fourth state for 'already seen 101', which is accepting and absorbing. For 'the number of 0s is even and the number of 1s is odd' it must remember two parities, giving four states. For 'the last symbol is 1' it must remember only the last symbol. If the answer depends on an unbounded quantity, such as the difference between the number of as and bs read so far, no finite set of states can remember it, and the language is not regular. Lesson 4 turns that intuition into proofs.

Automata are often designed for formats. Input validation is a natural example: a form field accepts a string only if it has the right shape. The program below implements a DFA as a table-driven loop for a postal code format. Each state counts how many characters have matched so far, and any wrong character sends the machine to a dead state. Real validation would add more rules, such as letters that are never used, but each such rule can be handled by more states or by intersecting with another regular language, which lesson 3 shows is always possible.

# A DFA, written as a table, for US ZIP codes: five digits, optionally followed by
# a hyphen and four more digits (ZIP+4), such as 80202 or 80202-1234.
# State i counts correct characters; 5 and 10 are accepting.
def accepts(w):
    q = 0                                   # states 0..10 plus a dead state "dead"
    for c in w:
        if q == "dead":
            break
        if q in (0, 1, 2, 3, 4) or q in (6, 7, 8, 9):
            q = q + 1 if c.isdigit() else "dead"
        elif q == 5:
            q = 6 if c == "-" else "dead"
        else:                               # q == 10: nothing may follow
            q = "dead"
    return q in (5, 10)

for w in ["80202", "80202-1234", "8020", "80202-123", "80202-12345", "8O202", "80202 1234"]:
    print(f"{w!r:14} {'accept' if accepts(w) else 'reject'}")
print("states used: 12 (states 0..10 plus a dead state; 5 and 10 accept)")

'80202'        accept
'80202-1234'   accept
'8020'         reject
'80202-123'    reject
'80202-12345'  reject
'8O202'        reject
'80202 1234'   reject
states used: 12 (states 0..10 plus a dead state; 5 and 10 accept)

Nondeterministic finite automata

A nondeterministic finite automaton (NFA) relaxes the requirement that each state and symbol determine a unique next state. Formally an NFA is \(N = (Q, \Sigma, \delta, q_0, F)\) with \(\delta : Q \times \Sigma_\varepsilon \to \mathcal{P}(Q)\), where \(\Sigma_\varepsilon = \Sigma \cup \{\varepsilon\}\). From a state, a symbol may lead to several states, to one, or to none, and \(\varepsilon\)-transitions let the machine change state without reading anything. N accepts w if some sequence of choices consumes w and ends in an accepting state. Rejection requires that every possible path either gets stuck or ends in a non-accepting state.

There are two useful ways to picture nondeterminism. In the guessing view, the machine guesses the right choice at each step, and it accepts if any guess succeeds. In the parallel view, the machine follows all choices at once, keeping track of the set of states it could be in; it accepts if that set contains an accepting state when the input ends. The second view is the one an implementation uses, and it is also the idea behind the proof that NFAs are no more powerful than DFAs. Nondeterminism is not a physical capability; it is a descriptive device that often makes machines much smaller and much easier to design.

The figure shows an NFA for \(L_3\), the binary strings whose third symbol from the end is 1. The start state loops on every symbol, and on reading a 1 it may also guess that this 1 is the third symbol from the end and move along a chain of three more states. The guess is right exactly when the input ends as the chain reaches the accepting state. Generalizing, \(L_n\) has an NFA with \(n + 1\) states. A DFA for \(L_n\) is much harder to write by hand: it must remember the last n symbols read, because any of them might turn out to be the n-th from the end.

Equivalence of NFAs and DFAs

Theorem (Rabin and Scott, 1959). For every NFA N there is a DFA M with \(L(M) = L(N)\). The proof is the subset construction, which CMPUT-415 used to build scanners; here we state it precisely and say why it is correct. First handle \(\varepsilon\)-moves: for a set of states S, let \(E(S)\) be its \(\varepsilon\)-closure, the states reachable from S using only \(\varepsilon\)-transitions. Define M with state set \(\mathcal{P}(Q)\), start state \(E(\{q_0\})\), transition \(\delta_M(S, a) = E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)\), and accepting states all sets that contain at least one state of F.

Correctness is an induction on the length of the input. The claim is that \(\hat\delta_M(E(\{q_0\}), w)\) is exactly the set of states N can be in after reading w. For \(w = \varepsilon\) that set is \(E(\{q_0\})\) by definition. If the claim holds for w, then after reading one more symbol a, the states N can reach are those reachable from the current set by an a-transition followed by \(\varepsilon\)-moves, which is exactly \(\delta_M\) applied to the current set. So M tracks N's possible states perfectly, and M accepts w if and only if one of N's possible states at the end is accepting, which is the definition of N accepting w.

The construction can create up to \(2^{|Q|}\) states, and in practice one builds only the subsets reachable from the start. Is the exponential worst case real? Yes. The program below applies the construction to the NFA for \(L_n\) and finds exactly \(2^n\) reachable subsets for every n tested. That count is not an accident of the construction. Any DFA for \(L_n\) needs at least \(2^n\) states, because any two distinct strings x and y of length n differ in some position, say position i from the end; appending \(n - i\) arbitrary symbols puts that position exactly n from the end, so one extension is in \(L_n\) and the other is not. A DFA that confused x and y by ending in the same state would give both extensions the same answer. With \(2^n\) pairwise distinguishable strings, the DFA needs \(2^n\) states. Lesson 4 turns this idea into the Myhill–Nerode theorem.

# L_n = binary strings whose n-th symbol from the end is 1.
# An NFA with n + 1 states guesses where that 1 is. The subset construction
# (CMPUT-415 lesson 2) produces a DFA; count its reachable states.
def nfa(n):
    # states 0..n; 0 loops on 0/1 and on 1 may also move to 1; i -> i+1 on 0/1; n accepts
    d = {}
    for c in "01":
        d[(0, c)] = {0, 1} if c == "1" else {0}
        for i in range(1, n):
            d[(i, c)] = {i + 1}
        d[(n, c)] = set()
    return d

def subset_construction(n):
    d = nfa(n)
    start = frozenset({0})
    seen, todo = {start}, [start]
    while todo:
        S = todo.pop()
        for c in "01":
            T = frozenset(q for s in S for q in d[(s, c)])
            if T not in seen:
                seen.add(T); todo.append(T)
    return seen

for n in range(1, 11):
    states = subset_construction(n)
    print(f"n = {n:2d}: NFA states {n + 1:2d}, reachable DFA states {len(states):5d} = 2^{n}: {len(states) == 2 ** n}")

n =  1: NFA states  2, reachable DFA states     2 = 2^1: True
n =  2: NFA states  3, reachable DFA states     4 = 2^2: True
n =  3: NFA states  4, reachable DFA states     8 = 2^3: True
n =  4: NFA states  5, reachable DFA states    16 = 2^4: True
n =  5: NFA states  6, reachable DFA states    32 = 2^5: True
n =  6: NFA states  7, reachable DFA states    64 = 2^6: True
n =  7: NFA states  8, reachable DFA states   128 = 2^7: True
n =  8: NFA states  9, reachable DFA states   256 = 2^8: True
n =  9: NFA states 10, reachable DFA states   512 = 2^9: True
n = 10: NFA states 11, reachable DFA states  1024 = 2^10: True

What equivalence buys us

Because NFAs and DFAs recognize the same class of languages, we can use whichever is more convenient in each situation. Proofs of closure properties often build an NFA, because nondeterminism lets a machine guess where one part of the input ends and the next begins. Implementations often prefer DFAs, because their running time per symbol is constant, or simulate NFAs directly with the set-of-states method when the DFA would be too large; this is the trade-off made by regular expression engines that guarantee linear-time matching, such as RE2 and Rust's regex crate. One operation does not transfer for free: complementation. Swapping accepting and non-accepting states complements a DFA, but in an NFA it gives the language of strings with some rejecting run, which is not the complement. To complement an NFA, convert it to a DFA first.

The equivalence also shows something conceptual. Nondeterminism does not change the power of finite automata. We will see that it does change the power of pushdown automata, whose deterministic version recognizes strictly fewer languages, and that whether it changes the power of time-bounded Turing machines is exactly the P versus NP question. Finite automata are the one level at which the question has a simple, completely understood answer, and the price of removing nondeterminism, an exponential increase in states in the worst case, is known exactly.

Worked examples