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

1. The variable which produces an epsilon is called:

a. empty variable

b. nullable

c. terminal

d. all of the mentioned

Ans- b. nullable

2. The use of variable dependency graph is in:

a. Removal of useless variables

b. Removal of null productions

c. Removal of unit productions

d. None of the mentioned

Ans- a. Removal of useless variables

3. In context to the process of removing useless symbols, which of the following is correct?

a. We remove the Nullable variables

b. We eliminate the unit productions

c. We eliminate products which yield no terminals

d. All of the mentioned

Ans- c. We eliminate products which yield no terminals

4. Simplify the given grammar: A-> a| aaA| abBc; B-> abba| b

a. A-> a| aaA| ababbAc| abbc

b. A-> a| aaA| ababbAc| abbc, B-> abba|b

c. A-> a| aaA| abbc, B->abba

d. None of the mentioned

Ans- a. A-> a| aaA| ababbAc| abbc

5. Given a Grammar G: S->aA; A->a; A->B; B->A; B->bb; Which among the following will be the simplified grammar?

a. S->aA|aB, A->a, B->bb

b. S->aA|aB, A->B, B->bb

c. S->aA|aB, A->a, B->A

d. None of the emntioned

Ans- a. S->aA|aB, A->a, B->bb

6. Inorder to simplify a context free grammar, we can skip the following operation:

a. Removal of null production

b. Removal of useless symbols

c. Removal of unit productions

d. None of the mentioned

Ans- d. None of the mentioned

7. Given grammar: S->aS|A; A->a; B->aa; Find the number of variables reachable from the Starting Variable?

a. 0

b. 1

c. 2

d. None of the mentioned

Ans- b. 1

8. Given grammar G: S->aS|A|C; A->a; B->aa; C->aCb; Find the set of variables thet can produce strings only with the set of terminals.

a. {C}

b. {A,B}

c. {A,B,S}

d. None of the mentioned

Ans- c. {A,B,S}

9. Given Grammar: S->A, A->aA, A->e, B->bA; Which among the following productions are Useless productions?

a. S->A

b. A->aA

c. A->e

d. B->bA

Ans- d. B->bA

10. Suppose A->xBz and B->y, then the simplified grammar would be:

a. A->xyz

b. A->xBz|xyz

c. A->xBz|B|y

d. none of the mentioned

Ans- a. A->xyz