Regex to DFA: Lexer Construction

Regular Expression

NFA states

–

DFA states

–

Test String

Run speed 3/s

Current state

Position

0 / 0

How it works

A lexer generator (lex, flex, re2c) turns a regular expression into a scanner in two provable steps:

1. Thompson's construction builds a nondeterministic finite automaton (NFA) from the regex's syntax tree, with one ε-transition gadget per operator:

a       : one edge labelled 'a'
r·s     : chain accept(r) --ε--> start(s)
r|s     : new start branches --ε--> start(r), start(s);
          accept(r), accept(s) --ε--> new accept
r*      : new start/accept wrap r with ε-loops
          (start->accept, start->r, accept(r)->r, accept(r)->accept)

2. Subset construction (powerset construction) removes the nondeterminism: each DFA state is the ε-closure of a set of NFA states.

ε-closure(T) = T ∪ {states reachable from T by ε-edges only}
move(T, a)   = {states reachable from any state in T by an edge labelled a}
D-states     = { ε-closure({n0}) } ∪ closure under:
  for each D-state S and symbol a:
    target = ε-closure(move(S, a))

A DFA state is accepting iff its NFA subset contains the NFA's accept state — that's why the graph collapses many nondeterministic paths into one deterministic walk.

Build DFA — parses the regex (literals, | alternation, * star, + one-or-more, ? optional, (…) grouping), runs both constructions, and lays out the resulting DFA graph.
Step / Run — feeds the test string through the DFA one character at a time; the highlighted node is the live state. A missing transition rejects immediately — no character makes it past the automaton it doesn't match.

Real-world relevance: this exact pipeline is why [a-zA-Z_][a-zA-Z0-9_]* in a lex spec becomes a single deterministic scan of your source file — no backtracking, one state transition per character.

Start state Accepting state Current position

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.