6. Prove that exists a context-sensitive language that is not context-free.
7. Show that every context sensitive language is recursive.
SHORT QUESTIONS AND ANSWERS
1. What is a context-sensitive language?
A language generated by a context-sensitive grammar is called a
context-sensitive language.
2. Define a context sensitive grammar.
A context-sensitive grammar is one whose productions are all of the
form
xAy xVy
→
where A v
∈ and x v y V T
, ,
(
)
*
∈ ∪
.
3. Give an alternative definition of context-sensitive grammar.
A context-sensitive grammar is one whose productions are all of the
form
x
y
→
where x y V T
x y
,
(
)
| | | |.
∈ ∪
≤
+ and
4. What is meant by “non-contracting” grammar?
Grammar is which the derivation steps never decrease the length of
the sentential form is called a ‘non-contracting’ grammar.
5. When is a language said to be context sensitive?
A language L is context-sensitive if there exists a content-sensitive
grammar G, such that either L L G
L L G
=
=
∪
( )
( ) { }
or
λ
6. Give an example for a context-sensitive language.
L a b c n
n n n
=
≥
{
|
}
1 is an example of a context-sensitive language.
7. What is a linear bounded automata?
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.
8. Say True or False: “Every context-free language is context-sensitive.”
TRUE.
9. Say True or False: “There exists a context-sensitive language that is not
context-free.”
TRUE.
10. Say True or False: “Every context-sensitive language need not be
recursive”.
FALSE, every context-sensitive language is recursive.
216
Theory of Automata, Formal Languages and Computation