Finite State Machine Animator

step through DFA transitions on a live state diagram

Worked example — Finite State Machine Animator

Next symbol	'1'

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

finite memory, infinite strings 🖖

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.

one token, one path 🖖

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.

born from a model of neurons 🖖

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.

Problem solved in full

Why no finite machine can match up 0s and 1s, however many states you give it 8 steps
The parity machine on this page has two states, and it reads 101101, six symbols, without ever wanting a third. Hand it six million symbols and it still wants two. So what is it that a machine with a fixed number of states cannot do? And how do you prove a machine does not exist, rather than merely failing to find one?
1. Watch the machine you have. Parity starts in e, and every 1 flips it. Six symbols later it is back in e and the input is accepted. Nothing accumulated along the way: the machine at symbol six is in exactly the same condition it could have been in at symbol one.
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. That is the entire resource. A DFA’s memory is the state it is in and nothing else. No counter, no stack, no tape it can write on. After reading any prefix, everything the machine knows about that prefix is which of its k states it now occupies.
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. So find something that plainly needs more. Take the strings that are some number of zeros followed by exactly as many ones. 01 is one, 0011 is one, 001 is not, and neither is 0110.
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. Suppose a DFA with k states recognises it. Do not ask what the machine looks like — you are never going to be told. Just feed it the k+1 prefixes made of 0 through k zeros, and note where each one leaves it.
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. Pigeonhole. There are more prefixes than states, so two of them land in the same place. Call them 0ⁱ and 0ʲ with i smaller than j. From that moment the machine cannot tell them apart, and not because it is badly designed. The state is all it has, and the two strings gave it the same one.
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. Now feed both continuations the same thing: i ones. Same starting state, same symbols, so same finishing state, so the same verdict. There is no room for the machine to do anything else.
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. And the two verdicts have to differ. 0ⁱ1ⁱ has matching counts and belongs; 0ʲ1ⁱ does not, because j is not i. One must be accepted and the other refused, and the machine gives them the same answer. What breaks is the supposition it existed.
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. Read the argument again and notice what never appeared in it: a value of k. Two, the parity machine’s own size, or two billion: k+1 prefixes outnumber k states either way. Put a ceiling on n, though, and the language becomes finite-state at once: matching up to N needs 2N+2 states, so 22 for N = 10 and 202 for N = 100.
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
Answer

No finite automaton recognises it, at any size. The proof needs nothing about how the machine is built, only that k+1 things cannot sit in k places without two of them sharing, and that sharing a state is forgetting. The parity machine shows the same thing in miniature: feed it 0, then 00, then 000, and all three leave it in e, because it does not look at zeros at all.

The ceiling is where the whole difficulty lives. Matching up to N is easy, at 2N+2 states, one more pair for every symbol you want to reach, and that count grows without stopping, so every particular N has a machine and no machine has every N. That gap is what “finite memory” means, and it is why the next thing after a DFA is defined by handing it a stack: an unbounded store, added back precisely because this is what its absence costs.

References (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

By the 42Math team · Updated 2026-06-03

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

ends with 01 - Suffix recognizer accepts strings ending with 01.
rejected (ends 10) - Step to the end and the machine finishes in q1 and rejects, having sat in the accepting state q2 partway through. Reading a 01 somewhere in the middle is not the same as ending on one. A DFA's whole answer is the state after the last symbol, and it has no way to remember that it was ever anywhere better.
even ones ✓ - Parity automaton accepts binary strings with even ones.
odd ones ✗ - Three 1s in the input, and the parity machine flips on each of them: e, o, o, e, o. It ends in o and rejects. Nothing is being counted here. Two states are all it has and all it needs, because whether the count so far is odd is the entire fact worth remembering about a string of any length.
contains 101 ✓ - The machine reaches s3 on the fourth symbol and then cannot leave: s3 goes to s3 on a 0 and on a 1 alike. Three more symbols go by and the verdict has already been fixed for all of them. A trap state is how a DFA commits to yes before the input runs out, without storing anything about when it happened.
no 101 ✗ - Rejected in s2, which the legend calls “read 10 — one symbol away”. One more 1 on the end would have completed the pattern and locked the machine into s3 for good. The state you land in says how close you got, which the accept-or-reject bit on its own never can.