A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols.
Thus, CSGs are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.
[1] A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language.
[6][7] This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963.
[8][9] Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is often the case that a word may or may not be appropriate in a certain place depending on the context.
Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar.
[10] Although it is well known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open question how much of CSGs' expressive power is needed to capture the context sensitivity found in natural languages.
Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages.
[citation needed] The syntaxes of some visual programming languages can be described by context-sensitive graph grammars.
The language of the grammar G is the set of all terminal-symbol strings derivable from its start symbol, formally:
Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to L(G).
[note 3] The name context-sensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not.
By contrast, in a context-free grammar, no context is present: the left hand side of every production rule is just a nonterminal.
The left-context- and right-context-sensitive grammars are defined by restricting the rules to just the form αA → αγ and to just Aβ → γβ, respectively.
A generation chain for aaabbbccc is: More complicated grammars can be used to parse { anbncndn | n ≥ 1 }, and other languages with even more letters.
Here we show a simpler approach using non-contracting grammars:[citation needed] Start with a kernel of regular productions generating the sentential forms
[citation needed] A noncontracting grammar for the language { a2i | i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979):[15] Every context-sensitive grammar which does not generate the empty string can be transformed into a weakly equivalent one in Kuroda normal form.
"Weakly equivalent" here means that the two grammars generate the same language.
The normal form will not in general be context-sensitive, but will be a noncontracting grammar.
A formal language can be described by a context-sensitive grammar if and only if it is accepted by some linear bounded automaton (LBA).
[18] In some textbooks this result is attributed solely to Landweber and Kuroda.
Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is context sensitive.
[19] Moreover, they are closed under union, intersection, concatenation, substitution,[note 4] inverse homomorphism, and Kleene plus.
In other words, there is a context-sensitive grammar G such that deciding whether a certain string s belongs to the language of G is PSPACE-complete (so G is fixed and only s is part of the input of the problem).
[27][note 5] Savitch has proven the following theoretical result, on which he bases his criticism of CSGs as basis for natural language: for any recursively enumerable set R, there exists a context-sensitive language/grammar G which can be used as a sort of proxy to test membership in R in the following way: given a string s, s is in R if and only if there exists a positive integer n for which scn is in G, where c is an arbitrary symbol not part of R.[10] It has been shown that nearly all natural languages may in general be characterized by context-sensitive grammars, but the whole class of CSGs seems to be much bigger than natural languages.
[citation needed] Worse yet, since the aforementioned decision problem for CSGs is PSPACE-complete, that makes them totally unworkable for practical use, as a polynomial-time algorithm for a PSPACE-complete problem would imply P=NP.
It was proven that some natural languages are not context-free, based on identifying so-called cross-serial dependencies and unbounded scrambling phenomena.
[citation needed] However this does not necessarily imply that the class of CSGs is necessary to capture "context sensitivity" in the colloquial sense of these terms in natural languages.
For example, linear context-free rewriting systems (LCFRSs) are strictly weaker than CSGs but can account for the phenomenon of cross-serial dependencies; one can write a LCFRS grammar for {anbncndn | n ≥ 1} for example.
[28][29][30] Ongoing research on computational linguistics has focused on formulating other classes of languages that are "mildly context-sensitive" whose decision problems are feasible, such as tree-adjoining grammars, combinatory categorial grammars, coupled context-free languages, and linear context-free rewriting systems.