Finite Automata

Every computer you have ever used is, at some level of abstraction, absurdly complicated. But strip the abstraction all the way down and you arrive at a finite automaton — a machine with nothing but a fixed set of states, a current state, and a table that says "if you're in state s and you read symbol a, move to state t."

That is it. No scratch pad, no stack, no extra memory at all. The machine reads its input one symbol at a time, moves from state to state, and when the input runs out it checks whether it landed in an accepting state. If yes, the string is accepted; otherwise it is rejected.

These machines — first studied by Warren McCulloch and Walter Pitts in 1943 as a model of neural activity, and formalised by Stephen Kleene in 1956 — are called Deterministic Finite Automata (DFA). Despite being memory-free, they recognise exactly the class of languages described by regular expressions: the patterns that power your text editor's search, your compiler's lexer, and every URL validator on the web.

There is also a richer-seeming variant: a Nondeterministic Finite Automaton (NFA), where a single state may have multiple transitions on the same symbol (or even transitions on nothing, called ε-transitions). It looks more powerful — but as Michael Rabin and Dana Scott proved in 1959, it is not. Every NFA can be converted to an equivalent DFA that accepts exactly the same strings. The price? The DFA may need exponentially more states.

That exponential gap — NFA small, DFA huge — is a preview of a theme that runs through all of computation: the same problem can have wildly different costs depending on which model you choose to solve it in.

Choose a DFA from the dropdown, type any string, and press Step to advance one symbol at a time. The current state lights up so you can follow exactly what the machine is doing. Press Run to process the whole string at once.

<div class="controls">
  <label for="dfaSelect">{{lbl_dfa}}</label>
  <select id="dfaSelect">
    <option value="even_a">{{opt_even_a}}</option>
    <option value="ends_01">{{opt_ends_01}}</option>
    <option value="div3">{{opt_div3}}</option>
  </select>
</div>
<div class="controls">
  <label for="inputStr">{{lbl_input}}</label>
  <input id="inputStr" type="text" value="aaba" maxlength="20" spellcheck="false" autocomplete="off"/>
</div>
<div id="diagram"></div>
<div class="tape-row" id="tapeRow"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="btnStep">{{btn_step}}</button>
  <button id="btnRun">{{btn_run}}</button>
  <button id="btnReset" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .5rem; margin-bottom: .45rem; flex-wrap: wrap; }
