识别 { 0ⁿ1ⁿ : n ≥ 1 }

父级：examples

finite automaton 无法识别的语言（没有计数能力），但图灵机可以——办法是把纸带当作无限内存来用。

思路：反复划掉最左边的 0（写成 X）与最右边的 1（写成 Y）；当两者同时耗尽时接受。

七元组（概要）。 Q = {seek0, seek1, back, check, accept}，q₀ = seek0，F = {accept}；Γ = {0,1,X,Y,b}，Σ = {0,1}。关键的 δ 转移：

δ(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

在 0011 上的执行轨迹：

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

（先划掉最外层的 0/1，再划掉内层的 0/1；全部标记完毕，无一剩余。）

在 001 上，多出来的那个 0 找不到可以匹配的 1 → 拒绝。X/Y 标记就是写在纸带上的计数器——正是有限自动机所缺乏的那种内存，这也是为什么这门语言至少需要一个栈（context-free-languages），而图灵机做起来则绰绰有余。