context-sensitive grammar

A Dictionary of Computing | 2004 | 700+ words | Copyright

context-sensitive grammar A grammar in which each production has the form αAβ → αγβ

where A is a nonterminal and α, β, and γ are arbitrary words with γ nonempty. If γ was allowed to be empty then any type 0 (equivalently, recursively enumerable) language of the Chomsky hierarchy could be generated. To derive the empty word, a production S → Λ

must also be included, with S not occurring in the right-hand side of any production. The term context-sensitive refers to the fact that A can be rewritten to γ only in the “context” α…β.

In a length-increasing grammar each production has a right-hand side at least as long as its left-hand side (apart possibly from S → Λ). Clearly any context-sensitive grammar is length-increasing, but it can also be shown that any length-increasing grammar is equivalent to a context-sensitive one. Context-sensitive grammars are a class of phrase-structure grammar.

Compare context-free grammar.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "context-sensitive grammar." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "context-sensitive grammar." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-contextsensitivegrammar.html

JOHN DAINTITH. "context-sensitive grammar." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-contextsensitivegrammar.html

Learn more about citation styles