Theoretical Foundations of Regular Expressions
Regular expressions (regex) are algebraic formulas used to define search patterns in text. They are built on formal language theory and theoretical computer science. In the Chomsky hierarchy, regular expressions define regular languages, which are parsed using finite automata.
A finite automaton is a mathematical model of computation representing state machines that process input strings character by character, transitioning between states based on predefined rules. There are two primary types of automata:
- Deterministic Finite Automata (DFA): Transition from one state to exactly one other state for any input. DFAs are fast, running in linear time O(N) relative to the text length, but do not support advanced regex features like backreferences.
- Non-deterministic Finite Automata (NFA): Can transition to multiple states simultaneously or backtrack. Most programming language regex engines (including JavaScript, Python, and Java) use backtracking NFA engines because they support capturing groups and lookaround assertions.