Context-Sensitive Grammar Definition/Meaning:
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 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.
|
