Definition
Context-Sensitive Grammar (Type-1)
A grammar
is called context-sensitive (Type-1) if every production rule in is context-sensitive. In words: a single non-terminal symbol may be replaced by a nonempty string, but only in its surrounding context.
Example
A grammar for
Consider the following context-sensitive grammar:
It generates the language
, which is context-sensitive but not context-free. Here is one derivation of
.
- Start with the start symbol:
- Apply
once. This adds one on the left and one and one on the right:
- Apply
to the remaining . This produces the base word:
- Apply
to the substring :
- Apply
to the remaining :