Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 1. Which of the following can be used to prove a language is not context free?

a. Ardens theorem

b. Power Construction method

c. Regular Closure

d. None of the mentioned


Ans- c. Regular Closure


2. The intersection of context free language and regular language is ___

a. regular language

b. context free language

c. context sensitive language

d. none of the mentioned


Ans- b. context free language


3. Which of the following is not a negative property of Context free languages?

a. Intersection

b. Complement

c. Both (a) and (b)

d. None of the mentioned


Ans- c. Both (a) and (b)


4. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?

a. <symbol> ->expression

b. <symbol>::=expression

c. <symbol>=<expression>

d. all of the mentioned


Ans- b. <symbol>::=expression


5. Which of the following is true for Valiants algorithm?

a. an extension of CYK

b. deals with efficient multiplication algorithms

c. matrices with 0-1 entries

d. all of the mentioned


Ans- d. all of the mentioned


6. The standard version of CYK algorithm operates only on context free grammars in the following form:

a. Greibach Normal form

b. Chomsky Normal form

c. Backus Naur form

d. All of the mentioned


Ans- b. Chomsky Normal form


7. Which among the following can parse a context free grammar?

a. top down parser

b. bottom up parser

c. CYK algorithm

d. all of the mentioned


Ans- d. all of the mentioned


8. Which of the following grammars is similar to Floyd Normal form?

a. Backus Naur Form

b. Kuroda Normal Form

c. Greibach Normal Form

d. Chomsky Normal Form


Ans- a. Backus Naur Form


9. Given a grammar in GNF and a derivable string in the grammar with the length n, any _____will halt at depth n.

a. top-down parser

b. bottom-up parser

c. multitape turing machine

d. none of the mentioned


Ans- a. top-down parser


10. Which of the following can generate Unrestricted grammars?

a. Pentonnen Normal form

b. Floyd Normal form

c. Greibach Normal form

d. None of the mentioned


Ans- a. Pentonnen Normal form


11. A turing machine is a:

a. real machine

b. abstract machine

c. hypothetical machine

d. more than one option is correct


Ans- d. more than one option is correct


12. Which of the following steps are wrong with respect to infiniteness problem?

a. Remove useless variables

b. Remove unit and epsilon production

c. Create dependency graph for variables

d. If there is a loop in the dependency graph the the language is finite else infinite


Ans- d. If there is a loop in the dependency graph the the language is finite else infinite


13. Which of the following is true for CYK Algorithm?

a. Triangular Table

b. Circular Chart

c. Linked List

d. None of the mentioned


Ans- a. Triangular Table


14. Which of the following belong to the steps to prove emptiness?

a. Remove useless variable

b. Check if a start variable S is useless

c. Both (a) and (b)

d. None of the mentioned


Ans- c. Both (a) and (b)


15. Which of the following are valid membership algorithms?

a. CYK algorithm

b. Exhaustive search parser

c. Both (a) and (b)

d. None of the mentioned


Ans- c. Both (a) and (b)

Previous Post Next Post

Responsive Ad