Collection · 20 machines · curated by @thethinkmachine
Beyond regular
Stacks, counters, queues and tapes: what each kind of memory buys. A stack counts and matches; a queue copies; two stacks are a Turing machine; a tape bounded by its input is exactly the context-sensitive languages.
Essay
A finite automaton cannot count past a fixed number, so it cannot check that a string is aⁿbⁿ. Give it memory that grows with the input and it can. What is interesting is that the shape of the memory decides what it can do — a stack, a counter, a queue, two stacks, a tape — and the differences are sharp, provable and visible in small machines.
A stack
A stack reverses, and matching is reversal: push on the way in, pop on the way out. That is enough for aⁿbⁿ, for balanced brackets of several kinds, and for a palindrome with its middle marked. Remove the marker and the machine must guess where the middle is — and here nondeterminism, which added nothing to finite automata, adds real power: no deterministic pushdown automaton recognises even-length palindromes. aⁿbⁿ or aⁿb²ⁿ is the standard example of a language every nondeterministic PDA can handle and no deterministic one can.
A stack cannot compare two things that come in the same order. The words ww — a string repeated — are not context-free. Their complement, oddly, is: not a word repeated twice guesses where two halves first differ.
A counter
A counter is a stack with one kind of symbol: it can count up, count down and test for zero. It is enough to validate reverse Polish notation, where only the depth of the evaluation stack matters, and too little for nested brackets of two kinds, where which bracket is open matters too.
A queue
A queue keeps things in arrival order, which is exactly what copying needs. Three copies, w#w#w checks the second copy while putting each symbol straight back for the third, and aⁿbⁿcⁿ with a queue counts three times by cycling the queue. A queue automaton is as powerful as a Turing machine.
Two stacks, a stack of stacks, a tape
Two stacks make a queue — pour one into the other and the order comes out right — and so two stacks are also as powerful as a Turing machine. Between one stack and two lies a stack of stacks, the embedded pushdown automaton, which recognises exactly the tree-adjoining languages: aⁿbⁿcⁿdⁿ, but not aⁿbⁿcⁿdⁿeⁿ.
Then the tape. A Turing machine restricted to the cells of its input is a linear bounded automaton, and those recognise exactly the context-sensitive languages. A one-tape Turing machine can check w#w by walking back and forth, in time proportional to n²; a second tape brings palindromes down to linear time.