Grammars
are defined as context-free grammars before
with the only difference that there may be several symbols on the
left-hand side of a production, i.e.
.
Here
means that at least one symbol has to
present. The relation derives
(and
) is defined as before
![]() |
![]() |
|
![]() |
![]() |
We say that a grammar is context-sensitive (or type 1) if the left
hand side of a production is at least as long as the right hand side.
That is for each
we have
Here is an example of a context sensitive grammar:
with
.
where
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
We present without proof: