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 α,β around A matters.
• Automaton: LBA = NSPACE(n).
• Examples: aⁿbⁿcⁿ and aⁿbⁿcⁿdⁿ (multiple coordinated counts); the copy language ww (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…-style wwʼ 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 decidable

An 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).