Library

LBA · Context-sensitive

aⁿbⁿcⁿ in the space of its input

The standard context-sensitive language, decided without a single extra cell: check the shape a*b*c*, then cross off one a, one b and one c per pass. A linear bounded automaton is exactly this — a Turing machine that may not leave its input.

f0f1f2f3rwroundfindBtailaccfindCret⊢ → ⊢, Ra → a, Rb → b, Rc → c, R⊣ → ⊣, Lb → b, Rc → c, R⊣ → ⊣, Lc → c, R⊣ → ⊣, La → a, Lb → b, Lc → c, L⊢ → ⊢, Rx → x, Ra → x, Ry → y, R⊣ → ⊣, Sa → a, Ry → y, Rb → y, Rb → b, Rz → z, Rc → z, La → a, Lb → b, Lc → c, Lx → x, Ly → y, Lz → z, L⊢ → ⊢, Ry → y, Rz → z, R⊣ → ⊣, S
The machine as drawn — 11 states, 34 transitions.

The author’s examples, run

ε → acceptabc → acceptaabbcc → acceptaaaabbbbcccc → accepta → rejectbbc → rejectbabbcc → rejectbaaabbbbcccc → reject