Case Study · CS Theory · Linguistics
Automaton Playground
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
where is a finite set of states, a finite alphabet, the transition function, the start state, and the accepting states. Extend to whole strings by and , and the language the machine recognizes is
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”
| state | a | b |
|---|---|---|
| → ◎ q0 | q1 | q0 |
| q1 | q0 | q1 |
→ 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.
Build a string with the symbol keys, then Step or Run.
NFA transition table; “Strings ending in “ab””
| state | a | b | ε |
|---|---|---|---|
| → 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.
NFA
Determinized DFA
Build a string, then Step or Run; every state the NFA could be in glows at once.
Thompson's construction; the complete rule set
| construct | gadget |
|---|---|
| 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.
Two groups: accepting and the rest. Split until stable.
| state | a | b | accept |
|---|---|---|---|
| A | B | A | |
| B | D | C | |
| C | B | A | ✓ |
| D | D | E | |
| E | D | A | ✓ |
Initial partition: 2 groups (accepting vs non-accepting).
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 : 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 states, reading , 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 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 , there exists a string, for every decomposition, there exists an ), 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 , and the only line that matters is : 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”
| state | read | pop | push | next |
|---|---|---|---|---|
| → ◎ 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.
Stack
Pick a string, then Step or Run.
| state | read | pop | push | next |
|---|
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, , 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 or , and fill an upper-triangular table in which cell holds every nonterminal deriving the substring of length starting at . Three nested loops, , and no backtracking anywhere.
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) -> )
- START
- E₀ is new: the old start symbol appears on a right-hand side, so it cannot also be the top of the derivation.
- TERM
- 4 terminals lifted into T+, T*, T(, T), so no terminal is left sharing a rule with anything else.
- BIN
- 3 link symbols added: a rule with k symbols on the right becomes a chain of k − 1 binary rules.
- DEL
- Nothing to do: no symbol derives ε.
- UNIT
- 1 rule of the form A -> B removed (E₀ -> E); each left-hand side inherits the rules of everything it could become.
- TRIM
- Nothing to do: every symbol is both reachable and able to derive a string.
The table, filled bottom-up
ACCEPTED · 2 parses. Click any cell to see what put it there.
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.
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: defeats a pushdown automaton for the same reason defeats a finite automaton, and there is a pumping lemma one level up that says so. The copy language 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
, 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 , where recodes 0 as 2 and 1 as 3,
so 0123 is in the language (, and 23 is exactly ). TM2 is a transducer
rather than a decider: it computes a function, mapping the first half of an 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 , 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
, and the formal-definition
panel reads each component straight off the table: the states , the input alphabet , the
larger tape alphabet (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 , 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
triples (the way you’d write 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
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 up to length , filtered through the machine, which is a brute-force way to
see 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 .
From there, the docstring’s to-do list, now fully paid off across Plates II and III: NFAs (transition function ), the subset construction animated so you can watch determinization pay its worst-case 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 yields an NFA with 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 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 to 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 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
candidate strings and filters them, when walking the automaton’s own
graph (enumerating paths from , 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.