The simplest computer
Before asking what a laptop can compute, theory asks what the simplest possible machine can compute. A turnstile, a vending machine and the part of a compiler that recognises numbers all work the same way: they are in one of a few states, they read one input at a time, and each input moves them to a next state. That's a finite automaton — finite because it has a fixed number of states and no other memory.
In this course you'll build the machines that theory of computation is founded on, in plain JavaScript, and test them on every string up to a given length. By the end you'll know which problems need only a few states, which need a stack, which need a full computer — and which no computer can ever solve.
A turnstile: Locked: a coin unlocks it, a push does nothing. Unlocked: a push lets you through and locks it again. Two states, two inputs, four arrows — and it never needs to remember anything else.
The five parts of a DFA
A DFA (deterministic finite automaton) is defined by five things: a set of states, an alphabet of input symbols, a transition function δ that says where to go from each state on each symbol, a start state, and a set of accept states. Deterministic means there is exactly one next state for every state and symbol — the machine never has to choose.
const EVEN_ONES = {
start: "even",
accept: ["even"],
delta: {
even: { 0: "even", 1: "odd" },
odd: { 0: "odd", 1: "even" },
},
};The set of all strings a machine accepts is called its language. EVEN_ONES recognises the language of binary strings with an even number of 1s — infinitely many strings, using just two states.