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

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,\mathrm{\Sigma },\delta ,q_0,F),$$

where:

$$\delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\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 and at most one target for each state-symbol pair. It is already deterministic; adding a trap state completes a DFA. Different inputs taking different edges is not nondeterminism. 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, accepting):
    alphabet = tuple(dict.fromkeys(alphabet))
    accepting = frozenset(accepting)
    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)
    dfa_accepting = {states for states in seen if states & accepting}
    return dfa_start, transitions, dfa_accepting

Materializing the finite alphabet prevents a generator from being exhausted after processing the first DFA state. The mappings must describe a finite NFA with hashable states and symbols. This Python 3.9+ example includes an epsilon cycle and acceptance reachable only by an epsilon edge after reading b or c:

edges = {
    ("q0", "a"): {"q1"},
    ("q1", "b"): {"q2"},
    ("q1", "c"): {"q3"},
}
epsilon_edges = {
    "start": {"q0"},
    "q0": {"start"},
    "q2": {"done"},
    "q3": {"done"},
}
start, table, accepting = determinize(
    "start", iter("abc"), edges, epsilon_edges, {"done"}
)

def accepts(text):
    state = start
    for symbol in text:
        if symbol not in table[state]:
            raise ValueError(f"outside alphabet: {symbol!r}")
        state = table[state][symbol]
    return state in accepting

for text in ("", "a", "ab", "ac", "abc", "b", "aab"):
    assert accepts(text) == (text in {"ab", "ac"})
assert epsilon_closure({"start"}, epsilon_edges) == {"start", "q0"}
print(len(table), len(accepting))

Expect 5 2: five reachable subsets, two accepting. The visited set prevents the epsilon cycle from looping forever.

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.

Partition refinement starts with accepting and nonaccepting groups, omitting either group if it is empty:

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.

For a fixed alphabet and language, the complete, reachable 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, first align their alphabets and add trap-state transitions where needed. Then 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: Only subsets reachable from the start are needed. There is no need to reserve seats for states that will never arrive.
• 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. Write a direct NFA simulator and compare its results with the determinized ab|ac automaton. Add a case where the empty string should be accepted.
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.