Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following parser reaches the root symbol of the tree at last?

a. Top down parser

b. Bottom up parser

c. TOP down and Bottom up parser

d. None of the mentioned

Ans- b. Bottom up parser

2. To derive a string using the production rules of a given grammar, we use:

a. Scanning

b. Parsing

c. Derivation

d. All of the mentioned

Ans- b. Parsing

3. Choose the correct option. Statement: Unambiguity is the ideal structure of a language.

a. TRUE

b. partially true

c. FALSE

d. cant be said

Ans- a. TRUE

4. Which of the following are distinct to parse trees?

a. abstract parse trees

b. sentence diagrams

c. both abstract parse trees and sentence diagrams

d. none of the mentioned

Ans- c. both abstract parse trees and sentence diagrams

5. If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the ____ structure of w.

a. semantic

b. syntactic

c. lexical

d. all of the mentioned

Ans- b. syntactic

6. If |w|>=2^h, then its parse tree's height is at least ___

a. h

b. h+1

c. h-1

d. 2^h

Ans- b. h+1

7. Which of the following is false for a grammar G in Chomsky Normal Form:

a. G has no useless symbols

b. G has no unit productions

c. G has no epsilon productions

d. None of the mentioned

Ans- d. None of the mentioned

8. A symbol X is called to be useful if and only if its is:

a. generating

b. reachable

c. both generating and reachable

d. none of the mentioned

Ans- c. both generating and reachable

9. A symbol X is ____ if there exists : S->* aXb

a. reachable

b. generating

c. context free

d. none of the mentioned

Ans- a. reachable

10. ____ is the acyclic graphical representation of a grammar.

a. Binary tree

b. Oct tree

c. Parse tree

d. None of the mentioned

Ans- c. Parse tree