Context-Sensitive Rules and Why Non-Contracting Rewriting Is Decidable

A context-sensitive grammar relaxes the single-nonterminal restriction of context-free rules while keeping a different one: no rule may make the sentential form shorter. The relaxation adds the ability to inspect neighbours; the restriction is what preserves decidability. Understanding why requires looking at what a derivation of a fixed string can do when its length can never decrease.

The rule form and what it permits

Type 1 productions have the shape

αAβ → αγβ

where A is a nonterminal, α and β are strings over (V ∪ Σ), and γ ∈ (V ∪ Σ)⁺. The symbol A is rewritten to γ, but only when it sits between α and β. The left context α and the right context β are preserved verbatim; only the marked symbol changes. Equivalently, the rule may be written u → v for arbitrary nonempty u ∈ (V ∪ Σ)⁺ and v with |v| ≥ |u|, provided u contains at least one nonterminal. The two formulations generate the same class; the αAβ form is easier to reason about, and the u → v form is easier to use in examples.

Two consequences follow immediately. First, the length of the sentential form never decreases, because |αγβ| = |α| + |γ| + |β| ≥ |α| + 1 + |β| = |αAβ|. Second, the rewriting can move information sideways: a rule can copy the left context into γ, which is how counting agreements across three or more symbols become expressible.

The canonical example is {aⁿbⁿcⁿ : n ≥ 1}. A grammar for it uses context to relabel a’s and b’s in step. In outline, the rules first generate aⁿbⁿcⁿ with nonterminals marking the block structure, then a left-to-right sweep rewrites each marked a into a checked symbol while requiring a marked b to its right, and a second sweep does the same for b and c. Each sweep uses the context to carry the “how many have been consumed” information along the string. A context-free grammar cannot do this because the information must travel through the derivation, not through the string.

Why monotonicity makes membership decidable

Fix a grammar G in the u → v form and a target string w of length n. The membership question is whether S ⇒* w. Consider the set of sentential forms reachable from S whose length is at most n. Every such form is a string over the finite alphabet V ∪ Σ of length at most n, so there are at most

Σ_{k=0}^{n} |V ∪ Σ|ᵏ

of them, a finite number depending only on G and n. Since derivations never shorten, any derivation of w stays inside this finite set. If w is derivable, there is a derivation visiting only forms of length at most n, and the shortest such derivation visits no form twice — a repeated form would allow the intervening steps to be deleted, yielding a shorter derivation of the same string. So the search can be bounded: explore the reachable set, and if w is not reached, it is not in the language.

This is a decision procedure in principle, and a hopeless one in practice. The reachable set is exponential in n, and the number of derivations to explore is worse. The theoretical significance is that the search terminates for every input, which places the class inside the decidable languages. The practical significance is that no one implements membership this way; the connection to linear-bounded automata gives a better algorithm, and even that is exponential in the worst case.

The corresponding machine is the linear-bounded automaton: a nondeterministic Turing machine whose tape is the input region plus two end markers, with the head confined between them. A configuration is a state, a head position, and a tape content, all bounded by the input length, so the number of configurations is finite and a run either halts or repeats. That is the same finiteness argument in machine form, and the equivalence of the two formalisms is a pair of compilations in both directions.

Kuroda normal form and the size of the translation

Every context-sensitive grammar can be converted to Kuroda normal form, in which every rule is one of

A → a      A → B      A → BC      AB → CD

with A, B, C, D nonterminals and a a terminal. The first three forms are context-free; the fourth is the context-sensitive one, and it rewrites a pair of adjacent nonterminals into another pair. No rule in the normal form has a context longer than one symbol on each side, and no rule produces more than two symbols.

The conversion is a sequence of eliminations analogous to the Chomsky normal form construction. Long left sides are broken up with fresh nonterminals that carry position information; long right sides are split; terminals are isolated. The blow-up is polynomial in the grammar size, and the language is preserved exactly.

