11. Give an example of a regular language
a*.
12. Give an example of a context-free language?
a
n b
n .
13. Give an example of a context-sensitive language
a b c
n n n .
14. Give an example of a recursively enumerable language.
Any computable function is an example.
15. What are kinds of regular grammars?
(a) Right-linear grammar.
(b) Left-linear grammar.
16. Give an example of a machine which applies context-free language.
Nondeterministic Pushdown Automaton
17. Give an example of a machine which applies context-sensitive
language.
Linear Bounded Automaton
18. Give an example of a machine which applies recursively enumerable
language.
Turing machine.
19. What is the grammar corresponding to a recursively enumerable
language.
Unrestricted grammar.
20. What are the languages the Chomsky Hierarchy describes?
(a) Regular language
(b) Context-free language
(c) Context-sensitive language
(d) Recursively enumerable language.
21. What are Unrestricted grammars?
The grammars in the Chomsky hierarchy allows productions of the
form
α β
→
where α and β are arbitrary strings of grammar symbols, with α λ
≠ .
These grammars are called ‘Unrestricted grammars”.
22. Mention the types of statements in the language of a random access
machine.
(a) if then else ;
(b) while do ;
(c) : = + 1; (increment)
(d) : = – 1; (decrement)
Chomsky Hierarchy
217