Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 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

Previous Post Next Post

Responsive Ad