Gregory Friedman The Greg Wide Web on the name →

Case Study · CS Theory · Linguistics

Automaton Playground

2026 · in progress · repository

The idea

In 2024 I wrote myself a one-file Python exercise: DFA.py, a from-scratch implementation of deterministic finite automata. The module docstring reads “maybe go into REs, NFAs, then maybe CFGs and PDAs”, a to-do list I left for future me. This project is future me answering: the exercise becomes an interactive plate where you draw states, add transitions, feed the machine a string, and watch it run.

A DFA is the smallest interesting model of computation, and it deserves better than a static diagram in a textbook. Formally it’s a 5-tuple

M=(Q,Σ,δ,q0,F),M = (Q, \Sigma, \delta, q_0, F),

where QQ is a finite set of states, Σ\Sigma a finite alphabet, δ:Q×Σ→Q\delta : Q \times \Sigma \to Q the transition function, q0∈Qq_0 \in Q the start state, and F⊆QF \subseteq Q the accepting states. Extend δ\delta to whole strings by δ^(q,ε)=q\hat{\delta}(q, \varepsilon) = q and δ^(q,wa)=δ(δ^(q,w),a)\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a), and the language the machine recognizes is

L(M)={ w∈Σ∗:δ^(q0,w)∈F }.L(M) = \{\, w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \,\}.

The definition is five symbols of setup for one idea: computation as a walk through a graph. That’s exactly the thing a playground can show and a formula can’t.

Four machines, one pipeline

Transition table; “Even number of a's”

Transition table of the deterministic finite automaton accepting strings over a, b with an even number of a's. Rows are states, columns are input symbols; each cell is the next state.
state ab
→ ◎ q0 q1q0
q1 q0q1

→ marks the start state, ◎ an accepting one. This machine accepts exactly the strings over {a, b} with an even number of a's. The interactive playground, including the Turing machines, needs JavaScript.

Input
State q0 step 0

Build a string with the symbol keys, then Step or Run.

Plate I The playground: toggle between finite automata and Turing machines, pick a preset, build an input from its alphabet keys, and step or run it. An automaton walks its state diagram, the current state glowing green on acceptance and ochre on rejection (states can be dragged to rearrange). A Turing machine runs on a tape whose head you watch read, write, and move; a missing rule is a clean rejection, exactly as it is on a decider. Open the formal-definition panel to see the machine as its tuple: the 5-tuple for automata, the 7-tuple for Turing machines.

NFA transition table; “Strings ending in “ab””

Transition table of the nondeterministic finite automaton accepting strings over a, b that end in ab. Rows are states, columns are input symbols plus epsilon; each cell is the set of possible next states.
state abε
→ q0 {q0, q1}{q0}∅
q1 ∅{q2}∅
◎ q2 ∅∅∅

→ marks the start state, ◎ an accepting one. Cells hold sets of states; on “a” in q0 the machine may stay or guess that the suffix has begun. Determinizing this NFA by the subset construction, and watching it happen, needs JavaScript.

Input

NFA

Determinized DFA

Build a string, then Step or Run; every state the NFA could be in glows at once.

Plate II Nondeterminism and its price: run an NFA and the whole active set glows at once (dashed rings flag states added by ε-closure), accepting iff any active state accepts. Switch to Determinize and the subset construction assembles the equivalent DFA one subset-state at a time, then reports the score (4 NFA states → 6 DFA states; the worst case would be 16) and lets you run the result.

Thompson's construction; the complete rule set

The five rules of Thompson's construction, which compile any regular expression into a nondeterministic finite automaton with epsilon transitions.
constructgadget
literal c two fresh states joined by a single c-edge; the atom everything else wraps
R·S (concatenation) an ε-edge glues R’s end to S’s start
R | S (union) a new start forks by ε into R and S; both rejoin at a new end
R* (star) new start and end; ε-edges let the input repeat R (back edge) or skip it entirely
R+ · R? star’s two halves sold separately: + keeps the repeat edge, ? keeps the skip

Every rule adds at most two states, so a regex of length n compiles to an NFA with O(n) states; nondeterminism is what keeps the machine small. Watching the gadgets assemble (and then driving the result) needs JavaScript.

Input

Plate III Thompson's construction: a regular expression compiled to an NFA one rule at a time (literal gadgets, ε-glue concatenation, union forks, star wrappings), each step's new states glowing as the fragments assemble in place. Edit the regex (literals, parentheses, |, *, +, ?), then switch to Run and drive the machine you just watched get built.

Two groups: accepting and the rest. Split until stable.

