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)