Back to home

Automata & Formal Languages

Five machines, each one step more powerful than the last. All of them are C++ compiled to WebAssembly, running inside your browser — nothing is sent to the server to make them work.

NFA — Non-deterministic Finite Automaton

Accepts a string only if it ENDS IN "ab".

What this machine checks

This machine is built to accept a string only if it ends in "ab". Nothing else.

Take "aab". It starts in q0. On the first 'a' the machine does something a DFA cannot: it goes to BOTH q0 and q1 at once — staying in q0 means "still scanning", moving to q1 means "guessing this 'a' starts the final ab". The second 'a' keeps both alive. Then 'b' takes q1 to q2, the accepting state, while q0 loops back to itself. We end with q2 among the active states, so the string is accepted.

Try "abb" and watch q2 light up in the middle and then go dark — the string contained "ab", but it did not END with it.

  1. 1.Type a string of a's and b's, e.g. a b b a b
  2. 2.Press Run
  3. 3.Watch every active state light up at once — an NFA explores all possibilities together
Loading the machine definition…

What the code is doing under the hood

The core is a TRANSITION TABLE, not a chain of if-statements. The loop does one lookup per character — current state plus current character gives the next state — and there is a single if at the very end asking whether the state we landed in is an accepting one. Swap the table and the same code recognises a different language.

What an NFA adds on top of that same core: the lookup returns a SET of possible next states instead of one, so the code carries a set forward instead of a single state. There is no backtracking and no re-running — all branches advance together, one step per character.

Code card

Run this demo to see the code that executed.

DFA — Deterministic Finite Automaton

Accepts a string only if it contains an EVEN NUMBER OF b's.

What this machine checks

This machine accepts a string only if the number of b's in it is even. Zero counts as even, so the empty string is accepted.

Take "abba". It starts in `even`. The 'a' changes nothing, so it stays in `even`. The first 'b' flips it to `odd`. The second 'b' flips it back to `even`. The final 'a' changes nothing. We finish in `even`, which is an accepting state, so the string is accepted — and indeed it has two b's.

Now try "ab": one b leaves the machine in `odd`, which is not accepting, so it is rejected.

  1. 1.Type a string of a's and b's, e.g. a b b a
  2. 2.Press Run
  3. 3.Watch the single active state move — a DFA is only ever in one place
Loading the machine definition…

What the code is doing under the hood

The core is a TRANSITION TABLE, not a chain of if-statements. The loop does one lookup per character — current state plus current character gives the next state — and there is a single if at the very end asking whether the state we landed in is an accepting one. Swap the table and the same code recognises a different language.

A DFA is the base case: exactly one next state per lookup, so the machine is only ever in one place. Everything below adds a capability on top of this same loop.

Code card

Run this demo to see the code that executed.

DFA minimisation

Four states reduced to the two that are actually needed.

What this demo checks

The machine on the left recognises the same language as the DFA above — even number of b's — but does it with four states instead of two. Two of them are redundant.

Minimisation starts by splitting the states into accepting and rejecting, because those can never be equivalent. Then it repeatedly asks: within a group, do all the members send every input symbol to the same group? If not, the group splits. When no group splits any more, each remaining group is one state of the smallest possible machine. Here A and C turn out to be the same state wearing two names, and so do B and D.

  1. 1.There is nothing to type — the machine is fixed
  2. 2.Press Run
  3. 3.Watch the partition refine round by round until it stops changing

Before — ? states

Loading…

After — press Run

The minimised machine appears here

What the code is doing under the hood

This is partition refinement, not a table lookup — it operates on the table rather than running it. Each round computes a signature for every state (which block does each symbol lead to?) and groups states by that signature. Identical signatures mean indistinguishable states.

It terminates because a partition can only ever get finer, and there are finitely many states to split.

Code card

Run this demo to see the code that executed.

PDA — Pushdown Automaton

Accepts only BALANCED BRACKETS.

What this machine checks

This machine accepts a string only if its brackets are balanced: every "(" is eventually closed, and a ")" never arrives before there is something to close.

Take "(())". Each "(" pushes a marker onto the stack, so the depth climbs to 2. Each ")" pops one off, so the depth falls back to 0. The string ends with an empty stack, which is the acceptance condition.

Try ")(" — the very first character tries to pop from an empty stack, and the machine rejects immediately. Try "(()" — it survives to the end but finishes with one bracket still open, so the stack is not empty and it is rejected.

No finite automaton can do this. Counting brackets needs unbounded memory, and a fixed set of states cannot count arbitrarily high.

  1. 1.Type a string of brackets, e.g. ( ( ) )
  2. 2.Press Run
  3. 3.Watch the stack rise and fall — the memory a finite automaton does not have
Loading the machine definition…

What the code is doing under the hood

The core is a TRANSITION TABLE, not a chain of if-statements. The loop does one lookup per character — current state plus current character gives the next state — and there is a single if at the very end asking whether the state we landed in is an accepting one. Swap the table and the same code recognises a different language.

What a PDA adds: the same lookup also names a stack operation — push or pop — and acceptance additionally requires the stack to be empty at the end. One control state, and all of the actual memory on the stack.

Code card

Run this demo to see the code that executed.

Turing machine

BINARY INCREMENT — adds one to the number on the tape.

What this machine checks

This machine adds 1 to whatever binary number is written on its tape.

Take "1011", which is 11 in decimal. The head first walks right until it falls off the end of the number, then steps back onto the last digit and starts adding. That digit is a 1, so 1 + 1 = 10: it writes 0 and carries, moving left. The next digit is also 1, so again write 0 and carry. The next is 0, so 0 + carry = 1: it writes 1 and stops. The tape now reads "1100" — which is 12.

Try "111". Every digit carries, the machine runs off the left end of the number, and writes a fresh 1 into the blank cell: "1000", which is 8.

  1. 1.Type a binary number, e.g. 1 0 1 1
  2. 2.Press Run
  3. 3.Watch the head walk right, then come back left rewriting digits
Loading the machine definition…

What the code is doing under the hood

The core is a TRANSITION TABLE, not a chain of if-statements. The loop does one lookup per character — current state plus current character gives the next state — and there is a single if at the very end asking whether the state we landed in is an accepting one. Swap the table and the same code recognises a different language.

What a Turing machine adds: the lookup also specifies a HEAD DIRECTION, left or right, and a symbol to write. The tape is read-write and unbounded, so unlike a stack the machine can revisit any cell in any order. That is the whole difference between a pushdown automaton and a machine that can compute anything computable.

Code card

Run this demo to see the code that executed.