Transition table of the preset DFA. Each row is a state; columns give the state reached on input a and input b; the last column marks accepting states.
stateabaccept
A BA
B DC
C BA ✓
D DE
E DA ✓
G1 A B D
G2 C E

Initial partition: 2 groups (accepting vs non-accepting).

Plate IV Minimization by partition refinement, the pipeline's last stage: start by splitting states into accepting and non-accepting, then split any group whose members disagree on where an input symbol sends them. When nothing splits, each group is one state of the smallest DFA that recognizes the language. This preset carries two redundant states on purpose; watch it fall from five states to three.

The four plates trace the whole pipeline a regex engine runs internally: a pattern becomes an NFA (Plate III), the NFA becomes a DFA (Plate II), and the DFA is squeezed to its smallest equivalent form (Plate IV), which is the machine you would actually ship. Minimization is also the piece with the cleanest theorem behind it: the minimal DFA for a language is unique up to renaming, so two regexes describe the same language exactly when their minimal DFAs are identical. Partition refinement is how you check.

Play with the machines above first; the sections below are the how and the why behind them.

The missing middle: what one stack buys

Four plates, and all of them recognize the same class of language. The pipeline above is tidy precisely because regular languages are closed under everything you throw at them, but the tidiness hides the interesting question, which is what falls outside. Take { anbn:n≥1 }\{\, a^n b^n : n \ge 1 \,\}: some number of a’s, then the same number of b’s. No finite automaton recognizes it, and the proof is the theorem every theory student meets and few enjoy. The pumping lemma says that a machine with pp states, reading apbpa^p b^p, must visit some state twice inside the opening block of a’s, so the segment of input between those two visits can be deleted or repeated as often as you like and the machine will end in the same place. Repeat it once and the string has more a’s than b’s while the machine still accepts, which it must not. The lemma is really a statement about memory rather than about strings: a finite control can remember finitely many things, and “how many a’s have I seen so far” is not one of them when nn is unbounded. One caution, since this is the part that gets misremembered: the lemma is a necessary condition and not a sufficient one. There are non-regular languages that pump perfectly well, so passing the test proves nothing. Only failing it proves anything.

I considered a pumping-lemma game for this page, a two-player adversary where the reader picks a decomposition and the machine picks the pump count that breaks it, and decided against it. What makes that theorem hard is the alternation of quantifiers (for every pp, there exists a string, for every decomposition, there exists an ii), and a game interface hides quantifier structure rather than revealing it. The reader coming off Plate IV does not need a fifth argument that finite memory is not enough. They need the machine that has just enough more, which is a finite automaton with one stack bolted on. A pushdown automaton is the 7-tuple (Q,Σ,Γ,δ,q0,Z,F)(Q, \Sigma, \Gamma, \delta, q_0, Z, F), and the only line that matters is δ\delta: read an input symbol or nothing at all, pop the symbol on top of the stack, push a string back in its place. That is the whole extension, and it is exactly enough to count to one depth of nesting.

Transition table; “Balanced brackets”

