 Contextsensitive grammar

A contextsensitive grammar (CSG) is a formal grammar in which the lefthand sides and righthand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Contextsensitive grammars are more general than contextfree grammars but still orderly enough to be parsed by a linear bounded automaton.
The concept of contextsensitive 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. A formal language that can be described by a contextsensitive grammar is called a contextsensitive language.
Contents
Formal definition
A formal grammar G = (N, Σ, P, S) ( this is the same as G = (V, T, P, S), just that the NonTerminal V(ariable) is replaced by N and T(erminal) is replaced by Σ ) is contextsensitive if all rules in P are of the form
 αAβ → αγβ
where A ∈ N (i.e., A is a single nonterminal), α,β ∈ (N U Σ)* (i.e., α and β are strings of nonterminals and terminals) and γ ∈ (N U Σ)^{+} (i.e., γ is a nonempty string of nonterminals and terminals).
Some definitions also add that for any production rule of the form u → v of a contextsensitive grammar, it shall be true that u≤v. Here u and v denote the length of the strings respectively.
In addition, a rule of the form
 S → λ provided S does not appear on the right side of any rule
where λ represents the empty string is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the context free languages, rather than having to make the weaker statement that all context free grammars with no →λ productions are also context sensitive grammars.
The name contextsensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not. This is different from a contextfree grammar where the context of a nonterminal is not taken into consideration. (Indeed, every production of a context free grammar is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty)).
If the possibility of adding the empty string to a language is added to the strings recognized by the noncontracting grammars (which can never include the empty string) then the languages in these two definitions are identical.
Examples
 This grammar generates the canonical noncontextfree language :
The generation chain for aaa bbb ccc is:
 S
More complicated grammars can be used to parse , and other languages with even more letters.
 The following grammar generates the noncontextfree copy language, :
The generation chain for abab is:
 S
Normal forms
Every contextsensitive grammar which does not generate the empty string can be transformed into an equivalent one in Kuroda normal form. "Equivalent" here means that the two grammars generate the same language. The normal form will not in general be contextsensitive, but will be a noncontracting grammar.
Computational properties and uses
The decision problem that asks whether a certain string s belongs to the language of a certain contextsensitive grammar G, is PSPACEcomplete. There are even some contextsensitive grammars whose fixed grammar recognition problem is PSPACEcomplete.
The emptiness problem for contextsensitive grammars (given a contextsensitive grammar G, is ?) is undecidable.
It has been shown that nearly all natural languages may in general be characterized by contextsensitive grammars, but the whole class of CSG's seems to be much bigger than natural languages^{[citation needed]}. Worse yet, since the aforementioned decision problem for CSG's is PSPACEcomplete, that makes them totally unworkable for practical use, as a polynomialtime algorithm for a PSPACEcomplete problem would imply P=NP. Ongoing research on computational linguistics has focused on formulating other classes of languages that are "mildly contextsensitive" whose decision problems are feasible, such as treeadjoining grammars, combinatory categorial grammars, coupled contextfree languages, and linear contextfree rewriting systems. The languages generated by these formalisms properly lie between the contextfree and contextsensitive languages.
See also
References
 Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)
External links
Automata theory: formal languages and formal grammars Chomsky hierarchy Type0—Type1———Type2——Type3—Grammars (no common name)ContextsensitiveLinear contextfree rewriting systems etc.Treeadjoining etc.—Languages Minimal automaton Thread automataEach category of languages is a proper subset of the category directly above it.  Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.Categories: Formal languages
Wikimedia Foundation. 2010.