# Context-sensitive grammar

A

**context-sensitive grammar** is a

formal grammar *G* = (

*N*, Σ,

*P*,

*S*) such that all rules in

*P* are of the form

- α
*A*β -> αγβ

with

*A* in

*N* (i.e.,

*A* is single nonterminal) and α and β in (

*N* U Σ)* (i.e., α and β strings of nonterminals and terminals) and γ in (

*N* U Σ)

^{+} (i.e., γ a nonempty string of nonterminals and terminals), plus that a rule of the form

- S -> ε

with ε the empty string, is allowed if S does not appear on the right side of any rule.

The adjective *context sensitive* is explained by the α and β that form then context of *A* and determine whether *A* can be replaced with γ or not. This is different from a context-free grammar where the context of a nonterminal is not taken into consideration. A formal language that can be described by a context-sensitive grammar is called a context-sensitive language.

The concept of context-sensitive grammar was introduced by Noam Chomsky in the 1950s as a way to describe the syntax of natural language where it is indeed often the case that a word may or may not be appropriate in a certain place depending upon the context.

Another definition of context-sensitive grammars defines them as formal grammars with the restriction that for all rules α -> β in *P* it holds that | α | ≤ | β | where | α | is the length of α. Such a grammar is also called a *noncontracting grammar* because none of the rules decreases the size of the string that is being rewritten.

While the noncontracting grammars are different from the context-sensitive ones, the two are *almost* equivalent in the sense that they define the same class of languages (except that noncontracting grammars can not generate any language that contains the empty string ε). But if a formal language *L* can be described by a grammar of the first definition then there is a noncontracting grammar that describes *L* - {ε}, and vice versa.

The decision problem that asks whether a certain string *s* belongs to the language of a certain context-sensitive grammar *G*, is PSPACE-complete. Indeed, there are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete.

**See also:** Chomsky hierarchy