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, in the sense that there are languages that can be described by CSG but not by contextfree grammars. Contextsensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between contextfree and unrestricted grammars in the Chomsky hierarchy.
A formal language that can be described by a contextsensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a contextsensitive language. Some textbooks actually define CSGs as noncontracting,^{[1]}^{[2]}^{[3]}^{[4]} although this is not how Noam Chomsky defined them in 1959.^{[5]}^{[6]} 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 contextsensitive; the latter issue was analyzed by Chomsky in 1963.^{[7]}^{[8]}
Chomsky introduced contextsensitive 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 "contextsensitive" as misleading and proposed "nonerasing" as better explaining the distinction between a CSG and an unrestricted grammar.^{[9]}
Although it is wellknown that certain features of languages (e.g. crossserial dependency) are not contextfree, it is an open question how much of CSG's 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 contextsensitive languages.^{[citation needed]} The syntaxes of some visual programming languages can be described by contextsensitive graph grammars.^{[10]}
Contents
Formal definition[edit]
A formal grammar G = (N, Σ, P, S), where N is a set of nonterminal symbols, Σ is a set of terminal symbols, P is a set of production rules, and S is the start symbol, is contextsensitive if all rules in P are of the form
 αAβ → αγβ
where A ∈ N,^{[note 1]} α,β ∈ (N∪Σ)^{*} ^{[note 2]} and γ ∈ (N∪Σ)^{+}.^{[note 3]}
A string u ∈ (N∪Σ)^{*} directly yields, or directly derives to, a string v ∈ (N∪Σ)^{*}, denoted as u ⇒ v, if u can be written as lαAβr, and v can be written as lαγβr, for some production rule (αAβ→αγβ) ∈ P, and some context strings l, r ∈ (N∪Σ)^{*}. More generally, u is said to yield, or derive to, v, denoted as u ⇒^{*} v, if u = u_{1} ⇒ ... ⇒ u_{n} = v for some n≥0 and some strings u_{2}, ..., u_{n1} (N∪Σ)^{*}. That is, the relation (⇒^{*}) is the reflexive transitive closure of the relation (⇒).
The language of the grammar G is the set of all terminal symbol strings derivable from its start symbol, formally: L(G) = { w ∈ Σ^{*}: S ⇒^{*} w }. Derivations that do not end in a string composed of terminal symbols only are possible, but don't contribute to L(G).
The only difference between this definition of Chomsky and that of unrestricted grammars is that γ can be empty in the unrestricted case.^{[9]}
Some definitions of a contextsensitive grammar only require that for any production rule of the form u → v, the length of u shall be less than or equal to the length of v, this seemingly weaker requirement is in fact weakly equivalent,^{[11]} see Noncontracting grammar#Transforming into contextsensitive grammar.
In addition, a rule of the form
 S → λ
