Finite Automata (DFA)

What is the simplest possible computer? Strip away the hard drive, the RAM, the operating system. What is the bare minimum you need to recognize a pattern? The answer is a DFA: a deterministic finite automaton. It reads input one symbol at a time, left to right, and carries nothing but a single state. No memory. No scratch space. Just a state and a set of rules for what to do next. related

Formally, it is a five-tuple $(Q,\Sigma,\delta,q_0,F)$: a finite set of states $Q$, an alphabet $\Sigma$, a transition function $\delta$ that says where to go next, a start state $q_0$, and a set of accepting states $F$. But the formalism hides how elegant the idea really is.

Below is a DFA that accepts exactly the binary strings with an even number of 1s. Watch the tape and the highlighted state together. The machine remembers only one thing: the parity of the 1s it has seen so far. That is all it needs. Limited memory, instant decisions.

Kleene and others developed these automata in the 1950s to formalize what a “regular pattern” is. DFAs are fast and elegant, but they have a hard ceiling: they cannot count without bound. Try designing a DFA that checks whether a string has equal numbers of 0s and 1s. You will not succeed; that requires unbounded memory. For that, you need a stack (pushdown automata) or a full tape (Turing machines).

Turing Machines

In 1936, a 23-year-old Alan Turing sat down to answer one of the deepest questions in mathematics: what does it mean to compute something? His answer was not a proof or a theorem. It was a machine. An imaginary one, built from the simplest possible ingredients: an infinitely long tape of symbols, a head that can read and write one cell at a time, and a finite set of rules telling it what to do next. That is it. No keyboard, no screen, no memory chips. And yet this bare-bones device turned out to be capable of computing anything that any computer can compute. Every app on your phone, every neural network, every algorithm ever written: all of it can, in principle, be run on Turing’s imagined machine.

Formally, it is a seven-tuple $(Q,\Gamma,\Sigma,\delta,q_0,q_{acc},q_{rej})$: states $Q$, tape alphabet $\Gamma$, input alphabet $\Sigma\subseteq\Gamma$, and $\delta$ mapping $(\text{state},\text{symbol})$ to $(\text{write},\text{move},\text{next state})$. The formula is precise. The implication is staggering.

Below is a tiny program that increments a unary number (a run of 1s). It walks right over the 1s until it finds a blank, writes a 1, and halts. Simple, almost trivially so. But watch the head moving, the tape being modified, the halt condition. This is exactly how every computation works at its core: read, decide, write, move, repeat.

Turing’s 1936 paper, “On Computable Numbers,” did not just define a machine. It drew a line around what is computable and what is not. He proved that there exist well-defined mathematical questions that no algorithm can ever answer (the halting problem). The surprising part is not that computation is powerful. The surprising part is how little you need: a finite control and a long enough tape. Everything else is engineering.

What Languages These Machines Recognize

One of the most beautiful results in all of computer science is this: these machines form a perfect hierarchy, and each level corresponds to a fundamentally different kind of memory.

At the bottom: DFAs, with no memory at all beyond their current state. They recognize the regular languages, patterns where you never need to count past some fixed limit. Add a single stack, and you get a pushdown automaton that can match opens with closes, handling context-free languages like balanced parentheses and the grammar of programming languages. Give a machine a full read/write tape, and you leap to Turing machines, which can simulate any algorithm we know how to write.

Each level is strictly more powerful than the last. No DFA, however cleverly designed, can check that parentheses are balanced. No PDA can verify that a string has equal numbers of a’s, b’s, and c’s ($a^n b^n c^n$). But a Turing machine handles all of these without breaking a sweat. The hierarchy is really a hierarchy of memory: no memory, a stack, a tape. And the question “what kind of memory do you need?” turns out to be one of the deepest questions you can ask about a problem.

Build a DFA

Your turn. Click “Add state” and drop a few nodes on the canvas. Choose a start, toggle which states accept, and wire them together with transitions. Do not worry about getting it right on the first try; half the fun is watching your machine do something unexpected and figuring out why. Enter an input string and step through. The highlight shows where the machine is; acceptance means ending in an accepting state with all input consumed.

Challenge: try building a DFA for strings over {0,1} that end with “01”. You will need three states. Ask yourself: where does the machine store “I just saw a 0”? That question is the whole game. Every DFA you design is really a question about what information is worth remembering.

Pushdown Automaton (Balanced Parentheses)

A DFA cannot count. That is its fundamental limitation. But what if we gave it just a tiny bit of memory? Not a hard drive. Not even random access memory. Just a stack: a pile of symbols where you can only touch the top, like a stack of plates in a cafeteria. You can put a plate on top, or take the top plate off. That is all. And yet this small addition unlocks an entirely new class of languages.

Here we use a PDA to check balanced parentheses, the classic example. Read '(' and push it onto the stack. Read ')' and pop. If you try to pop from an empty stack, reject immediately: too many closing parens. If the input ends and the stack is empty, accept: every open had a close. Watch the stack grow and shrink as you step through.

Try adding a stray ‘)’ in the middle of the string and step through. The pop fails and the PDA rejects immediately. That is the stack doing its job: it remembers exactly how many unmatched opens are pending, and it refuses to go negative. Every compiler you have ever used runs a version of this algorithm to check your code’s brackets.

Edit a Turing Program

This is where you get real power. The text box below is a Turing machine program, and you can rewrite it entirely. Each line is an instruction: given a state and a symbol under the head, write something, move left or right (or stay), and transition to a new state. The format is q0,1 -> 1,R,q0. You can add as many states as you like. You can make the machine loop, search, copy, compare. Anything computable is within reach. Try modifying the default increment program, or write something new from scratch. What happens if you make it move left instead of right? What if you add a second state that acts differently?