# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following does not have left recursions?

a. Chomsky Normal Form

b. Greibach Normal Form

c. Backus Naur Form

d. All of the mentioned

Ans- b. Greibach Normal Form

2. The format: A->aB refers to which of the following?

a. Chomsky Normal Form

b. Greibach Normal Form

c. Backus Naur Form

d. None of the mentioned

Ans- b. Greibach Normal Form

3. Which of the following variables in the given grammar is called live variable? S->AB; A->a

a. S

b. A

c. B

d. None of the mentioned

Ans- b. A

4. Given grammar G: S-> ABA, A->aA|e, B-> bB|e; Eliminate e and unit productions. State the number of productions the starting variable holds?

a. 6

b. 7

c. 9

d. 5

Ans- b. 7

5. A can be A-> derivable if and only if ____

a. A-> A is actually a production

b. A->B, B-> A exists

c. Both (a) and (b)

d. None of the mentioned

Ans- a. A-> A is actually a production

6. If grammar G is unambiguous, G' produced after the removal of Unit production will be:

a. ambiguous

b. unambiguous

c. finite

d. cannot be said

Ans- b. unambiguous

7. Given Grammar G: S->aA; A->a| A; B->B; The number of productions to be removed immediately as Unit productions:

a. 0

b. 1

c. 2

d. 3

Ans- c. 2

8. Which among the following is the format of unit production?

a. A->B

b. A->b

c. B->Aa

d. None of the mentioned

Ans- a. A->B

9. Consider the following grammar: A->e; B->aAbC; B->bAbA A->bB;  The number of productions added on the removal of the nullable in the given grammar:

a. 3

b. 4

c. 2

d. 0

Ans- b. 4

10. Simplify the given grammar: S->aXb; X->aXb | e

a. S->aXb | ab, X-> aXb | ab

b. S->X | ab, X-> aXb | ab

c. S->aXb | ab, X-> S | ab

d. None of the mentioned

Ans- a. S->aXb | ab, X-> aXb | ab