Type 1 — context-sensitive languages (bounded tape)
Parent: chomsky-hierarchy
A Turing machine whose tape is bounded by the input length — a linear-bounded automaton (LBA). Full random-access memory, but a finite amount of it.
- Grammar: context-sensitive — non-contracting productions
αAβ → αγβ(|γ|≥1); the contextα,βaroundAmatters. - Automaton: LBA =
NSPACE(n). - Examples:
aⁿbⁿcⁿandaⁿbⁿcⁿdⁿ(multiple coordinated counts); the copy languageww(checking two arbitrary halves match);{ aⁿ : n prime }and{ aⁿ : n = 2ᵏ }(arithmetic conditions on the length); and the linguists' favourite — cross-serial dependencies (Swiss-German…aabb…-stylewwʼpatterns), the empirical evidence that some natural language is beyond context-free, sitting in the "mildly context-sensitive" band (Chomsky's motivation).
The key fact — still decidable.
Membership is decidableAn LBA has only finitely many configurations (bounded tape × states × head positions), so a run either halts or provably loops — membership is decidable (in
PSPACE).
This is the last decidable tier. (Fine print: NSPACE = coNSPACE by Immerman–Szelepcsényi, so CS languages are closed under complement; whether deterministic LBA = nondeterministic LBA is the open LBA problem.)
But not everything is decidable even here: emptiness of a context-sensitive language is undecidable. One step further — unbounded tape — and even membership goes (recursively-enumerable-languages).