a regex engine

When you type a search pattern into a text editor, a grep command, or a web form's validation field, something behind the scenes takes your pattern and checks it against text. That something is a regex engine: the software that compiles a pattern string into a matcher and then runs it over input. It is the everyday, practical descendant of the mathematical regular expression.

There are two broad engine designs, and the difference matters. An automaton-based engine (the kind built on Thompson's construction plus NFA or DFA simulation) processes each input character a bounded number of times, giving guaranteed linear-time matching; tools like grep and the RE2 library work this way. A backtracking engine instead tries one way to match, and if it fails, backs up and tries another, much like exploring a maze by trial and error; most language libraries (Perl, Python's re, Java, JavaScript) use backtracking because it cleanly supports extra features. The engine also handles anchors, character classes, capture groups, and other conveniences layered on top of the three core operations.

Here is the honest part: a regex engine usually accepts more than truly-regular patterns. Backreferences and lookahead, common in backtracking engines, let you describe languages that no finite automaton can recognize, so 'regex' in programming is a superset of the mathematical object that happens to share its name. This extra power comes at a cost: backtracking engines can take exponential time on some patterns and inputs (catastrophic backtracking), whereas automaton-based engines stay fast but refuse the non-regular features. Choosing an engine is a real engineering trade-off between expressiveness and worst-case speed.