Context-sensitive language

Context-sensitive languages are defined by grammars whose productions preserve, or under a restricted convention may exceptionally remove, sentential-form length. A typical context-sensitive production has the form αAβ → αγβ, where the nonterminal A can be rewritten as γ only in the surrounding context α and β; γ must be nonempty. Equivalently, one commonly defines the grammars as noncontracting grammars, in which the right-hand side is at least as long as the left-hand side.¹

In the Chomsky hierarchy, the class is called type 1. It properly contains the context-free languages, which use productions such as A → γ without requiring neighboring symbols, and is properly contained in the recursively enumerable languages. The hierarchy compares generative power, not the practical quality or speed of every parser.²

The machine counterpart of a context-sensitive language is a linear-bounded automaton. A linear-bounded automaton is a nondeterministic Turing machine whose usable tape is bounded by a constant multiple of the input length, so its computation remains within a linearly sized region.³

The grammar–automaton correspondence is a central result of formal language theory: languages accepted by nondeterministic linear-bounded automata coincide, subject to the conventional treatment of the empty string, with context-sensitive languages.¹ This characterization explains the class’s name in computational terms. It can express dependencies requiring more than a stack, such as the equal-count language {aⁿbⁿcⁿ | n ≥ 1}, while still restricting computation to linear space. The correspondence is mainly theoretical; general-purpose parsing for this class is substantially more difficult than parsing context-free grammars.

Context-sensitive languages are closed under several operations that preserve their bounded-space character. They are closed under union, intersection, concatenation, and nonempty Kleene plus; they are also closed under complement, a result associated with the nondeterministic space theorem for linear space.²

The language {aⁿbⁿcⁿ | n ≥ 1} is the standard separating example: it is context-sensitive but not context-free because recognizing it requires coordinating three unbounded counts rather than matching a single nested dependency. Other examples can encode synchronized copying, bounded workspace computations, and restrictions on multiple regions of a string. Closure does not mean that every natural transformation preserves the class: erasing operations and unrestricted grammar manipulations require care, while nonerasing homomorphisms and inverse homomorphisms fit the usual closure theory.

The treatment of the empty string is a technical exception that distinguishes textbook definitions. A noncontracting grammar cannot derive ε through an ordinary length-decreasing rule, so definitions commonly permit S → ε only when the start symbol S never appears on a production’s right-hand side. This convention keeps the grammar formulation aligned with the linear-bounded-automaton characterization without changing the main hierarchy.³

“Context-sensitive” does not mean that a word’s meaning depends on conversational context; here, context is the neighboring material surrounding a nonterminal during derivation. The class also illustrates a broader methodological point: grammar form, automaton space, and closure properties describe the same computational boundary from different perspectives. Although the model is rarely used directly for everyday parsing, it provides a precise benchmark for languages involving several simultaneous, linearly bounded dependencies.¹

Context-sensitive grammar

A grammar whose productions preserve length, or rewrite a nonterminal only within specified surrounding context, with a restricted exception for the empty string.

Chomsky hierarchy

A classification of formal grammars into regular, context-free, context-sensitive, and recursively enumerable levels.

Linear-bounded automaton

A nondeterministic Turing machine whose tape usage is bounded linearly by the input length.

Noncontracting grammar

A grammar in which no production decreases the length of the sentential form, apart from a conventional start-symbol exception.

Closure property

A statement that a language class remains within the class after an operation such as union, intersection, or complement.