Finite State Machine Animator

A finite automaton has fixed memory — its state set. No matter how long the input string, the machine never uses more memory than its number of states. This is why DFAs cannot count unboundedly: there is no state that 'remembers' an arbitrary integer. The pumping lemma makes this precise — any sufficiently long string accepted by a DFA can have a middle section repeated arbitrarily many times and still be accepted. Languages that cannot be pumped (like aⁿbⁿ, equal counts of a and b) need a pushdown automaton or Turing machine. The Myhill-Nerode theorem gives the exact minimum: the number of states equals the number of distinguishable equivalence classes of input prefixes.

A deterministic finite automaton is just a labeled diagram of states connected by arrows. For every state and every input symbol there is exactly one arrow to follow, so there is never a choice to make — the machine reads the string once, left to right, and lands in a single state. If that final state is marked as accepting, the input belongs to the language. Tracing it is as simple as sliding a token along the arrows, which is exactly what this tool lets you watch.

Finite automata did not start in computer science. In 1943 Warren McCulloch and Walter Pitts described neurons as simple on/off units wired together, and this became the first mathematical model of a finite-state machine. In 1951 Stephen Kleene analysed exactly which patterns such 'nerve nets' could recognise, naming them regular events — the origin of today's regular expressions. So the DFA you are stepping through descends directly from an attempt to explain how the brain computes.