Regular Expressions and Finite Automata

You have typed a regex — a short string like [A-Z][a-z]+\d{2,4} — into a text editor, a terminal, or a script, and within milliseconds it scanned megabytes of text and flagged every match. Where does that speed come from, and what exactly can a regex match?

The answers go back to 1956, when the mathematician Stephen Kleene defined regular languages — the class of patterns that can be described by a finite set of states and transitions. In 1959, Ken Thompson (who later co-created Unix) showed how to compile any regular expression into a nondeterministic finite automaton (NFA) in linear time and simulate it without ever backtracking. The result: matching always runs in $O(n)$ in the length of the input, no matter how complex the pattern.

Regular expressions define exactly the regular languages — not one pattern more, not one less. That tight correspondence between the notation and the machine is what makes them both powerful and predictable.

Type a regular expression below and test strings against it. The demo implements Thompson's construction, compiling your pattern to an NFA, then simulates the NFA by tracking all active states at once — no backtracking ever needed.

<div class="demo-wrap">
  <div class="input-row">
    <label for="regex-input">{{lbl_regex}}</label>
    <input id="regex-input" type="text" value="ab*c" spellcheck="false" autocomplete="off"/>
    <span id="compile-status" class="tag"></span>
  </div>
  <div class="input-row">
    <label for="string-input">{{lbl_string}}</label>
    <input id="string-input" type="text" value="abbc" spellcheck="false" autocomplete="off"/>
    <span id="match-result" class="tag"></span>
  </div>
  <div class="examples-row">
    <span class="ex-label">{{lbl_try}}</span>
    <button class="ex" data-p="ab*c" data-s="abbc">ab*c</button>
    <button class="ex" data-p="a(b|c)d" data-s="acd">a(b|c)d</button>
    <button class="ex" data-p="[0-9]+" data-s="42">digits+</button>
    <button class="ex" data-p="hel+o" data-s="helllo">hel+o</button>
    <button class="ex" data-p="colou?r" data-s="color">colou?r</button>
  </div>
  <div class="nfa-section">
    <div class="nfa-header">{{nfa_header}} <span class="nfa-note">{{nfa_note}}</span></div>
    <div id="nfa-table" class="nfa-table"></div>
  </div>
  <div class="sim-section">
    <div class="sim-label">{{sim_label_pre}} <span id="sim-string" class="sim-str"></span>{{sim_label_post}}</div>
    <div id="sim-steps" class="sim-steps"></div>
  </div>
