S = start symbol A = first left bookend B = second left bookend C = third left bookend D = first right bookend E = second right bookend X = first token R = runner Y = second token (moves left) Z = third token (moves right) S -> AD generate first bookends A -> AX | B generate n X's for some n, then turn into second bookend B -> CR generate runner RX -> YXR generate one Y for each X, n Y's altogether RD -> D absorb runner XY -> YX move Y leftward past X ZY -> YZ move Y leftward past Z CY -> CZ each Y changes to Z, n Z's altogether ZX -> 1XZ generate 1 each time a Z passes an X, n^2 1's altogether Z1 -> 1Z move Z rightward past 1 ZD -> D absorb Z after it's done its job D -> E turn into second bookend X1 -> 1X move X rightward past 1 XE -> E absorb X C -> empty erase left bookend E -> empty erase right bookend Here's how to generate strings for n = 0, n = 1, and n = 2: S => AD => BD => CRD => CD => CE => E => empty S => AD => AXD => BXD => CRXD => CYXRD => CYXD => CZXD => C1XZD => C1XD => C1XE => C1E => 1E => 1 S => AD => AXD => AXXD => BXXD => CRXXD => CYXRXD => CYXYXRD => CYXYXD => CZXYXD => CZYXXD => CYZXXD => CZZXXD => CZ1XZXD => CZ1X1XZD => CZ1X1XD => C1ZX1XD => C11XZ1XD => C11X1ZXD => C11X11XZD => C11X11XD => C11X11XE => C11X11E => C111X1E => C1111XE => C1111E => 1111E => 1111