Automata & Formal Languages · Instrument 02 · Regular Expressions

Patterns are machines

A regular expression and a finite automaton are the same thing wearing different clothes. Thompson's construction wires any pattern into an ε-NFA, gadget by gadget; the subset construction turns that into a DFA. Three notations, one class of languages — the regular ones.

Operators

Construction

Matching

Equivalence

Thompson's gadgets

Every regular expression is built from four rules, and each rule is a small NFA gadget with one start and one accepting state, glued together with ε-transitions (taken for free):

• literal a — one edge labeled a
• concatenation RS — link R's accept to S's start
• union R|S — branch into both, merge after
• star R* — loop back, or skip entirely

Because each gadget preserves the single-start, single-accept shape, they nest without limit.

the four rules

Choose a pattern

The pattern is parsed and each operator emits its gadget, placed left to right. Solid edges consume a symbol; dashed edges are ε-moves. The whole thing has exactly one start and one accept, however deeply nested.

Thompson NFA

Pattern

Build a string

Run the string through the constructed NFA. After each symbol the active set is closed under ε. Accept if the single accepting state is reachable.

matching

Pattern

Subset-construct the NFA into a DFA, then test strings against all three forms. The columns always agree — regex = NFA = DFA, the three faces of a regular language. The DFA is what a real matcher runs: one state, one transition per symbol.

three forms, one language