Introduction

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)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.

Try It: Build an NFA

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">Regex pattern:</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">Test 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">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 states <span class="nfa-note">(Thompson construction — ε = epsilon transition)</span></div>
    <div id="nfa-table" class="nfa-table"></div>
  </div>
  <div class="sim-section">
    <div class="sim-label">Active states while matching <span id="sim-string" class="sim-str"></span>:</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Thompson's NFA construction for a subset of regex:
// literals, '.', char classes [a-z0-9], concatenation, alternation (|),
// Kleene star (*), plus (+), optional (?), grouping ().
// NFA states: {id, transitions:{char->[state]}, epsilon:[state]}
// Simulation: epsilon-closure + move, no backtracking — O(n * m).

let nfaStart = null, nfaAccept = null, nfaStates = [];
let stateCount = 0;
function newState() {
  const s = { id: stateCount++, transitions: {}, epsilon: [] };
  nfaStates.push(s); return s;
}
function epsilonClosure(states) {
  const closure = new Set(states.map(s => s.id));
  const stack = [...states];
  while (stack.length) {
    const s = stack.pop();
    for (const t of s.epsilon) {
      if (!closure.has(t.id)) { closure.add(t.id); stack.push(t); }
    }
  }
  return closure;
}
function statesById(ids) {
  return nfaStates.filter(s => ids.has(s.id));
}

// Parse helpers
let pos = 0, src = '';
function parseRegex() { return parseAlt(); }
function parseAlt() {
  let { start: s1, accept: a1 } = parseConcat();
  while (pos < src.length && src[pos] === '|') {
    pos++;
    const { start: s2, accept: a2 } = parseConcat();
    const ns = newState(), na = newState();
    ns.epsilon.push(s1, s2);
    a1.epsilon.push(na); a2.epsilon.push(na);
    s1 = ns; a1 = na;
  }
  return { start: s1, accept: a1 };
}
function parseConcat() {
  let result = parseQuantifier();
  while (pos < src.length && src[pos] !== ')' && src[pos] !== '|') {
    const next = parseQuantifier();
    result.accept.epsilon.push(next.start);
    result = { start: result.start, accept: next.accept };
  }
  return result;
}
function parseQuantifier() {
  let { start: s, accept: a } = parseAtom();
  if (pos < src.length) {
    const q = src[pos];
    if (q === '*') { pos++; const ns = newState(), na = newState(); ns.epsilon.push(s, na); a.epsilon.push(s, na); s = ns; a = na; }
    else if (q === '+') { pos++; const na = newState(); a.epsilon.push(s, na); a = na; }
    else if (q === '?') { pos++; const ns = newState(), na = newState(); ns.epsilon.push(s, na); a.epsilon.push(na); s = ns; a = na; }
  }
  return { start: s, accept: a };
}
function parseAtom() {
  if (pos >= src.length) throw new Error('Unexpected end');
  const ch = src[pos];
  if (ch === '(') {
    pos++;
    const inner = parseAlt();
    if (src[pos] !== ')') throw new Error('Missing )');
    pos++;
    return inner;
  }
  if (ch === '[') {
    pos++;
    const chars = parseClass();
    const s = newState(), a = newState();
    for (const c of chars) { if (!s.transitions[c]) s.transitions[c] = []; s.transitions[c].push(a); }
    return { start: s, accept: a };
  }
  pos++;
  const s = newState(), a = newState();
  if (ch === '.') {
    s.transitions['__any__'] = [a];
  } else {
    if (!s.transitions[ch]) s.transitions[ch] = [];
    s.transitions[ch].push(a);
  }
  return { start: s, accept: a };
}
function parseClass() {
  const chars = new Set();
  let negated = false;
  if (pos < src.length && src[pos] === '^') { negated = true; pos++; }
  while (pos < src.length && src[pos] !== ']') {
    const c = src[pos]; pos++;
    if (src[pos] === '-' && pos + 1 < src.length && src[pos + 1] !== ']') {
      pos++;
      const end = src[pos]; pos++;
      for (let code = c.charCodeAt(0); code <= end.charCodeAt(0); code++)
        chars.add(String.fromCharCode(code));
    } else { chars.add(c); }
  }
  if (src[pos] === ']') pos++;
  if (negated) {
    const all = new Set();
    for (let i = 32; i < 127; i++) all.add(String.fromCharCode(i));
    for (const c of chars) all.delete(c);
    return all;
  }
  return chars;
}

