Headlines
Loading...
Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 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