label { font-size: .85rem; font-weight: 600; color: #444; white-space: nowrap; }
select, input { font: .9rem system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #cdd9e3;
  border-radius: 6px; background: #f5f8fa; color: #1d3557; }
input { width: 140px; letter-spacing: .05em; }
#diagram { display: flex; gap: 8px; align-items: center; flex-wrap: wrap;
           background: #f0f4f8; border-radius: 10px; padding: 10px 12px; margin: .5rem 0; min-height: 68px; }
.state-box { display: flex; flex-direction: column; align-items: center; gap: 3px; }
.state-circle { width: 46px; height: 46px; border-radius: 50%; border: 2px solid #4a6fa5;
                display: flex; align-items: center; justify-content: center;
                font: 700 14px ui-monospace, monospace; color: #1d3557;
                background: #fff; transition: all .2s; }
.state-circle.accept { border-width: 4px; border-color: #0a7d33; }
.state-circle.current { background: #ffd166; border-color: #d4a000; color: #7a5500; transform: scale(1.13); }
.state-circle.current.accept { border-color: #0a7d33; }
.state-circle.dead { background: #fce8e8; border-color: #e63946; }
.state-label { font-size: .7rem; color: #666; max-width: 60px; text-align: center; word-break: break-word; }
.arrow { font-size: 1.1rem; color: #4a6fa5; flex-shrink: 0; }
.arrow-label { font-size: .75rem; color: #555; text-align: center; margin-top: -4px; }
.tape-row { display: flex; gap: 4px; margin: .4rem 0; flex-wrap: wrap; }
.sym { width: 32px; height: 32px; display: flex; align-items: center; justify-content: center;
       font: 700 14px ui-monospace, monospace; border-radius: 6px;
       background: #dde4ec; border: 1px solid #b8c4d0; color: #1d3557; }
.sym.read { background: #ffd166; border-color: #c8970a; color: #7a5500; }
.sym.past { background: #c5e8cc; border-color: #5aa96a; color: #1a5c2b; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; } .status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what happens when the string is rejected: the machine did not "get stuck" — it simply ended in a non-accepting state. The DFA always reads every symbol; there is no early exit. That is the nature of determinism: for every (state, symbol) pair there is exactly one next state, so the path is always fully determined.

DFA and NFA look very different, but they are provably equivalent:

• NFA → DFA (subset construction): Given an NFA with n states, the equivalent DFA tracks which set of NFA states the machine could currently be in. There are $2^{n}$ possible subsets, so the DFA can have up to $2^{n}$ states. Rabin and Scott (1959) proved this construction always works — and that the exponential bound is tight: there are specific NFA families where no DFA with fewer than $2^{n}$ states can do the same job.
• DFA → NFA: trivial — every DFA is already an NFA (each state just happens to have exactly one transition per symbol).
• Regular languages: the class of languages these machines accept is called regular. It is exactly the class defined by regular expressions and closed under union, concatenation, and Kleene star.
• What they cannot do: a DFA cannot check balanced parentheses (that requires a stack), count arbitrary repetitions, or recognise any context-free language that is not also regular. The pumping lemma (Bar-Hillel, Perles, Shamir, 1961) gives a clean test: if a language is regular, every long-enough string can be "pumped" (a middle section repeated any number of times) and still stay in the language. If that fails, the language is not regular.

This decidability picture is strikingly clean: given two DFA, we can decide in polynomial time whether they accept the same language — a problem that is undecidable for context-free grammars. Minimising a DFA to its smallest equivalent form (Hopcroft's algorithm, 1971) also runs in $O(n \log n)$ time. See also automata minimization and the broader P vs NP context.

Despite their simplicity, finite automata do real work in nearly every layer of a computing system:

• Regular expressions: every regex engine (grep, Python re, JavaScript RegExp) compiles the pattern into an NFA and then simulates it — either by converting to a DFA up front or by running the NFA directly with multiple active states.
• Lexical analysis: the first phase of a compiler or interpreter is a lexer (tokeniser). It is almost always a DFA that recognises keywords, identifiers, literals, and punctuation in a single linear scan of the source file.
• Network packet filtering: firewalls and intrusion-detection systems use DFA to match packet payloads against thousands of patterns simultaneously with guaranteed linear time per byte.
• Hardware controllers: traffic lights, vending machines, elevator logic, and digital circuit controllers are typically designed as explicit state machines — a finite automaton rendered directly in hardware.
• Protocol specification: network protocols (TCP handshake, HTTP request parsing) are formally described as state machines, which makes them amenable to automated verification.

The key guarantee automata give you is linear time: a DFA processes each symbol exactly once and makes exactly one transition — so the work is O(input length) regardless of how complex the pattern is. That predictability is why they remain the tool of choice wherever worst-case performance matters.

A finite automaton carries no memory: it knows only which state it is in right now. That constraint sounds crippling, yet it is exactly enough to recognise every regular language — every pattern that a regular expression can describe — in linear time and constant space.

The equivalence between NFA and DFA is a small miracle: nondeterminism, which looks like cheating, turns out to buy nothing new in terms of what can be recognised. What it does buy is conciseness — an NFA with n states may need a DFA with $2^{n}$ states to simulate it, a gap that is real and unavoidable.

Finite automata sit at the very bottom of the Chomsky hierarchy, the ladder of language classes (regular → context-free → context-sensitive → recursively enumerable). Understanding them is the first step toward understanding what computation can and cannot do — a journey that leads all the way to the halting problem and beyond.