Chap ter 5
Chomsky Hier ar chy
5.1 CONTEXT SENSITIVE GRAMMARS AND LANGUAGES
A context-sensitive Language is a language generated by a context sensitive
grammar.
Definition 1: A context-sensitive grammar is one whose productions are all
of the form
xAy xvy
→
where A v
∈ and x v y V T
, ,
(
)
*
∈ ∪
.
“Context-sensitive” implies the fact that the actual string modification is
given by A v
→ , while the x and y provide the context in which the rule may be
applied.
Definition 2: A context-sensitive grammar is one whose productions are all
of the form
x
y
→
where x y V T
x y
,
(
) ,
| | | |.
∈ ∪
≤
+ and
This type of grammar is called “Non-contracting” as the derivation steps
never decrease the length of the sentential form.
This definition given above is mostly used. The two kinds of grammar are
almost equivalent generating the same languages with only the exception: One kind
of grammar permits languages to contain the empty string, while the other doesn’t.
A language L is context-sensitive if there exists a context sensitive
grammar G such that either L L G
L L G
=
=
∪
( )
( ) { }.
or
λ
Ì Exam ple 5.1.1: Show that the language L a b c n
n n n
=
≥
{
|
}
1 is a
context-sensitive language.
Solu tion
Let us prove this by showing a context-sensitive grammar for the language.