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
Context (linguistics) , Context
Like "text," the word "context" is a metaphor derived from the Latin texere, "to weave." In the fourth century c.e. the Latin noun contextio… Geometric Figures , Skip to main content
Geometric figures
geometric shapes (plane figures)
geometric shapes (plane figures)
Types of triangle
Equilateral
All the sides… Achaea , A·chae·an / əˈkēən/ • adj. of or relating to Achaea in ancient Greece. ∎ (esp. in Homeric contexts) Greek. • n. an inhabitant of Achaea. ∎ (esp. in H… Parallelogram , A parallelogram, in plane geometry, is a plane figure of four sides whose opposite sides are parallel to each other and where each side is equal in l… Length , length / leng(k)[unvoicedth]; lenth/ • n. 1. the measurement or extent of something from end to end; the greater of two or the greatest of three dime… Telephoto Lens , telephoto lens Camera lens with a long focal length. A true telephoto lens has a focal length longer than the physical length of the lens, as opposed…
You Might Also Like
NEARBY TERMS
context-sensitive grammar