function compile(pattern) {
  stateCount = 0; nfaStates = [];
  pos = 0; src = pattern;
  const { start, accept } = parseRegex();
  if (pos < src.length) throw new Error('Unexpected: ' + src[pos]);
  nfaStart = start; nfaAccept = accept;
}

function matchNFA(input) {
  const steps = [];
  let current = epsilonClosure([nfaStart]);
  steps.push({ label: 'start', states: new Set(current), char: null });
  for (let i = 0; i < input.length; i++) {
    const ch = input[i];
    const next = new Set();
    for (const s of statesById(current)) {
      if (s.transitions[ch]) for (const t of s.transitions[ch]) next.add(t.id);
      if (s.transitions['__any__']) for (const t of s.transitions['__any__']) next.add(t.id);
    }
    const closed = epsilonClosure(statesById(next));
    steps.push({ label: fmt('read ""%ch%"', { ch: ch }), states: closed, char: ch });
    current = closed;
  }
  const accepted = current.has(nfaAccept.id);
  return { steps, accepted };
}

function renderNFATable() {
  const div = document.getElementById('nfa-table'); div.innerHTML = '';
  for (const s of nfaStates) {
    const row = document.createElement('div'); row.className = 'nfa-row';
    const lbl = document.createElement('span'); lbl.className = 'nfa-state';
    if (s.id === nfaStart.id) lbl.classList.add('start');
    if (s.id === nfaAccept.id) lbl.classList.add('accept');
    const prefix = s.id === nfaStart.id ? '→' : s.id === nfaAccept.id ? '★' : ' ';
    lbl.textContent = prefix + 'q' + s.id;
    const parts = [];
    for (const [ch, targets] of Object.entries(s.transitions))
      parts.push((ch === '__any__' ? '.' : ch) + '→' + targets.map(t => 'q' + t.id).join(','));
    for (const t of s.epsilon) parts.push('ε→q' + t.id);
    const trans = document.createElement('span'); trans.className = 'nfa-trans';
    trans.textContent = parts.length ? parts.join('  ') : '(no transitions)';
    row.appendChild(lbl); row.appendChild(trans); div.appendChild(row);
  }
}

function renderSim(steps, accepted, input) {
  document.getElementById('sim-string').textContent = '"' + input + '"';
  const div = document.getElementById('sim-steps'); div.innerHTML = '';
  steps.forEach((step, i) => {
    const pill = document.createElement('div');
    const isLast = i === steps.length - 1;
    pill.className = 'sim-step' + (isLast && accepted ? ' accepted' : isLast ? ' active' : '');
    const stateList = [...step.states].sort((a,b)=>a-b).map(id => 'q'+id).join(',');
    pill.textContent = step.label + ' → {' + stateList + '}';
    div.appendChild(pill);
  });
}

function run() {
  const pattern = document.getElementById('regex-input').value;
  const input = document.getElementById('string-input').value;
  const cst = document.getElementById('compile-status');
  const mr = document.getElementById('match-result');
  try {
    compile(pattern);
    cst.textContent = fmt('%length% states', { length: nfaStates.length }); cst.className = 'tag ok';
    renderNFATable();
    const { steps, accepted } = matchNFA(input);
    mr.textContent = accepted ? 'MATCH' : 'NO MATCH';
    mr.className = 'tag ' + (accepted ? 'match' : 'nomatch');
    renderSim(steps, accepted, input);
  } catch(e) {
    cst.textContent = e.message; cst.className = 'tag err';
    mr.textContent = ''; mr.className = 'tag';
    document.getElementById('nfa-table').innerHTML = '';
    document.getElementById('sim-steps').innerHTML = '';
  }
}

document.getElementById('regex-input').addEventListener('input', run);
document.getElementById('string-input').addEventListener('input', run);
document.querySelectorAll('.ex').forEach(btn => btn.addEventListener('click', () => {
  document.getElementById('regex-input').value = btn.dataset.p;
  document.getElementById('string-input').value = btn.dataset.s;
  run();
}));
run();
Result
Console

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).

The Real Complexity

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⋅m)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)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(nlog⁡n)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 {anbna^{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.

Where It Matters

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)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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/regular-expressions/Content licensed under CC BY-NC 4.0.