Unrestricted grammar: Production of the form α β
→ where α β
, are
arbitrary strings of grammar symbols, with α λ
≠ forms unrestricted
grammar.
REVIEW QUESTIONS
1. What do you mean by a context-sensitive grammar?
2. What do you mean by a context-sensitive language?
3. What do you mean Linear bounded automata?
4. Prove: “Every context-free language is context-sensitive”.
5. Prove: “There exists a context-sensitive language that is not
context-free”.
6. Prove: “Every context-sensitive language is recursive”.
7. Given an example for
(a) Regular language (b) Context-free language.
8. Give an example for
(a) Context-sensitive language (b) Recursively enumerable language.
9. What do you mean by Chomsky hierarchy of languages?
10. What are the machines corresponding to each of the following?
(a) Recursively enumerable language
(b) Context sensitive language
(c) Context-free language
(d) Regular language.
11. What do you mean by unrestricted grammar?
12. What do you mean by a random access machine?
EXERCISES
1. Check whether the language given by
L a b n
n n
=
≥
{
|
}
1
is a context-sensitive language or not.
2. Check whether the language
L
n
n n
=
≥
{
|
}
1 0
1
is a context-sensitive language or not.
3. Explain the Chomsky hierarchy of languages with an example.
4. Explain the concept of unrestricted grammar with examples.
5. Show that every context-free language is context sensitive.
Chomsky Hierarchy
215