A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Context-sensitive languages (Type 1) are generated by grammars with productions of the form αAβ → αγβ where γ is non-empty, ensuring string length never decreases. These languages strictly contain context-free languages yet are properly contained in recursively enumerable languages. Context-sensitive corresponds to linear-bounded automata—machines with tape bounded linearly by input length—capturing problems solvable with controlled memory resources.
You know from the Chomsky hierarchy that formal languages are organized into a nested sequence of increasingly powerful classes, and you understand context-free grammars (Type 2), which generate languages like balanced parentheses and arithmetic expressions. Context-sensitive languages (Type 1) sit one level above context-free in that hierarchy, capturing patterns that context-free grammars fundamentally cannot express.
The defining feature is in the name: productions are context-sensitive. In a context-free grammar, a production like `A → γ` says "replace `A` with `γ` regardless of what surrounds `A`." In a context-sensitive grammar, a production takes the form `αAβ → αγβ`, meaning "`A` can be replaced by `γ`, but only when `A` appears between `α` and `β`." The surrounding strings α and β provide the *context* that determines whether the rule applies. There is one additional constraint: `γ` must be non-empty, which guarantees that strings never shrink during derivation. This non-shrinking property is what separates context-sensitive grammars from the fully general unrestricted (Type 0) grammars.
The classic example of a context-sensitive language is `{aⁿbⁿcⁿ | n ≥ 1}` — strings with equal numbers of a's, b's, and c's in order. You may recall proving (via the pumping lemma) that this language is not context-free: no pushdown automaton can track three linked counts simultaneously. A context-sensitive grammar handles it by using context to coordinate the growth of all three regions together. This illustrates the additional power: context-sensitive grammars can enforce dependencies between distant parts of a string that context-free grammars cannot.
The machine model equivalent to context-sensitive grammars is the linear-bounded automaton (LBA) — a nondeterministic Turing machine whose tape is restricted to be at most a constant multiple of the input length. Where a pushdown automaton has a single stack (enough for one counter), an LBA has a full read-write tape, but bounded in size. This bounded tape is enough to handle the coordination problems that defeat pushdown automata, yet not so powerful as an unrestricted Turing machine with unbounded tape. The correspondence is exact: a language is context-sensitive if and only if it is accepted by some LBA. This makes context-sensitive languages the class of problems solvable with linear memory — a natural and important resource bound that sits between the stack-based memory of context-free parsing and the unlimited memory of general computation.