Regular Expressions and Automata

Regular expressions describe a set of strings, and finite automata determine whether an input belongs to that set. Lexical analyzers must additionally answer: starting from the current position, how long should we capture, and which token type does it belong to? Understanding the distinction between these three problems is essential for applying automata theory to real-world lexers.

Regular Languages: Remembering a Finite Number of Cases

Concatenation (ab), alternation (a|b), repetition (a*), along with the empty string and the empty language, constitute the basic operations of classic regular expressions. Character classes and operators like + and ? are typically convenient syntactic sugar. For example, [0-9]+ represents one or more decimal digits.

The "finite" in finite automata refers to a fixed number of states that does not grow with the input. It can remember whether a decimal point has appeared in the current number or whether the string ends with a specific fixed suffix; generally, it cannot remember arbitrarily deep bracket nesting with a fixed number of states. Language rules such as nested comments can be handled by lexers using additional counters, but this goes beyond pure finite automata.

The syntax of modern regex libraries is not exactly equivalent to classic regular languages. Capture groups record match positions but do not themselves push the language beyond the regular class; backreferences require re-matching arbitrary-length content previously matched, which may describe non-regular languages. RE2 supports capture groups but does not support backreferences. RE2 Syntax

NFA: Preserving All Still-Possible Paths in Parallel

An NFA allows a single state to transition to multiple states on the same character, and also allows ε-transitions that do not consume input. An input is accepted if there exists at least one accepting path; it is not required that all paths succeed.

Thompson's construction transforms each sub-expression of a regular expression into a fragment with an entry and exit, then composes these fragments: concatenation connects the exit of the previous fragment to the entry of the next; alternation adds ε-branches and merges; the Kleene star adds paths to "skip the entire fragment" and to "return from the exit to the entry for repetition." A graph without back-edges can only represent optional occurrences, not arbitrary repetitions.

For the expanded basic regular expression, the number of constructed states is proportional to the size of the expression. This conclusion discusses the size of the automaton and cannot be used directly to compare the matching time of backtracking engines.

NFA simulation maintains a set of active states, updating the set for each character read and filling in states reachable via ε. Deduplicating states in each round avoids repeatedly exploring the same "state, input position" combinations. Let the NFA have $m$ states and the input length be $n$; the time complexity of simple Thompson simulation is $O(mn)$, with active set space complexity $O(m)$. For fixed patterns, this is often referred to as linear in the input size. Russ Cox: NFA Simulation

DFA: Treating a Set of NFA States as a Single State

A DFA has exactly one next state for each state and input symbol. Subset construction pre-encodes "which NFA states might we be in" into a DFA state.

In the diagram, after reading ab, the set contains q2, so it accepts; if we continue reading a, we return to set B, and the current entire string no longer ends with ab. The state represents the information that must be remembered after reading the entire current prefix.

The steps of subset construction are:

1. The initial set is ε-closure({start}), where the closure includes the set itself.
2. For a set S and character c, compute T = ε-closure(move(S, c)).
3. If T has no number yet, assign a new state and add it to the work queue; record the transition from S on c to T.
4. Until no new sets remain. Sets containing any NFA accepting state are marked as accepting.

The empty set can be represented as an explicit dead state or by missing transitions. Practical implementations often handle character equivalence classes or ranges, without enumerating all Unicode code points.

If the NFA has $m$ states, there can be up to $2^m$ potential subsets; generating only reachable subsets can still result in exponential growth. There is no guarantee that the NFA and DFA state counts are similar for real-world lexical rules.

An intuitive example is (0|1)*1(0|1){k-1}: it requires the $k$-th-to-last character to be 1. The NFA can guess which 1 is the target, while the DFA needs to distinguish combinations of the most recent $k$ bits; different $k$-bit suffixes can be distinguished by subsequent input, requiring at least $2^k$ states. Conversely, (a*)* and a* describe the same language, so this is not an example of minimal DFA exponential growth.

Implementing Subset Construction: Computing All Three Sets in the Graph

The NFA in the graph does not require ε-edges, so the set after move is itself the next set. Below, we directly simulate the NFA, construct the reachable DFA, and finally compare results for all 127 strings of length 0 to 6 over the alphabet {a,b}.

from collections import deque
from itertools import product

edges = {(0, "a"): {0, 1}, (0, "b"): {0}, (1, "b"): {2}}
start, accept = frozenset({0}), {2}


def move(states, char):
    return frozenset().union(*(edges.get((q, char), set()) for q in states))


numbers, subsets, transitions = {start: 0}, [start], {}
work = deque([start])
while work:
    current = work.popleft()
    for char in "ab":
        target = move(current, char)
        if target not in numbers:
            numbers[target] = len(subsets)
            subsets.append(target)
            work.append(target)
        transitions[numbers[current], char] = numbers[target]

assert set(subsets) == {frozenset({0}), frozenset({0, 1}), frozenset({0, 2})}
for length in range(7):
    for letters in product("ab", repeat=length):
        text = "".join(letters)
        nfa, dfa = start, 0
        for char in text:
            nfa = move(nfa, char)
            dfa = transitions[dfa, char]
        assert bool(nfa & accept) == bool(subsets[dfa] & accept) == text.endswith("ab")

