context-sensitive grammar
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.
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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
context-sensitive grammar