Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 61 ยท Lexical Analysis

From Regex to NFA to DFA

Turn a regular expression into an NFA with Thompson's construction, then into a DFA with subset construction, and see DFA minimization in runnable Python.

A lexer author writes patterns such as [a-z][a-z0-9]* because regular expressions are compact. A machine cannot run a pattern directly, though. It needs a finite automaton: a small graph of states that reads one character at a time. The classic route from the first to the second has three steps, and every lexer generator (Lex, Flex, and the regex engines inside many tools) follows it in some form:

  1. Parse the regular expression and build an NFA using Thompson's construction.
  2. Convert the NFA into a DFA with the subset construction.
  3. Optionally minimize the DFA so that it has as few states as possible.

This lesson walks through all three and builds each one in Python. It assumes you know what NFAs and DFAs are; if not, read Finite Automata: DFA and NFA first. The regex operators are recapped in Regular Expressions for Lexers.

The big picture

flowchart LR
    R["Regex<br/>(a|b)*abb"] --> N["NFA<br/>with epsilon moves"]
    N --> D["DFA<br/>one move per symbol"]
    D --> M["Minimal DFA"]
    M --> T["Transition table<br/>used by the lexer"]

From pattern to table: each arrow is an algorithm you can implement in a few dozen lines.

Why not stop at the NFA? An NFA can be in several states at once, so simulating it costs work for every character. A DFA is always in exactly one state, so matching takes one table lookup per character. Lexers scan huge files, so they pay the conversion cost once, at build time, and enjoy the fast matching forever.

Thompson's construction

Thompson's idea is to build the NFA for a big regex by gluing together the NFAs of its parts. Every piece, called a fragment, has exactly one start state and one accept state. Gluing uses epsilon moves (written eps, also called lambda moves), which let the automaton change state without reading a character.

There is one rule per regex operator:

  • A single symbol a: two states, with an edge labeled a from the first to the second.
  • Concatenation RS: an epsilon edge from the accept state of R to the start state of S.
  • Alternation R|S: a new start state with epsilon edges into both R and S, and a new accept state that both of them reach with epsilon edges.
  • Star R*: a new start and a new accept state. The new start goes into R and can also skip straight to the new accept (zero repetitions). The accept state of R loops back to the start of R (more repetitions) and also leaves to the new accept state.
  • Plus R+ and optional R?: star without the skip edge, and star without the loop-back edge.
flowchart LR
    s(("start")) -- eps --> r1(("R in"))
    r1 -. "R" .-> r2(("R out"))
    r2 -- eps --> e(("accept"))
    s -- "eps (skip)" --> e
    r2 -- "eps (repeat)" --> r1

The NFA for R. The top path runs R once or more, the skip edge allows zero times.*

Thompson's construction has useful properties: an NFA has at most twice as many states as the regex has symbols and operators, every state has at most two outgoing edges, and no edge ever enters the start state of the whole machine. This keeps the NFA small and predictable.

Building it in Python

The code below parses a regex with a tiny recursive-descent parser (the same technique you will use for the toy language later) and builds fragments as it goes. It supports |, *, +, ?, grouping with parentheses, and plain characters. It then simulates the NFA by tracking the set of states the machine could be in.

The function eps_closure is the key helper: given a set of states, it adds every state reachable by epsilon edges alone.

Python Thompson's construction and NFA simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the printed transition list and find the a, b, b edges at the end, and the loop made by states 1 to 9 for (a|b)*. Our parser makes a few extra "glue" states (the textbook version for this regex has fewer), but the shape is the same and every state still has at most two outgoing edges.

Notice how nfa_matches works: it never guesses. It keeps all the states the NFA could be in and advances them together. That is the secret that avoids exponential backtracking, and it is how the project A Regex Engine will work.

Epsilon closure

The epsilon closure of a set of states S, written eps-closure(S), is the set of all states you can reach from S using only epsilon edges (including S itself). It is a plain graph search, which is why eps_closure above is a stack-based depth-first search with a seen set. Two operations come up all the time:

  • move(S, a): the states reachable from S by reading one symbol a.
  • eps_closure(move(S, a)): what an NFA simulation does for each character.

Forgetting the closure after a move is the most common bug when you write this by hand. You then find the right states but miss the ones reachable through epsilon edges, and patterns like a* suddenly fail.

The subset construction

A DFA state is a set of NFA states. The subset construction creates DFA states on demand:

  1. The DFA start state is eps-closure({NFA start}).
  2. Take an unprocessed DFA state D and every input symbol a. Compute eps_closure(move(D, a)). If it is non-empty, it is the target of the edge labeled a from D. If it has not been seen, add it to the work list.
  3. Repeat until no unprocessed states remain.
  4. A DFA state is accepting if its set contains the NFA's accept state.

