Regular Expressions and Finite Automata: Theory, Performance, and Conversion

In everyday development we often need to use regular expressions. Different regex patterns can achieve the same matching goal, but their performance may vary dramatically. For example, to match the string <p>hello</p> we can use the greedy pattern /<p>.*<\/p>/ or the lazy pattern /<p>.*?<\/p>/ . Although both patterns match the target, the greedy version incurs more backtracking and is slower.

To illustrate the performance difference, the article stores <p>hello</p> at the beginning, middle, and end of a million‑character document and measures the matching time of the two patterns using regexr.com . The results show that the greedy pattern takes 1.1 ms / 0.7 ms / 0.2 ms, while the lazy pattern takes only 0.1 ms / 0.2 ms / 0.3 ms, clearly demonstrating the impact of pattern design.

The article then explains that regular expressions are built on the theory of Finite Automata (FA). When a regex is compiled, the engine constructs an automaton that accepts the input string if it reaches a final state. The article describes the graphical elements of an automaton (arrows, single/double circles, ε‑transitions) and shows how the regex ab*c translates into a simple FA.

Two types of FA are introduced: Nondeterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA). An NFA may have ε‑transitions and multiple possible moves for the same input symbol, while a DFA has exactly one transition per symbol. Using the example regex ab|ac , the article illustrates the structural differences between the corresponding NFA and DFA.

Conversion from regex to NFA is based on three construction rules (concatenation, alternation, repetition). The article presents these rules with diagrams and shows how the Kleene star A* can be expressed as AA* . It then introduces Thompson’s algorithm, which builds an NFA by combining elementary units for characters and ε‑transitions.

Next, the article covers the subset‑construction method that transforms an NFA into an equivalent DFA. A detailed example from a compiler‑theory textbook— (a|b)*(aa|bb)(a|b)* —is used to walk through the creation of state sets, the construction of the transition table, and the merging of equivalent states.

After obtaining a DFA, the article explains DFA minimization using Hopcroft’s algorithm. By repeatedly partitioning the state set into final and non‑final groups and refining the partitions until they stabilize, the algorithm produces a minimal DFA with fewer states.

The article also discusses why most programming languages implement regex engines as NFAs rather than DFAs: NFAs are more expressive and easier to construct, while DFAs can consume more memory and may not handle certain features (e.g., backreferences) efficiently.

Backtracking is examined in depth. When an NFA engine matches a string, it records each successful character and backtracks when a mismatch occurs. The article demonstrates backtracking with the pattern ab|ac against the string ac , and shows how greedy quantifiers ( * ) cause extensive backtracking. A case of catastrophic backtracking is presented with the pattern a*b applied to the string aaa , where the engine repeatedly retries and ultimately fails.

Finally, the article emphasizes that small changes in regex syntax can lead to large performance differences in real‑world applications. Readers are encouraged to understand the underlying automata theory to write robust and efficient regular expressions.

References include lectures on compiler theory, tutorials on building a simple regex engine, and the book High‑Performance JavaScript by Nicholas C. Zakas.