Recognizing { 0ⁿ1ⁿ : n ≥ 1 }

Parent: examples

The language a finite automaton cannot recognize (no counting) but a Turing machine can — by using the tape as unbounded memory.

Idea: repeatedly cross off the leftmost 0 (write X) and the rightmost 1 (write Y); accept iff they run out together.

The 7-tuple (sketch). Q = {seek0, seek1, back, check, accept}, q₀ = seek0, F = {accept}; Γ = {0,1,X,Y,b}, Σ = {0,1}. Key δ moves:

δ(seek0, 0) = (seek1, X, R)     mark a 0, go find its matching 1
δ(seek0, Y) = (check, Y, R)     no 0s left -> verify no 1s remain
δ(seek1, 1) = (back,  Y, L)     mark the rightmost 1, walk back
δ(back,  X) = (seek0, X, R)     returned to the marks -> repeat
δ(check, b) = (accept, b, R)    everything matched -> accept

Trace on 0011:

0 0 1 1   ->   X 0 1 1   ->   X 0 1 Y   ->   X X 1 Y   ->   X X Y Y   -> accept

(cross outer 0/1, then inner 0/1; all marked, none left over.)

On 001 the extra 0 finds no 1 to match → reject. The X/Y marks are a counter written on the tape — exactly the memory a finite automaton lacks, which is why this language forces at least a stack (context-free-languages) and a TM does it comfortably.