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. Context-sensitive grammars are more general than context-free grammars but still orderly enough to be parsed by a linear bounded automaton.

The concept of context-sensitive 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 context-sensitive grammar is called a context-sensitive language.

Contents

Formal definition

A formal grammar G = (N, Σ, P, S) ( this is the same as G = (V, T, P, S), just that the Non-Terminal V(ariable) is replaced by N and T(erminal) is replaced by Σ ) 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 also add that for any production rule of the form u → v of a context-sensitive 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 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.

Examples

  1. S \rightarrow aSBC
  2. S \rightarrow aBC
  3. CB \rightarrow HB
  4. HB \rightarrow HC
  5. HC \rightarrow BC
  6. aB \rightarrow ab
  7. bB \rightarrow bb
  8. bC \rightarrow bc
  9. cC \rightarrow cc

The generation chain for aaa bbb ccc is:

S
\Rightarrow_1 aSBC
\Rightarrow_1 a\boldsymbol{aSBC}BC
\Rightarrow_2 aa\boldsymbol{aBC}BCBC
\Rightarrow_3 aaaB\boldsymbol{HB}CBC
\Rightarrow_4 aaaB\boldsymbol{HC}CBC
\Rightarrow_5 aaaB\boldsymbol{BC}CBC
\Rightarrow_3 aaaBBC\boldsymbol{HB}C
\Rightarrow_4 aaaBBC\boldsymbol{HC}C
\Rightarrow_5 aaaBBC\boldsymbol{BC}C
\Rightarrow_3 aaaBB\boldsymbol{HB}CC
\Rightarrow_4 aaaBB\boldsymbol{HC}CC
\Rightarrow_5 aaaBB\boldsymbol{BC}CC
\Rightarrow_6 aa\boldsymbol{ab}BBCCC
\Rightarrow_7 aaa\boldsymbol{bb}BCCC
\Rightarrow_7 aaab\boldsymbol{bb}CCC
\Rightarrow_8 aaabb\boldsymbol{bc}CC
\Rightarrow_9 aaabbb\boldsymbol{cc}C
\Rightarrow_9 aaabbbc\boldsymbol{cc}

More complicated grammars can be used to parse  \{ a^n b^n c^n d^n | n \ge 1 \} , and other languages with even more letters.

  • The following grammar generates the non-context-free copy language, C = \{ x x | x \in \{a,b\}^* \} :
  1. S \rightarrow aAS | bBS | T
  2. Aa \rightarrow aA
  3. Ba \rightarrow aB
  4. Ab \rightarrow bA
  5. Bb \rightarrow bB
  6. BT \rightarrow Tb
  7. AT \rightarrow Ta
  8. T \rightarrow \epsilon

The generation chain for abab is:

S
\Rightarrow_1 aAS
\Rightarrow_1 aA\boldsymbol{bBS}
\Rightarrow_1 aAbB\boldsymbol{T}
\Rightarrow_4 a\boldsymbol{bA}BT
\Rightarrow_6 abA\boldsymbol{Tb}
\Rightarrow_7 ab\boldsymbol{Ta}b
\Rightarrow_8 abab

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 certain context-sensitive grammar G, is PSPACE-complete. There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete.

The emptiness problem for context-sensitive grammars (given a context-sensitive grammar G, is L(G)=\emptyset ?) 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

References

  • Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule 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). The… …   Wikipedia

  • Context-sensitive — is an adjective meaning depending on context or depending on circumstances . It may refer to: Context sensitive grammar Context sensitive language Context sensitive help Context sensitive user interface in computing This disambiguation page lists …   Wikipedia

  • Context-sensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… …   Wikipedia

  • context-sensitive — adjective a) Sensitive to context; exhibiting different behaviour depending on a task or situation. Right click anywhere in the document window, and a context sensitive menu appears. b) (Of a grammar) Involving transformations that are affected… …   Wiktionary

  • Mildly context-sensitive language — In formal grammar theory, mildly context sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced …   Wikipedia

  • Deterministic context-free grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… …   Wikipedia

  • context — In linguistics, context is the parts of an utterance surrounding a unit and which may affect both its meaning and its grammatical contribution. A context free grammar is one where the rules apply regardless of context; a context sensitive grammar …   Philosophy dictionary

  • Context-free language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… …   Wikipedia

  • Tree-adjoining grammar — (TAG) is a grammar formalism defined by Aravind Joshi. Tree adjoining grammars are somewhat similar to context free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context free grammars have rules for… …   Wikipedia

  • Noncontracting grammar — Contents 1 Formal definition 2 Example 3 Equivalent types of grammars; expressive power 4 See also Formal definition …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”