The transition table shows why an accepting state is not "always successful": C transitions to B on a, and back to A on b. Here, we are checking if the entire input ends with ab; if the requirement is to search for ab appearing at any position, the control logic or automaton after acceptance must be defined separately.

After adding ε-edges, the start point and the result of each move must take the closure. The closure model below allows ε-cycles, ensuring each state is expanded only once via a visited set:

def closure(seeds, epsilon):
    seen, work = set(seeds), list(seeds)
    while work:
        state = work.pop()
        for target in epsilon.get(state, ()):
            if target not in seen:
                seen.add(target)
                work.append(target)
    return frozenset(seen)


assert closure({0}, {0: {1}, 1: {0, 2}}) == frozenset({0, 1, 2})
assert closure({7}, {}) == frozenset({7})
assert closure(set(), {0: {1}}) == frozenset()

Which NFA states live inside one DFA state?

Distinguish taking one NFA path from storing one name for a whole set. The two views below represent the same prefix: the NFA keeps all possibilities, while A/B/C name entire sets. Edit input or select a prefix to compare acceptance. Reading a after ab leaves acceptance; having accepted an earlier prefix is not permanent acceptance.

$$S_{k+1}=\epsilon \text{-closure}(\mathrm{move}(S_k,c_k))$$

Minimization: Merge Only If Future Behavior Is Identical

Two DFA states are equivalent if, starting from them, any subsequent string yields the same acceptance result. Minimization first classifies by output, then continuously splits states with different future behaviors.

A simple recognizer can first divide into accepting and non-accepting. A lexer must further distinguish acceptance actions: Identifier and Number, even though both are accepting, cannot be merged just by looking at boolean acceptance, as this would lose token types and rule priorities.

Hopcroft's algorithm refines partitions using splitters and their transition predecessors, controlling repeated processing via a work queue and smaller-subset strategies. Simply writing "scan repeatedly until no changes occur" is general partition refinement and is insufficient to prove Hopcroft's complexity. The common formulation for $n$ states and alphabet size $k$ is $O(kn\log n)$; for a fixed alphabet, this is abbreviated as $O(n\log n)$. This is also not a claim of a unified optimal lower bound for all computational models.

The minimum number of states does not equal the fastest machine code. Branch layout, table size, cache hits, and vectorization also affect throughput; whether to minimize and the specific generation format depend on the tool and configuration.

Longest Match and Rule Priority

After composing multiple token rules into a recognizer, a single scan must retain the most recent acceptance position and action until no further progress can be made, then return to that position to output the token. If no acceptance position is ever reached, lexical error handling is triggered.

re2c's rule selection first compares match length, then selects the earlier rule in case of ties. Keywords can also be scanned as identifiers first and then classified via a lookup table; both approaches are valid. re2c Manual

"Single DFA transition in constant time" does not automatically guarantee linear time for the entire longest-match lexer. For example, with rules a and a*b, and input consisting of many as followed by c: a naive scanner scans to the end each time looking for b, then backs up to accept only a single a, repeating this process can lead to quadratic time. Overall complexity must be discussed in conjunction with rule backtracking distance, implementation memoization, or other scanning strategies.

Quantifying Backtracking Cost: Transitions Are Cheap, But The Same Character May Be Visited Many Times

For rules a and a*b, with input aaaaac. Starting from position 0, we read 5 as to try the longer a*b, only confirming failure when c is reached; the most recent acceptance position allows outputting only one a. The next round restarts from position 1, reading 4 more as, and so on. Just the advancement on a amounts to 5+4+3+2+1=15 visits.

def rescans(n):
    source = "a" * n + "c"
    visits = 0
    for start in range(n):
        cursor = start
        while source[cursor] == "a":
            visits += 1
            cursor += 1
        # a*b fails; back up to the acceptance position of a single a, next round starts at start+1.
    return visits


assert rescans(5) == 15
for n in (1, 10, 100):
    assert rescans(n) == n * (n + 1) // 2

Here, we count separately the successful crossings of a, excluding the failed checks on c each round. The quadratic term already comes from repeated suffix scanning; there is no need to make each state transition itself an expensive operation. Improvement requires constraining rule backtracking, recording failure suffix information, or adopting appropriate scanning algorithms; one cannot use "using DFA" as proof that the entire token stream processing is linear.

Why can cheap transitions still yield quadratic scanning?

Count how often each input position is revisited. One row per scan exposes the triangle for final c: n traversals, then n−1, down to one. A final b lets a*b cover the whole string in one scan. The figure counts a traversals only; handling the invalid final c is separate.

$$W(n)=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$$

Comparing Automata and Backtracking Engines

Real-world libraries may combine multiple strategies. Capturing positions and greedy disambiguation require additional information but do not force the implementation to use exponential backtracking. For untrusted patterns, compilation memory limits should be considered; for untrusted inputs, matching workload must be considered. These two cannot be conflated into a single "linear safe" label.

Continue Reading

Lexer Design implements these rules into token, position, buffer, and error recovery interfaces; Recursive Descent and LL Analysis continues to handle nested structures between tokens.

Keywords: regular language, Thompson construction, NFA, DFA, subset construction, epsilon closure, Hopcroft, maximal munch, capture, backreference, ReDoS