If the NFA has n states, the DFA could in theory have up to 2^n states, because there are that many subsets. In practice, lexer patterns produce DFAs of modest size, because only subsets reachable from the start are ever created. There are known pathological regexes that really do blow up, but they rarely show up in tokenizers.

Python Subset construction and the resulting DFA table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 17-state NFA collapsed into a 5-state DFA, and each DFA state is printed as the NFA states it stands for. The NFA and DFA agree on every test word. The last line previews the next section: the 5-state DFA can still be squeezed to 4 states.

Notice also that dfa_matches has no sets, no closure and no search. It is a loop with one dictionary lookup per character. This is exactly the table a generated lexer embeds.

DFA minimization

Two DFA states are equivalent if no input string can tell them apart: for every string, both end in an accepting state or both end in a non-accepting state. Equivalent states can be merged without changing the language. Every regular language has a unique smallest DFA, so minimization also gives you a canonical form for comparing two patterns.

The simplest algorithm is partition refinement (Moore's algorithm):

  1. Start with two groups: accepting states and non-accepting states.
  2. Split a group whenever two of its states, on some symbol, move into different groups.
  3. Stop when a full round splits nothing. States that are still together are equivalent.

Hopcroft's algorithm does the same thing faster, in O(n log n) instead of O(n^2) per refinement, by always splitting with the smaller half. Production tools use it; Moore's version is easier to read, so we use it here.

flowchart TD
    A["Round 0<br/>accepting vs not"] --> B["Round 1<br/>split states whose targets<br/>fall in different groups"]
    B --> C["Round 2<br/>split again"]
    C --> D["No change:<br/>groups are the minimal states"]

Partition refinement starts coarse and only ever splits groups, so it must stop.

Here is a wasteful 6-state DFA for "strings over a and b that end in abb". Watch the groups get refined:

Python Minimizing a DFA by partition refinement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

S0, S2 and S5 all mean "I have not yet seen the start of an abb". They behave identically, so they become one state. Compare with the DFA in the previous example: its D0 and D2 are the same kind of pair, which is why that DFA minimizes from 5 states to 4.

Putting it together in a lexer

A real lexer has many token patterns, not one. Lex-style tools build one NFA per pattern, join them all with a new start state and epsilon edges, and remember which token type each accept state belongs to. After the subset construction, a DFA state may contain several NFA accept states. Then the earliest rule in the specification wins, which gives keywords priority over identifiers. Combined with the "keep going while the DFA can still move, then fall back to the last accepting state" rule, this implements longest match, discussed in Regular Expressions for Lexers.

Lexers also add a dead state (a trap that every missing transition leads to), so the table is total. In our printed table we simply left it out and used -, which is the same thing.

Python's own re module does not follow this pipeline. It uses backtracking, which supports features like backreferences but can take exponential time on patterns such as (a*)*b. Engines built on NFA simulation or DFAs (such as RE2 and the one in this lesson) guarantee time linear in the input.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does Thompson's construction produce?

    Thompson's construction glues small NFA fragments (one start state and one accept state each) together with epsilon edges, one rule per regex operator.
  2. 2. In the subset construction, what is a single DFA state?

    The DFA is always in exactly one state, and that state stands for the whole set of NFA states the NFA could be in after reading the same input.
  3. 3. When is a DFA state accepting after the subset construction?

    If any NFA state the machine could be in is accepting, the input read so far matches the regex, so the DFA state is accepting.
  4. 4. What does the epsilon closure of a set of NFA states contain?

    The closure follows epsilon edges repeatedly, since those moves consume no input.
  5. 5. Which statement about DFA minimization is correct?

    Partition refinement starts with two groups and splits any group whose members move into different groups on some symbol. The language never changes.

Summary

  • A regex becomes an NFA with Thompson's construction: small fragments with one start and one accept state, joined by epsilon edges.
  • The epsilon closure adds every state reachable without reading input; apply it after every move when simulating an NFA.
  • The subset construction turns the NFA into a DFA whose states are sets of NFA states; accepting sets contain the NFA's accept state.
  • A DFA matches with one table lookup per character, which is why lexers are compiled to DFAs.
  • Minimization merges equivalent states with partition refinement (Moore) or Hopcroft's faster version; the result is unique for a language.
  • A lexer combines all token patterns into one automaton and breaks ties by rule order and longest match.

Next: Writing a Complete Lexer