1. Pumping lemma for context free grammar
is used for
a) Proving certain languages are not
context free
b) Proving language is infinite
c) Both (a) and (b)
d) None of these
2. If L1 and L2 are context free language then
a) Their union is also a context free
language
b) There concatenation is also context
free language
c) Both (a) and (b)
d) None of these
3. Which of the following statement is
false?
a) If L is context free language then L*
is also a context free language
b) If L1 and L2 are context free language then there
intersection is not a context free language
c) If L1 and L2 are context free language then there
union is also a context free language
d) None of these
4. Context free grammar is closed under
a) Union
b) Intersection
c) Both
d) None of these
5. CYK algorithm is named CYK because it
was invented by
a) John Cocke, Tadao Kasami and Daniel H.
Younger
b) Jass Carry, Tom Kosami and
Daniel Richy
c) Cammy lenna, Yousaf, Kosami
d) None of these
6. The CYK algorithm start with
a) Chomsky normal form grammar
b) Greibach normal form grammar
c) Both (a) and (b)
d) None of these
7. Pumping lemma for context free
language breaks the strings into
a) Two parts
b) Three parts
c) Five parts
d) Six parts
8. In pumping lemma for context free
language
a) We start by assuming the given
language is context free and then we get contradict
b) We first convert the given language
into regular language and then apply steps on
c) Both (a) and (b)
d) None of these
9. The CYK algorithm constructs table
from where we can conclude whether w is in L
a) O(n³) time
b) O(n²) time
c) O(n) time
d) None of these
10. The CYK algorithm is also known as
a) Table filling algorithm
b) Pumping lemma
c) Both (a) and (b)
d) None of these