The reason the pair-rewriting form is enough is that any context-sensitive rule can be simulated by a sequence of pair rewrites that first mark the left context, then rewrite the marked symbol, then unmark. Each step touches at most two adjacent symbols, so each is expressible as AB → CD. The construction is the grammar-level analogue of a Turing machine implementing a multi-symbol rewrite as a sequence of single-cell writes with head motion.

Kuroda normal form is the standard input format for theoretical results about the class, in the same way Chomsky normal form is for context-free languages. Its practical use is limited because context-sensitive grammars are rarely written by hand, but it is the form in which the equivalence with linear-bounded automata is usually proved.

The space-complexity characterisation

The class of context-sensitive languages equals NSPACE(n), the languages decided by a nondeterministic Turing machine using O(n) tape cells. The forward direction is the linear-bounded automaton construction. The reverse direction compiles a machine’s computation into a grammar: nonterminals encode a state, a head position, and a tape symbol at a position, and rules simulate a transition while preserving the neighbouring cells. Because the tape is bounded by c·n, the grammar can be constructed with a context that carries the machine state along the tape.

The Immerman–Szelepcsényi theorem then applies: nondeterministic space classes are closed under complement. Since NSPACE(n) is closed under complement, the context-sensitive languages are closed under complement. This is a nontrivial closure property, and it is the point where type 1 separates sharply from type 2. The complement of a context-free language need not be context-free, as Closure Gaps in Context-Free Languages sets out; the complement of a context-sensitive language is always context-sensitive.

The proof of Immerman–Szelepcsényi is an inductive counting argument: a nondeterministic machine can compute how many configurations are reachable within a given number of steps, using the count itself to verify that no configuration has been missed. The technique is called inductive counting, and it works because a nondeterministic machine can guess a set of configurations and then verify both that every guessed configuration is reachable and that the count is complete, all within the same space bound. The argument is not constructive in a way that yields small grammars, but it is effective, so complementation is a computable operation on grammars even though the construction is enormous.

What context sensitivity costs in practice

Context-sensitive grammars are expressive enough for many natural-language and program-language phenomena that context-free grammars cannot handle: agreement between a verb and a subject that may be arbitrarily far away, cross-serial dependencies in some languages, and the requirement that a program’s identifiers be declared before use in a way that depends on the surrounding scope structure.

They are also undecidable in the ways that matter for tools. Emptiness is undecidable, by a reduction from the halting problem: for a Turing machine M and an input w one can construct a linear-bounded automaton whose language is exactly the set of accepting computation histories of M on w, and that language is nonempty precisely when M halts on w. Non-contraction bounds each intermediate form relative to the target string, not the length of the target itself, so it does not make the search for any terminal string finite. Equivalence is undecidable too — every context-free grammar is also a context-sensitive one, so a decision procedure for the class would decide the context-free equivalence problem — and universality is undecidable as well, being emptiness of the complement, since the class is closed under complement. The closure properties are better than type 2 — union, intersection, complement, concatenation, and star all preserve the class — while the decision problems are worse. That combination, good closure and bad decidability, is the signature of a class that is useful for specification and useless for automated analysis.

The recognition cost is the binding constraint. A linear-bounded automaton can be simulated directly, which costs time exponential in the input length in the worst case, because the number of configurations is exponential and the simulation may explore all of them. No polynomial-time algorithm is known for general context-sensitive membership, and the problem is PSPACE-complete when the grammar is part of the input. For fixed grammars, membership is in NSPACE(n) and therefore in PSPACE, and the practical algorithms are backtracking searches over the tape, which behave well on structured inputs and badly on adversarial ones.

The design lesson is the one The Chomsky Hierarchy as a Ladder of Memory draws in general: a formalism that can inspect context can express agreements that context-free grammars cannot, and the price is a decision procedure that is finite but not fast. Context-sensitive grammars sit at the exact point where the theory still guarantees termination and the engineering has already given up on efficiency.