Context-sensitive grammar

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[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 context-sensitive if all rules in P are of the form

αAβ → αγβ

where AN (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 of a context-sensitive 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,[1] see Noncontracting grammar#Transforming into context-sensitive grammar.

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.[2]

Examples[edit]

  • This grammar, with start symbol S, generates the canonical non-context-free language { anbncn : n ≥ 1 } :
1.       S     →     a b c
2. S a S B c
3. c B W B
4. W B W X
5. W X B X
6. B X B c
7. b B b b

Rules 1 and 2 allow for blowing-up S to an(Bc)n; rules 3 to 6 allow for successively exchanging each cB to Bc (four rules are needed for that since a rule cBBc wouldn't fit into the scheme αAβ → αγβ); rule 7 allows for replacing a non-terminal B with its corresponding terminal b, provided it is in the right place. A generation chain for aaabbbccc is:

S
2 aSBc
2 aaSBcBc
1 aaabcBcBc
3 aaabWBcBc
4 aaabWXcBc
5 aaabBXcBc
6 aaabBccBc
3 aaabBcWBc
4 aaabBcWXc
5 aaabBcBXc
6 aaabBcBcc
3 aaabBWBcc
4 aaabBWXcc
5 aaabBBXcc
6 aaabBBccc
7 aaabbBccc
7 aaabbbccc

More complicated grammars can be used to parse { anbncndn: n ≥ 1 }, and other languages with even more letters.

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

Normal forms[edit]

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.

Computational properties and uses[edit]

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.[citation needed] 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[edit]

References[edit]

  1. ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ; p.223-224; Exercise 9, p.230. In the 2003 edition, the chapter on CSG has been omitted.
  2. ^ (Hopcroft, Ullman, 1979); Theorem 9.5, 9.6, p.225-226

External links[edit]