1. Finite
automata accept
a) Regular
language
b) Recursive language
c) Both (a) and
(b)
d) None of these
2. A context
sensitive language is accepted by
a) Finite
automata
b) Linear bounded
automata
c) Both (a) and
(b)
d) None of these
3. Unrestricted
grammar is also known as
a) Type 0
b) Semi-thue grammar
c) Phrase
structure grammar
d) All of these
4. A grammar G
= (V, T, P, S) in which V is
a) Set of
variables
b) Set of terminals
c) Set of
variables and terminals
d) None of these
5. A grammar G
= (V, T, P, S) in which T is
a) Set of
variables
b) Set of terminals
c) Set of
variables and terminals
d) None of these
6. The language
generated by the following grammar is
A0 -> aA1
A1 -> ab
a) Type 0
b) Type 1
c) Type 2
d) Type 3
7. Which of the
following is more powerful?
a) PDA
b) Turing machine
c) Finite
automata
d) Context sensitive
language
8. Which of the
following string is generated by the grammar
S -> 0S1AB
A -> 4A
B -> SA
a) 0111
b) 010101
c) 00000
d) None of these
9. Which of the
following statement is wrong?
a) All context
sensitive grammar which are already left sensitive are equivalent to context
sensitive grammar which are left sensitive but only have productions of the
form: AB -> AC
b) If G = (V, T, P,
S) is an unrestricted grammar than L(G) is a recursively enumerable language.
c) Both (a) and
(b)
d) None of these
10. Which of the following
statement is wrong?
a) Chomsky
hierarchy originally define only two grammars
b) Type 0 grammar is
called unrestricted grammar
c) Type 0 is
recognized by turing machine
d) All of these