Course contentsShow
← Computer Science
Lesson 1942 of 2,87244. Lexical Analysis and ParsingFree lesson

From Regular Expressions to Finite Automata

Converting regular expression patterns into NFAs and then DFAs for efficient token recognition.

From Regular Expressions to Finite Automata

What You'll Learn

You'll learn how to systematically convert regular expression patterns into executable finite automata that can efficiently recognize tokens in a lexical analyzer.

The Bridge Between Patterns and Machines

Regular expressions are patterns that describe token structures (like identifiers, numbers, or keywords). But a compiler can't directly "run" a regex—it needs a concrete machine to process input character by character. That machine is a finite automaton.

The conversion happens in two stages:

Stage 1: Regular Expression → NFA

Using Thompson's Construction, each regex operator gets translated into a small NFA fragment:

  • Single character a: Two states connected by an edge labeled a
  • Concatenation ab: Chain the NFA for a to the NFA for b
  • Alternation a|b: Create parallel paths with ε-transitions
  • Kleene star a*: Add a loop with ε-transitions for zero-or-more repetition

These fragments connect together to build a complete NFA matching the entire regex.

Stage 2: NFA → DFA

The resulting NFA often has nondeterminism—multiple possible transitions from a state, or ε-transitions that move without consuming input. This makes direct simulation slow.

We use the subset construction algorithm to convert the NFA into an equivalent DFA where each state represents a set of NFA states. The DFA has exactly one transition per input symbol from each state, making it much faster to execute.

Why This Matters

Once you have a DFA, recognizing tokens becomes trivial: start at the initial state, follow exactly one transition per input character, and check if you end in an accepting state. This deterministic, table-driven approach is what makes lexical analysis blazingly fast.

Key Takeaway: Converting regex → NFA → DFA transforms declarative token patterns into efficient, executable state machines that power the first phase of compilation.