Thompson Construction
You type a(b|c)* into a regex tester and hit go. Before the engine reads a single character of your input, it has already thrown your pattern away and replaced it with a little map of states and arrows.
- ▸The pattern text never runs. The engine first rebuilds it as a graph of states and arrows.
- ▸Stick two pieces together and the engine adds zero new states, it just fuses the seam.
- ▸Every piece, however large, has one way in and one way out, that is the whole trick.
Take the pattern c: one literal, nothing else. Up to now an operator like c ate a character out of the input and moved on. This time, watch what the engine does before it reads any input at all. It turns c into a tiny machine: two states, a start and a stop, joined by a single arrow labelled c. That is the entire compiled form of c.
Read the machine as a route. You enter at the start, and the only way to reach the stop is to travel the arrow, which you may do only by reading a c. One way in, one way out, with a single labelled step between them.
This two-state shape is the atom everything else is built from. A literal 7 is the same picture with a different label. The empty pattern, the one that matches nothing at all, is the same two states joined by an arrow that carries no label, a free step you may take without reading anything.
Notice what is missing: there is no logic about repetition, no choice, no anchors, none of the pattern syntax. The engine has compiled punctuation into geometry. From here the job is mechanical. Every operator you already know adds a fixed piece of wiring to this picture, and the rest of this topic is just watching the pieces snap together.