A kind of grammar is
S
abc aAbc
Ab bA
Ac Bbcc
bB
Bb
aB
aa aa A
→
→
→
→
→
|
,
,
,
,
|
Let us see how this works by looking at the derivation of a b c
3 3 3 .
S
aAbc abAc abBbcc
aBbbcc aaAbbcc aabAbcc
aabbAcc
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒ aabbBbccc
aabBbbccc aaBbbbccc
aaabbbccc
⇒
⇒
⇒
.
This uses the variables A and B. Since the language is not context-free, it is
said to be context-sensitive language.
5.2 LINEAR BOUNDED AUTOMATA
A Turing machine has an infinite supply of blank tape. A linear-bounded
automaton is a Turing machine whose tape is only αn squares long, where ‘n’ is
the length of the input string and α is a constant associated with the particular
linear-bounded automaton.
THE O REM (I): For every context-sensitive language L there exists a
linear-bounded automaton M such that L = L(M), i.e., M accept exactly the
strings of L.
THE O REM (II): For every language L accepted by a linear-bounded
automaton that produces exactly L or L − { }
λ , depending on the definition
of context sensitive grammar.
5.3 RELATIONSHIP OF OTHER GRAMMARS
THE O REM (I): Every context-free language is context-sensitive.
Proof: The productions of a context-free language have the form A v
→ . The
productions of a context-sensitive language have the form xAy xvy
→
, where x
and y are permitted to be λ.
Hence the result.
¨
THE O REM (II): There exists a context-sensitive language that is not
context-free.
Chomsky Hierarchy
211