Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

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

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)