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**