1. Push down automata accepts which
language
a) Context sensitive
language
b) Context free language
c) Recursive language
d) None of these
2. A context free grammar G is in Chomsky
normal form if every production is of the form
a) A → BC or A → A
b) A → BC or A → a
c) A → BCa or B → b
d) None of these
3. Which of the following statement is
false?
a) A recursive language
is also a regular language
b) A context free language is also a
regular language
c) A context free
language is also recursive enumerable language
d) Both (a) and (b)
4. A context free language is called
ambiguous if
a) It has two or more
leftmost derivations for some terminal string ѡ є L (G)
b) It has two or more leftmost
derivations for some terminal string ѡ є L (G)
c) Both (a) and (b)
d) None of these
5. Which of the
following statement is false?
a) The context free
language can be converted into Chomsky normal form
b) The context free language can be
converted into Greibach normal form
c) The context free language is accepted
by pushdown automata
d) None of these
6. The language L={0ᵐ1ᵐ0ᵐ| m ≥ 1} is a
a) Regular language
b) Context free language
c) Both (a) and (b)
d) None of these
7. While converting the context free
grammar into Greibach normal form, which of the following is not necessary
a) Elimination of null production
b) Elimination of unit
production
c) Converting given grammar in Chomsky
normal form
d) None of these
8. The context free grammar S → A111|S1,
A → A0 | 00 is equivalent to
a) {0ⁿ1ᵐ | n=2, m=3}
b) {0ⁿ1ᵐ | n=1, m=5}
c) {0ⁿ1ᵐ | n should be greater than two
and m should be greater than four}
d) None of these
9. The context free grammar S → SS | 0S1
| 1S0 | ɛ generates
a) Equal number of 0’s and 1’s
b) Unequal number of 0’s
and 1’s
c) Any number of 0’s followed by any
number of 1’s
d) None of these
10. Which of the following
statement is false?
a) In derivation
tree, the label of each leaf node is terminal
b) In derivation tree, the label of all
nodes except leaf nodes is a variable
c) In derivation
tree, if the root of a sub tree is X then it is called –tree
d) None of these