where λ represents the empty string and S does not appear on the righthand side of any rule is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the contextfree languages, rather than having to make the weaker statement that all contextfree 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 contextfree 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.
The leftcontext and rightcontextsensitive grammars are defined by restricting the rules to just the form αA → αγ and to just Aβ → γβ, respectively. The languages generated by these grammars are also the full class of contextsensitive languages,^{[12]} the equivalence was established by Penttonen normal form.^{[13]}
Examples[edit]
The following grammar, with start symbol S, generates the canonical noncontextfree language { a^{n}b^{n}c^{n} : n ≥ 1 } :
1.  S  →  a  B  C  
2.  S  →  a  S  B  C  
3.  C  B  →  C  Z  
4.  C  Z  →  W  Z  
5.  W  Z  →  W  C  
6.  W  C  →  B  C  
7.  a  B  →  a  b  
8.  b  B  →  b  b  
9.  b  C  →  b  c  
10.  c  C  →  c  c 
Rules 1 and 2 allow for blowingup S to a^{n}BC(BC)^{n1}; rules 3 to 6 allow for successively exchanging each CB to BC (four rules are needed for that since a rule CB → BC wouldn't fit into the scheme αAβ → αγβ); rules 7–10 allow replacing a nonterminals B and C with its corresponding terminals b and c respectively, provided it is in the right place. A generation chain for aaabbbccc is:
 S
 →_{2} aSBC
 →_{2} aaSBCBC
 →_{1} aaaBCBCBC
 →_{3} aaaBCZCBC
 →_{4} aaaBWZCBC
 →_{5} aaaBWCCBC
 →_{6} aaaBBCCBC
 →_{3} aaaBBCCZC
 →_{4} aaaBBCWZC
 →_{5} aaaBBCWCC
 →_{6} aaaBBCBCC
 →_{3} aaaBBCZCC
 →_{4} aaaBBWZCC
 →_{5} aaaBBWCCC
 →_{6} aaaBBBCCC
 →_{7} aaabBBCCC
 →_{8} aaabbBCCC
 →_{8} aaabbbCCC
 →_{9} aaabbbcCC
 →_{10} aaabbbccC
 →_{10} aaabbbccc
More complicated grammars can be used to parse { a^{n}b^{n}c^{n}d^{n}: n ≥ 1 }, and other languages with even more letters.
A contextsensitive grammar for the language { a^{2i} : i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979).
Kuroda normal form[edit]
Every contextsensitive 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 contextsensitive, but will be a noncontracting grammar.^{[14]}^{[15]}
The Kuroda normal form is an actual normal form for noncontracting grammars.
Properties and uses[edit]
This section needs additional citations for verification. (August 2014) (Learn how and when to remove this template message)

Equivalence to linear bounded automaton[edit]
A formal language can be described by a contextsensitive grammar if and only if it is accepted by some linear bounded automaton (LBA);^{[16]} in some textbooks this result is attributed solely to Landweber and Kuroda.^{[6]} Others call it the MyhillLandweberKuroda Theorem.^{[17]} (Myhill introduced the concept of deterministic LBA in 1960. Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is context sensitive. Kuroda introduced the notion of nondeterministic LBA and the equivalence between LBA and CSGs in 1964.^{[18]}^{[19]})
As of 2010^{[update]} it is still an open question whether every contextsensitive language can be accepted by a deterministic LBA.^{[20]}
Closure properties[edit]
Contextsensitive languages are closed under complement, this 1988 result is known as the Immerman–Szelepcsényi theorem.^{[17]} Moreover, they are closed under union, intersection, concatenation, substitution,^{[note 4]} inverse homomorphism, and Kleene plus.^{[21]}
Every recursively enumerable language L can be written as h(L) for some contextsensitive language L and some string homomorphism h.^{[22]}
Computational problems[edit]
The decision problem that asks whether a certain string s belongs to the language of a given contextsensitive grammar G, is PSPACEcomplete. Moreover, there are contextsensitive grammars whose languages are PSPACEcomplete; in other words, there is a contextsensitive grammar G such that deciding whether a certain string s belongs to the language of G is PSPACEcomplete (so G is fixed and only s is part of the input of the problem).^{[23]}
The emptiness problem for contextsensitive grammars (given a contextsensitive grammar G, is L(G)=∅ ?) is undecidable.^{[24]}^{[note 5]}
The LuZc parser is a working example of a program which can parse Contextsensitive grammars.
As model of natural languages[edit]
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 contextsensitive 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 sc^{n} is in G, where c is an arbitrary symbol not part of R.^{[9]}
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.
It was proven that some natural languages are not contextfree, based on identifying socalled crossserial dependencies and unbounded scrambling phenomena, however this does not necessarily imply that all the class CSG is necessary to capture "context sensitivity" in the colloquial sense of these terms in natural languages. For example, the strictly weaker (than CSG) linear contextfree rewriting systems (LCFRS) can account for the phenomenon of crossserial dependencies; one can write a LCFRS grammar for {a^{n}b^{n}c^{n}d^{n}  n ≥ 1} for example.^{[25]}^{[26]}^{[27]}
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.
More recently, the class PTIME has been identified with range concatenation grammars, which are now considered to be the most expressive of the mildcontext sensitive languages.^{[27]}
See also[edit]
 Chomsky hierarchy
 Growing contextsensitive grammar
 Definite clause grammar#Noncontextfree grammars
 List of parser generators for contextsensitive grammars
Notes[edit]
 ^ i.e., A is a single nonterminal
 ^ i.e., α and β are strings of nonterminals and terminals
 ^ i.e., γ is a nonempty string of nonterminals and terminals
 ^ more formally: if L ⊆ Σ^{*} is a contextsensitive language and f maps each a∈Σ to a contextsensitive language f(a), the f(L) is again a contextsensitive language
 ^ This also follows from (1) contextfree languages being also contextsensitive, (2) contextsensitive language being closed under intersection, but (3) disjointness of contextfree languages being undecidable.
References[edit]
 ^ Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. p. 291. ISBN 9781449615529.
 ^ Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 730. ISBN 9781852330743.
 ^ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. p. 189. ISBN 9780080502465.
 ^ Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGrawHill. p. 277. ISBN 9780073191461.
 ^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. p. 26. ISBN 9027232504.
 ^ ^{a} ^{b} Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. pp. 330–331. ISBN 9780080502465.
 ^ Chomsky, N. (1963). "Formal properties of grammar". In Luce, R. D.; Bush, R. R.; Galanter, E. Handbook of Mathematical Psychology. New York: Wiley. pp. 360–363.
 ^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 125–126. ISBN 9027232504.
 ^ ^{a} ^{b} ^{c} Carlos Martín Vide, ed. (1999). Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., April 1998. John Benjamins Publishing. pp. 186–187. ISBN 9027215561.
 ^ Zhang, DaQian, Kang Zhang, and Jiannong Cao. "A contextsensitive graph grammar formalism for the specification of visual languages." The Computer Journal 44.3 (2001): 186200.
 ^ Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. AddisonWesley.; p. 223–224; Exercise 9, p. 230. In the 2003 edition, the chapter on CSG has been omitted.
 ^ Hazewinkel, Michiel (1989). Encyclopaedia of Mathematics. 4. Springer Science & Business Media. p. 297. ISBN 9781556080036. also at http://www.encyclopediaofmath.org/index.php/Grammar,_contextsensitive
 ^ Ito, Masami; Kobayashi, Yūji; Shoji, Kunitaka (2010). Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20–22 September 2008. World Scientific. p. 183. ISBN 9789814317603. citing Penttonen, Martti (Aug 1974). "Onesided and twosided context in formal grammars". Information and Control. 25 (4): 371–392. doi:10.1016/S00199958(74)910493.
 ^ Kuroda, SigeYuki (June 1964). "Classes of languages and linearbounded automata". Information and Control. 7 (2): 207–223. doi:10.1016/s00199958(64)901202.
 ^ Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. SpringerVerlag. pp. 175–252. ISBN 3540614869., Here: Theorem 2.2, p. 190
 ^ (Hopcroft, Ullman, 1979); Theorem 9.5, 9.6, p. 225–226
 ^ ^{a} ^{b} http://www.cs.cmu.edu/~flac/pdf/ContSens.pdf
 ^ Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 755. ISBN 9781852330743.
 ^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 9027232504.
 ^ Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGrawHill. p. 283. ISBN 9780073191461.
 ^ (Hopcroft, Ullman, 1979); Exercise S9.10, p. 230–231
 ^ (Hopcroft, Ullman, 1979); Exercise S9.14, p. 230–232. h maps each symbol to itself or to the empty string.
 ^ An example of such a grammar, designed to solve the QSAT problem, is given in Lita, C. V. (20160901). "On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses". 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC): 371–378. doi:10.1109/SYNASC.2016.064.
 ^ (Hopcroft, Ullman, 1979); Exercise S9.13, p. 230–231
 ^ Kallmeyer, Laura (2011). "Mildly ContextSensitive Grammar Formalisms: Natural Languages are not ContextFree" (PDF).
 ^ Kallmeyer, Laura (2011). "Mildly ContextSensitive Grammar Formalisms: Linear ContextFree Rewriting Systems" (PDF).
 ^ ^{a} ^{b} Kallmeyer, Laura (2010). Parsing Beyond ContextFree Grammars. Springer Science & Business Media. pp. 1–5. ISBN 9783642148460.
Further reading[edit]
 Meduna, Alexander; Švec, Martin (2005). Grammars with Context Conditions and Their Applications. John Wiley & Sons. ISBN 9780471736554.