Automata and Regular Languages
Finite automata (DFAs and NFAs), regular languages, the equivalence of regular expressions and automata (Thompson's construction, subset construction), minimisation, the pumping lemma and what regexes cannot match (balanced brackets), backtracking engines versus automata engines, and ReDoS measured.
Finite automata
// the DFA above as a table-driven matcher: O(n), no backtracking possible
const T = { start: c => c === '0' ? 'zero' : /[1-9]/.test(c) ? 'num' : 'dead',
zero: () => 'dead',
num: c => /[0-9]/.test(c) ? 'num' : 'dead',
dead: () => 'dead' };
const accepts = s => ['zero', 'num'].includes([...s].reduce((q, c) => T[q](c), 'start'));
accepts('420000') // true accepts('042') // false accepts('0') // trueSame power: every regular expression can be turned into an NFA (Thompson's construction) and then a DFA (subset construction), and every DFA back into a regex. What they cannot do: recognise balanced brackets or nested JSON, because that needs unbounded counting and a DFA has finitely many states (the pumping lemma proves it). Use a parser (next part).
ReDoS, measured
const re = /^(a+)+$/;
for (const n of [16, 20, 22, 24, 26]) { const s = 'a'.repeat(n) + 'b'; const t = process.hrtime.bigint(); re.test(s);
console.log(n, Number(process.hrtime.bigint() - t) / 1e6, 'ms'); }
// Node v25.7.0, M3 Pro: 16 → 4.7 ms, 20 → 7.5, 22 → 27.1, 24 → 107.3, 26 → 440.2
/^a+$/.test('a'.repeat(100000) + 'b') // 0.17 msThis class of bug, regular expression denial of service, has caused real outages; Cloudflare's global outage on 2 July 2019 was caused by a backtracking regex in a WAF rule that exhausted CPU. Since V8 8.8, Node also offers an experimental non-backtracking engine for some patterns (the --enable-experimental-regexp-engine flag and the /l flag).