1. Which of the following does not obey pumping lemma for context free languages ?
a. Finite languages
b. Context free languages
c. Unrestricted languages
d. None of the mentioned
Ans- c. Unrestricted languages
2. What is the pumping length of string of length x?
a. x+1
b. x
c. x-1
d. x2
Ans- a. x+1
3. The pumping lemma is often used to prove that a language is:
a. Context free
b. Not context free
c. Regular
d. None of the mentioned
Ans- b. Not context free
4. Which of the following is called Bar-Hillel lemma?
a. Pumping lemma for regular language
b. Pumping lemma for context free languages
c. Pumping lemma for context sensitive languages
d. None of the mentioned
Ans- b. Pumping lemma for context free languages
5. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in _____.
a. restricted form
b. parsed form
c. normal form
d. all of the mentioned
Ans- c. normal form
6. In which of the following, does the CNF conversion find its use?
a. CYK Algorithm
b. Bottom up parsing
c. Preprocessing step in some algorithms
d. All of the mentioned
Ans- d. All of the mentioned
7. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are: S->ABa; A->aab; B->Ac;
a. 3
b. 4
c. 2
d. 5
Ans- a. 3
8. Which of the following grammars are in Chomsky Normal Form:
a. S->AB|BC|CD, A->0, B->1, C->2, D->3
b. S->AB, S->BCA|0|1|2|3
c. S->ABa, A->aab, B->Ac
d. All of the mentioned
Ans- a. S->AB|BC|CD, A->0, B->1, C->2, D->3
9. Which of the production rule can be accepted by Chomsky grammar?
a. A->BC
b. A->a
c. S->e
d. All of the mentioned
Ans- d. All of the mentioned
10. Every grammar in Chomsky Normal Form is:
a. regular
b. context sensitive
c. context free
d. all of the mentioned
Ans- c. context free