</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #1a1a2e; background: #f8f9fb; }
.demo-wrap { padding: .75rem; display: flex; flex-direction: column; gap: .65rem; }
.input-row { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; }
label { font-size: .82rem; font-weight: 600; white-space: nowrap; min-width: 90px; }
input[type=text] { flex: 1; min-width: 130px; font: 500 14px ui-monospace, monospace;
  padding: .3rem .55rem; border: 1.5px solid #c0c8d8; border-radius: 6px; background: #fff; outline: none; }
input[type=text]:focus { border-color: #5a7088; }
.tag { font-size: .78rem; font-weight: 700; padding: .18rem .5rem;
  border-radius: 5px; white-space: nowrap; }
.tag.ok { background: #d4edda; color: #155724; }
.tag.err { background: #f8d7da; color: #721c24; }
.tag.match { background: #cce5ff; color: #004085; }
.tag.nomatch { background: #fff3cd; color: #856404; }
.examples-row { display: flex; align-items: center; gap: .35rem; flex-wrap: wrap; }
.ex-label { font-size: .8rem; color: #555; }
button.ex { font: 500 12px ui-monospace, monospace; padding: .22rem .55rem;
  border: 1px solid #b0bec5; border-radius: 5px; background: #fff; cursor: pointer; }
button.ex:hover { background: #e8eef3; }
.nfa-section { background: #fff; border: 1px solid #dde3ed; border-radius: 8px; padding: .55rem; }
.nfa-header { font-size: .8rem; font-weight: 700; color: #3d4f60; margin-bottom: .35rem; }
.nfa-note { font-weight: 400; color: #7a8ba0; font-size: .75rem; }
.nfa-table { font-size: .78rem; font-family: ui-monospace, monospace; max-height: 160px;
  overflow-y: auto; display: flex; flex-direction: column; gap: 2px; }
.nfa-row { display: flex; gap: .5rem; align-items: baseline; }
.nfa-state { min-width: 32px; font-weight: 700; color: #1d3557; }
.nfa-state.start { color: #0a7d33; }
.nfa-state.accept { color: #c92f3c; }
.nfa-trans { color: #444; }
.sim-section { background: #fff; border: 1px solid #dde3ed; border-radius: 8px; padding: .55rem; }
.sim-label { font-size: .8rem; font-weight: 700; color: #3d4f60; margin-bottom: .35rem; }
.sim-str { font-family: ui-monospace, monospace; font-weight: 400; color: #1d3557; }
.sim-steps { display: flex; flex-wrap: wrap; gap: .35rem; }
.sim-step { font-size: .76rem; font-family: ui-monospace, monospace;
  padding: .18rem .45rem; border-radius: 5px; border: 1px solid #c0c8d8; background: #f0f4f8;
  color: #1d3557; }
.sim-step.active { background: #d0e8ff; border-color: #80baff; font-weight: 700; }
.sim-step.accepted { background: #d4edda; border-color: #5cb85c; color: #155724; font-weight: 700; }

// Code not found

Notice that every input string gets an answer in time proportional to its length, regardless of how nested the pattern is. This is the guarantee that makes regex engines safe to use on untrusted data — as long as the engine follows Thompson's algorithm rather than recursive backtracking (some older engines do not, and can exhibit catastrophic slowdown).

Regular expressions sit in a precise place in the complexity landscape — proven, not conjectured.

• Matching is in P. Thompson's NFA simulation runs in $O(n \cdot m)$ time, where n is the input length and m is the pattern size. Converting the NFA to a DFA first gives $O(n)$ matching but at the cost of up to 2ᵐ states — so the NFA simulation is usually preferred.
• Equivalence is PSPACE-complete (Stockmeyer & Meyer, 1973). Asking whether two regular expressions match exactly the same set of strings is a provably hard problem — every PSPACE problem reduces to it.
• Minimising a DFA is polynomial (Hopcroft's algorithm, 1971, $O(n \log n)$). This is a rare example where a natural optimisation problem admits a sub-quadratic exact solution.
• The pumping lemma proves limits. Regular languages cannot count. The language {$a^{n}b^{n}$ : n ≥ 1} — equal numbers of as and bs — is not regular; no finite automaton can accept it. This is proven impossible, not merely unachieved.
• Context-free languages require a stack. As soon as you need to match balanced brackets or nested structures, you leave the world of regular expressions and enter context-free grammars — the next level in the Chomsky hierarchy.

The boundary is clean: regular expressions are exactly what finite automata can recognise, and we know precisely which patterns exceed that boundary.

The NFA–DFA duality powers a surprisingly wide range of technology:

• Lexical analysis in compilers: every compiler's first stage (the lexer) is a DFA compiled from regular expressions that tokenises source code. Tools like Flex generate this DFA automatically.
• Text search tools: grep, sed, and editors like VS Code run NFA simulations. Correct implementations guarantee $O(n)$ matching regardless of the pattern.
• Network intrusion detection: systems like Snort and Suricata match thousands of attack signatures simultaneously using multi-pattern automata built from regular expressions.
• Bioinformatics: sequence motif search in DNA and protein databases is finite-automaton matching at genomic scale.
• Input validation: email addresses, phone numbers, and date formats are validated by automata compiled from regular expressions in virtually every programming language's standard library.

Understanding finite automata explains why regex matching is fast and provably safe when implemented correctly — and why features like backreferences (which break the regular-language model) can make matching exponentially slow.

Regular expressions look like a practical tool, but they rest on one of the cleanest theories in computer science. Kleene defined the regular languages; Thompson showed they compile to NFAs in linear time; the pumping lemma proved they cannot count; and the equivalence problem was placed in PSPACE.

Every grep invocation, every compiler lexer, every firewall rule is a finite automaton in disguise. The machine has a fixed amount of memory, forgets everything it doesn't track in its state, and yet matches exactly the patterns we can describe with concatenation, alternation, and repetition. That is both its power and its limit — and the limit is as precisely drawn as any boundary in all of theoretical computer science.