Context-sensitive grammar

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. 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. Context-sensitive grammars are more general than context-free grammars.

Noam Chomsky introduced context-sensitive grammars 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.

Formal definition

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 context-sensitive 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).

In addition, a rule of the form

S → λ

where λ represents the empty string and S does not appear on the right-hand 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 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 context-sensitive 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 context-free 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.

A formal language can be described by a context-sensitive grammar if and only if it is accepted by some linear bounded automaton.

Examples

• This grammar, with start symbol S, generates the canonical non-context-free language { aⁿbⁿcⁿ : n ≥ 1 } :

1.		S	→	a	b	c
2.		S	→	a	T	B	c
3.		T	→	a	B	C
4.		T	→	a	T	B	C
5.	C	B	→	W	B
6.	W	B	→	W	X
7.	W	X	→	B	X
8.	B	X	→	B	C
9.	C	c	→	c	c
10.	a	B	→	a	b
11.	b	B	→	b	b

Rules 1 to 4 allow for either generating the word abc or blowing-up to aⁿ⁺¹(BC)ⁿBc. Rules 5 to 8 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β → αγβ). Their repeated application allows to sort the B and C nonterminals, resulting in a word of the form aⁿ⁺¹Bⁿ⁺¹Cⁿc. Rules 9 to 11 allow for replacing the nonterminals B and C with terminals b and c, respectively. The context ensures that they can only be applied to nonterminals that have been moved all the way to the right or left, using rules 5 to 8. A generation chain for aaabbbccc is:

S

→₂ aTBc

→₄ a aTBC Bc

→₃ aa aBC BCBc

→₅ aaaB WB CBc

→₆ aaaB WX CBc

→₇ aaaB BX CBc

→₈ aaaB BC CBc

→₅ aaaBBC WB c

→₆ aaaBBC WX c

→₇ aaaBBC BX c

→₈ aaaBBC BC c

→₅ aaaBB WB Cc

→₆ aaaBB WX Cc

→₇ aaaBB BX Cc

→₈ aaaBB BC Cc

→₉ aaaBBBC cc

→₉ aaaBBB cc c

→₁₀ aa ab BBccc

→₁₁ aaa bb Bccc

→₁₁ aaab bb ccc

More complicated grammars can be used to parse { aⁿbⁿcⁿdⁿ: n ≥ 1 }, and other languages with even more letters.

A context-sensitive grammar for the language { a²ⁱ : i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979).

Normal forms

Every context-sensitive 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 context-sensitive, 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 given context-sensitive grammar G, is PSPACE-complete. Morever, there are context-sensitive grammars whose languages are PSPACE-complete. 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).

The emptiness problem for context-sensitive grammars (given a context-sensitive grammar G, is L(G)=∅ ?) is undecidable.

It has been shown that nearly all natural languages may in general be characterized by context-sensitive grammars, but the whole class of CSG's seems to be much bigger than natural languages. Worse yet, since the aforementioned decision problem for CSG's 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. 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. The languages generated by these formalisms properly lie between the context-free and context-sensitive languages.

See also

• Chomsky hierarchy
• Growing context-sensitive grammar

References

• Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. ISBN 9780073191461. Retrieved 10 December 2012.

External links

• Earley Parsing for Context-Sensitive Grammars