1. Which of the following a Turing machine does not consist of? a. input tape b. head c. state register d. none of the mentioned Ans- d. none of the mentioned 2. Which of the problems are unsolvable? a. Halting problem b. Boolea…
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 fre…
1. Every Kuroda Normal form grammar generates _____ a. Context free grammar b. Context sensitive grammar c. Unrestricted grammar d. None of the mentioned Ans- b. Context sensitive grammar 2. There is a linear grammar that genera…
1. Which of the following does not obey pumping lemma for context free languages ? a. Finite languages b. Context free languages c. Unrestricted languages d. None of the mentioned Ans- c. Unrestricted languages 2. What is the pu…
1. Which of the following does not have left recursions? a. Chomsky Normal Form b. Greibach Normal Form c. Backus Naur Form d. All of the mentioned Ans- b. Greibach Normal Form 2. The format: A->aB refers to which of the foll…
1. The variable which produces an epsilon is called: a. empty variable b. nullable c. terminal d. all of the mentioned Ans- b. nullable 2. The use of variable dependency graph is in: a. Removal of useless variables b. Removal of…
1. Find a regular expression for a grammar which generates a language which states : L contains a set of strings starting wth an a and ending with a b, with something in the middle. a. a(a*Ub*)b b. a*(aUb)b* c. a(a*b*)b d. None …
1. Which of the following relates to Chomsky hierarchy? a. Regular<CFL<CSL<Unrestricted b. CFL<CSL<Unrestricted<Regular c. CSL<Unrestricted<CF<Regular d. None of the mentioned Ans- a. Regular<CFL<…
1. |-* is the ____ closure of |- a. symmetric and reflexive b. transitive and reflexive c. symmetric and transitive d. none of the mentioned Ans- b. transitive and reflexive 2. A PDA machine configuration (p, w, y) can be correc…
1. Halting states are of two types. They are: a. Accept and Reject b. Reject and Allow c. Start and Reject d. None of the mentioned Ans- a. Accept and Reject 2. The production of the form A->B , where A and B are non terminals…
