2.2 NFA, Subset Construction and Minimization: From Multiple Possible Paths to a Single State

The gatekeeper of the compiler tower faces the same character and sees multiple outgoing edges. The head curator asks Ah Hua to record all possible states at once.

The curator draws two edges labeled a on the same circle and adds a dashed edge that doesn't consume a character. Suddenly, the gatekeeper seems capable of "guessing" its path. Non-determinism is not magic computation; it's the act of preserving a set of possible paths. As long as one of those paths leads to an accepting state, the input is accepted.

Learning Objectives

• Explain the acceptance semantics of NFA with ε-transitions;
• Correctly compute the ε-closure of a set of states;
• Use the subset construction method to convert an NFA into an equivalent DFA;
• Understand state explosion, on-demand determinization, and DFA minimization.

1. NFA Transition Returns a Set of States

A nondeterministic finite automaton (NFA) with ε-transitions can be written as:

$$ N = (Q, \Sigma, \delta, q_0, F), $$

where:

$$ \delta: Q \times (\Sigma \cup {\varepsilon}) \to \mathcal{P}(Q). $$

Given a state and an input symbol, the transition may result in zero, one, or multiple states. An NFA accepts a string if there exists a path that consumes the entire input and ends in an accepting state.

An NFA is not simply "randomly picking a path." If implementation blindly selects one branch, it might miss an accepting path. During simulation, the current set of reachable states should be maintained, or the NFA should first be determinized into a DFA.

2. Empty closures cannot be overlooked

The ε-closure(S) is the set of all states reachable from a state set S via zero or more ε-transitions, including S itself.

The process for handling an input symbol $a$ consists of:

1. Compute the ε-closure of the current state set;
2. Follow all edges labeled $a$;
3. Compute the ε-closure of the resulting state set.

If the ε-closure is computed only at the initial state, transitions that emerge after reading a character (due to newly activated ε-edges) will be missed.

3. An NFA that recognizes ab or ac

q0 --a--> q1
q1 --b--> q2  (accept)
q1 --c--> q3  (accept)

This example has no ε-transitions, but q1 offers different choices for different characters. When constructing the expression ab|ac using Thompson's method, new start states, branches, and merge points are typically created, connected by ε-transitions.

A more expressive example of non-determinism is "the second-to-last character is a":

q0 --a/b--> q0
q0 --a--> q1
q1 --a/b--> q2  (accept)

Whenever an a is encountered, the NFA can either stay in q0 or guess that it is the second-to-last character and transition into q1. The string is accepted if at least one such guess leads to q2 at the end of input.

4. Subset Construction Method

A state in the equivalent DFA represents a set of possible states in the NFA. The algorithm proceeds as follows:

1. The initial state of the DFA is ε-closure({q₀});
2. For each unprocessed state set S and each symbol a ∈ Σ, compute ε-closure(move(S, a));
3. Each newly generated set becomes a state in the DFA;
4. If a set contains any accepting state of the NFA, it is an accepting state in the DFA;
5. Repeat until no new states are generated.

from collections import deque
from collections.abc import Mapping, Set

State = str

def epsilon_closure(
    states: Set[State], epsilon_edges: Mapping[State, Set[State]]
) -> frozenset[State]:
    closure = set(states)
    pending = list(states)
    while pending:
        state = pending.pop()
        for target in epsilon_edges.get(state, set()):
            if target not in closure:
                closure.add(target)
                pending.append(target)
    return frozenset(closure)

def determinize(start, alphabet, edges, epsilon_edges):
    dfa_start = epsilon_closure({start}, epsilon_edges)
    pending = deque([dfa_start])
    seen = {dfa_start}
    transitions = {}

    while pending:
        current = pending.popleft()
        transitions[current] = {}
        for symbol in alphabet:
            moved = {
                target
                for state in current
                for target in edges.get((state, symbol), set())
            }
            target = epsilon_closure(moved, epsilon_edges)
            transitions[current][symbol] = target
            if target not in seen:
                seen.add(target)
                pending.append(target)
    return dfa_start, transitions

The empty set is also a valid DFA state, typically corresponding to a trap state. If omitted, the result is only a partial transition table that must be supplemented by the executor with failure semantics.

5. Expressive Power Is the Same, but Representation Sizes Differ

NFA and DFA describe the same class of languages: regular languages. A DFA is a special case of an NFA; any NFA can be transformed via subset construction into an equivalent DFA.

If an NFA has $n$ states, subset construction theoretically generates up to $2^n$ states. Some languages indeed require exponentially large DFAs. However, many practical NFAs have only a small number of reachable subsets. In practice, implementations typically only construct states that are reachable from the initial state.

Optional strategies include:

• Preconstructing the full DFA, with a transition for each input character during runtime;
• Directly simulating the NFA's state set;
• On-demand construction and caching of DFA states;
• Compressing the transition table at the cost of additional lookup overhead.

Thus, the notion that "NFA is for humans to write, DFA is for machines to run" is merely a beginner's slogan, not a general engineering truth. Thompson NFA simulation, for instance, can be executed directly and provides predictable time bounds.

6. What DFA Minimization Solves

After determinization, some states may behave equivalently. DFA minimization merges states that cannot be distinguished by any suffix.

The classic partition refinement begins with two groups:

Accepting states | Non-accepting states

If two states in the same group transition to different groups upon reading a character, the group must be split. This process continues iteratively until the groups stabilize. The Hopcroft algorithm efficiently performs this refinement.

The minimal DFA is unique up to state renaming. Before minimizing, it's common to remove states unreachable from the start state, since such states do not affect the language and would otherwise contaminate the result.

7. Equivalence Verification

To determine whether two deterministic finite automata (DFA) recognize the same language, construct the product automaton and search for a state pair where exactly one side accepts and the other rejects. If such a distinguishable state pair is reachable, a counterexample string can be derived; if no such pair is reachable, the two DFAs are equivalent.

This approach is stronger than random string testing. Random testing can only uncover certain differences, while the equivalence algorithm provides a complete and definitive determination.

Common Misconceptions

• NFA randomly chooses paths at runtime: The correct semantics is that at least one accepting path exists; the implementation must retain all relevant possibilities.
• Subset construction generates all states in the power set: It's sufficient to generate only those subsets reachable from the start state.
• NFA is always smaller than DFA: It may be smaller, or it may be comparable in size; the outcome depends on the specific language and representation.
• Fewer DFA states always mean faster scanners: Actual performance also depends on cache layout, character classification, and table compression.

Exercise

1. List the reachable DFA states constructed from the subset construction for the language where the second-to-last character is a.
2. Manually compute the ε-closure for each state in an NFA containing ε-loops.
3. Modify the deterministic finite automaton code to return the set of accepting states, and write a test for ab|ac.
4. Construct two equivalent DFAs with different numbers of states, and manually perform state partition refinement.

Summary

NFA expresses multiple possible paths using a set of states, and subset construction transforms that set into a single state of a DFA. Both models have equivalent expressive power, with the main trade-offs lying in construction size, runtime cost, and memory usage. Minimization further merges states that behave identically for all future inputs.

The next lesson begins by constructing an NFA from a regular expression, while disentangling three commonly conflated concepts: classic regular languages, actual regex dialects, and specific matching engines.