Regular Expressions and Finite Automata: DFA, NFA, and Thompson Construction

Regular expressions (regex) and Finite State Automata (FSA) are foundational concepts in theoretical computer science, compiler design, lexical analysis, and formal language theory. Understanding the conversion between regular expressions, Non-Deterministic Finite Automata (NFA), and Deterministic Finite Automata (DFA) is essential for writing high-performance parsers and preventing catastrophic exponential backtracking (Regular Expression Denial of Service - ReDoS).

This guide details Thompson's Construction algorithm, the Powerset Subset Construction for DFA determinization, Chomsky hierarchy classifications, and ReDoS mitigation.

1. Quick-Reference: DFA vs. NFA Comparison

+-----------------------------------------------------------------------------------------+
|                               FINITE AUTOMATA COMPARISON                                |
+-----------------------------------------------------------------------------------------+
| Dimension              | Deterministic Finite Automaton(DFA)| Non-Deterministic Automaton(NFA)|
+------------------------+------------------------------------+---------------------------------+
| Transition Uniqueness  | Exactly 1 transition per (state, σ)| Multiple transitions possible   |
| $\epsilon$-Transitions | Not permitted                      | Permitted (free jumps)          |
| String Matching Time   | Strictly $O(N)$ linear time        | $O(M \cdot N)$ or $O(2^N)$ back |
| State Space Size       | Potentially $O(2^M)$ states        | Exactly $O(M)$ states (Linear)  |
| Canonical Engines      | Rust `regex`, Google `RE2`         | Python `re`, PCRE, JavaScript   |
+-----------------------------------------------------------------------------------------+

2. Thompson's NFA Construction Algorithm

Ken Thompson's algorithm compiles any regular expression of length M into an equivalent \epsilon-NFA with at most 2M states in O(M) time.

Thompson Construction Primitives:
1. Base Symbol 'a':      (State 0) --- 'a' ---> ((State 1))
2. Concatenation 'ab':   (S0) -- 'a' --> (S1) -- ε --> (S2) -- 'b' --> ((S3))
3. Alternation 'a|b':    (S_in) -- ε --> (Branch A) -- ε --> ((S_out))
                               \-- ε --> (Branch B) -- ε --/
4. Kleene Star 'a*':     (S_in) -- ε --> (Loop A) -- ε --> ((S_out))
                               \-------- ε -------------->/ (Bypass)

3. The ReDoS Catastrophic Backtracking Hazard

Backtracking engines (such as standard Python and JavaScript regex engines) evaluate ambiguous nested quantifiers like (a+)+$ in O(2^N) exponential time when matching non-matching inputs like "aaaaaaaaaaaaab".