Transition table of a deterministic pushdown automaton recognizing balanced brackets. Each row is a rule: in the given state, reading the given symbol with the given symbol on top of the stack, replace the stack top and move to the next state.
statereadpoppushnext
→ ◎ q0 ( Z A Z q1
q1 ( A A A q1
q1 ) A ε q1
q1 ε Z Z q0

→ marks the start state, ◎ an accepting one; Z is the bottom of the stack, and a push of ε means the popped symbol is simply gone. No two rules can apply at once, so this machine is deterministic. The interactive machine, with the stack drawn as it rises and falls, needs JavaScript.

Input
Try

Stack

Pick a string, then Step or Run.

statereadpoppushnext

Plate V A pushdown automaton with its memory drawn beside it. The machine is the state diagram from the plates above, unchanged, plus one column: each rule reads a symbol (or nothing, on an ε-move), pops whatever is on top of the stack, and pushes a string back in its place, with the rule that fired highlighted in the table below. Step through aⁿbⁿ and watch the pile rise once per a and fall once per b, the bottom marker Z reappearing exactly when the two counts match. The third preset is the one to sit with: equal numbers of a's and b's in any order at all, where nothing nests and the stack is simply a counter with a sign.

Every machine in that plate is deterministic, and the formal-definition panel checks it rather than asserting it: no two rules may apply to the same configuration. That restriction is the limit of what a single animated trace can show. The textbook pushdown automaton for even-length palindromes has to guess where the middle of the string is, and a guess is not a trace; drawing it faithfully would mean drawing a tree of live configurations, which is a different figure about a different subject. So the palindrome preset carries an explicit centre marker, w c wRw\,c\,w^R, and the machine reads the middle instead of guessing it. The gap that opens up is real and worth naming: unlike finite automata, where the subset construction of Plate II makes nondeterminism free, deterministic pushdown automata recognize strictly fewer languages than nondeterministic ones. Palindromes without a centre marker are the standard witness. Nondeterminism is not a convenience at this level, it is a capability.

The other half of the context-free story is the grammar, and the two halves describe exactly the same class of languages: every context-free grammar has a pushdown automaton that recognizes what it generates, and every pushdown automaton has a grammar. A grammar is the generative view, and it is the one linguists actually use, which is where this project’s other thread comes back. Russian prefix stacking is finite-state, as the playground argues above, because morphology mostly is. Syntax is not. The classic demonstration is attachment: “I saw the man with the telescope” has two derivations, one where the prepositional phrase hangs off the verb and one where it hangs off the noun, and both are grammatical English. That is structural ambiguity, and a grammar that generates both is telling the truth about the sentence. Deciding whether a string is in the language is then a parsing problem, and CYK is the clean answer: convert the grammar to Chomsky normal form, where every rule is A→BCA \to BC or A→aA \to a, and fill an upper-triangular table in which cell (i,j)(i, j) holds every nonterminal deriving the substring of length jj starting at ii. Three nested loops, O(n3⋅∣G∣)O(n^3 \cdot |G|), and no backtracking anywhere.

Try

The grammar, as written

The classic ambiguous grammar: nothing in it says that × binds tighter than +, so a+a*a has two parse trees and the grammar declines to choose. Step through both.

The same grammar in Chomsky normal form

E₀ -> E X1 | E X2 | T( X3 | a
E -> E X1 | E X2 | T( X3 | a
X1 -> T+ E
X2 -> T* E
X3 -> E T)
T+ -> +
T* -> *
T( -> (
T) -> )

The table, filled bottom-up

a+a*a

ACCEPTED · 2 parses. Click any cell to see what put it there.

Parse tree 1 of 2

EEa+EEa*Ea

Symbols the conversion invented are folded away again, so this is a tree of the grammar as it was written, not of its normal form.

Plate VI CYK on whatever grammar you give it. The conversion to Chomsky normal form happens first and is shown, because it is worth seeing: ε-rules and renaming rules are not deleted, they are compiled into the rules that survive, and the stage list on the right says what each pass did. Then the table fills bottom-up, one cell per Step. Each cell spans exactly the tokens it covers, so the triangle is a picture of substrings rather than a square table pretending to be one; click any cell to see which rule and which split put each symbol there. The apex is the answer. The default grammar is ambiguous on purpose: a+a*a has two parse trees, and the tree view pages between them.

That is the middle of the hierarchy filled in, and it also explains the section that follows. One stack buys one depth of counting, and no more: { anbncn }\{\, a^n b^n c^n \,\} defeats a pushdown automaton for the same reason { anbn }\{\, a^n b^n \,\} defeats a finite automaton, and there is a pumping lemma one level up that says so. The copy language { ww }\{\, ww \,\} fails the same test, which is worth holding onto, because the next section is about a machine that decides exactly that language. TM3 needs a tape rather than a stack, and now the reason is visible instead of asserted: a stack can only be read in the order it was written, and checking that the second half of a string matches the first requires reading both halves forwards. Regular, then context-free, then decidable. Each level is the previous one plus one more kind of memory.

From the theory course: four Turing machines

The playground’s second family is a set of Turing machines I wrote for CSE 3502, the automata and computability course, and they climb a small ladder. TM0 decides { w#w:w∈{0,1}∗ }\{\, w \# w : w \in \{0,1\}^* \,\}, checking that a string is two identical halves split by a hash: it crosses off matching symbols from each side and rejects the moment they disagree. TM1 decides { w τ(w):w∈{0,1}∗ }\{\, w\,\tau(w) : w \in \{0,1\}^* \,\}, where τ\tau recodes 0 as 2 and 1 as 3, so 0123 is in the language (w=01w = 01, and 23 is exactly τ(01)\tau(01)). TM2 is a transducer rather than a decider: it computes a function, mapping the first half of an {a,b}\{a,b\} string to digits 0 and 1 and the second half to 2 and 3, and it halts on every input. TM3 then composes the two, running TM2 to recode its input and feeding the result into TM1, so the whole machine decides the copy language { ww:w∈{a,b}∗ }\{\, ww : w \in \{a,b\}^* \,\}, a canonical example of a language no finite automaton can recognize.

The machines are written in the tape-and-head notation of Anthony Morphett’s online simulator, one rule per line as (state) (read) (write) (move) (next-state), and the playground parses those tables directly. A Turing machine is a 7-tuple (Q,Σ,Γ,δ,q0,qaccept,qreject)(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}), and the formal-definition panel reads each component straight off the table: the states QQ, the input alphabet Σ\Sigma, the larger tape alphabet Γ\Gamma (which adds the blank and the scratch symbols the machine writes), and the two halting states. One subtlety worth calling out, because it is easy to misread as a bug: these are deciders written so that a missing rule counts as rejection. If the head reads a symbol for which the current state has no transition, the machine simply halts without ever reaching qacceptq_{\text{accept}}, and a halt outside the accepting state is a reject. The playground honors that, reporting “no rule” as a clean rejection rather than an error.

The approach

The Python repo is deliberately minimal: a single DFA class that takes the 5-tuple directly. The design choice I still like is that the transition function comes in as a set of (state,symbol,state)(\text{state}, \text{symbol}, \text{state}) triples (the way you’d write δ\delta on paper) and gets compiled into a nested dictionary for constant-time lookup. The constructor then refuses any machine whose table is not total, counting triples against ∣Q∣⋅∣Σ∣|Q| \cdot |\Sigma| to do it (with the error message “Nuh uh, not deterministic!”, which I stand by, and a counting rule the last section sharpens). Beyond runOn, which simulates a string, there’s enumerateTillLen(n): a breadth-first enumeration of every string over Σ\Sigma up to length nn, filtered through the machine, which is a brute-force way to see L(M)L(M) and one the last section improves on.

The browser playground rebuilds this as a visual instrument: place states on a canvas, mark them accepting, drag transitions between them, then type a string and watch a token walk the graph, stepping symbol by symbol or animating straight through, green on acceptance, red on rejection. It ships with preset machines, and the presets are where the linguistics comes in.

Finite-state machines are not just a theory-course warmup; they’re the standard industrial tool for morphology, the structure of words. Morphological analyzers for real languages are built as finite-state devices, because so much of word formation is regular in exactly the formal sense. My favorite test case is Russian verbal prefixes. Russian verbs take stacking prefixes (по-, пере-, вы-, за-, на-, до-, and more), and the stacking is constrained: some sequences are productive (colloquial Russian happily builds по-на-вы-думывать, roughly “to dream up a whole heap of”), while others are flatly ill-formed. Treat the prefixes themselves as the alphabet and the licit stacking stages as states, and the grammar of prefixation is a finite automaton you can draw, run, and argue with. Speaking Russian makes this alphabet a lot more fun to debug than {a,b}\{a, b\}.

From there, the docstring’s to-do list, now fully paid off across Plates II and III: NFAs (transition function δ:Q×Σε→P(Q)\delta : Q \times \Sigma_\varepsilon \to \mathcal{P}(Q)), the subset construction animated so you can watch determinization pay its worst-case 2∣Q∣2^{|Q|} price in real time, and regex → NFA compilation via Thompson’s construction, so a regular expression becomes a machine before your eyes. Thompson’s algorithm is a small marvel of compositionality: five rules, each adding at most two states, so a regex of length nn yields an NFA with O(n)O(n) states. And the pipeline regex → NFA → DFA (Plate III into Plate II) is, conceptually, how every grep you’ve ever run begins.

What the playground changes

The browser version is a second pass over the 2024 design, and two checks move to where they belong. Determinism is a property of the domain of δ\delta rather than of its size: the check that belongs in a constructor is that no (state, symbol) pair carries two targets, which is the condition itself, where comparing ∣δ∣|\delta| to ∣Q∣⋅∣Σ∣|Q| \cdot |\Sigma| only counts triples and can be satisfied by a table that is nondeterministic on one pair and silent on another. And input is validated at the boundary: a character outside Σ\Sigma is a clean rejection with a named reason rather than an exception, the same treatment the playground gives a missing rule on the Turing machines above, since a decider should have an answer for every string it can be handed. Both are one principle, that a machine’s contract is enforced at its edges, and both only matter off the happy path, which is exactly where a teaching instrument gets used.

The enumeration is the next thing to rebuild. enumerateTillLen generates all ∑k≤n∣Σ∣k\sum_{k \le n} |\Sigma|^k candidate strings and filters them, when walking the automaton’s own graph (enumerating paths from q0q_0, or counting accepted strings per state with dynamic programming) does the same job without materializing the exponential haystack. That is the version I would build next, and it is the quiet virtue of rebuilding old projects in public: the second version’s specification is written by reading the first.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.