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…
1. Which among the following is not a part of the Context free grammar tuple? a. End symbol b. Start symbol c. Variable d. Production Ans- a. End symbol 2. The following move of a PDA is on the basis of: a. Present state b. Inpu…
1. Which of the following is a parser for an ambiguous grammar? a. GLR parser b. Chart parser c. All of the mentioned d. None of the mentioned Ans- c. All of the mentioned 2. Which of the following is an real-world programming l…
1. A DTD is associated with a XML file by means of _____ a. Function b. <!DOCTYPE> c. Macros d. None of the mentioned Ans- b. <!DOCTYPE> 2. Which of them have XML as their default format? a. IWork b. LibreOffice c. O…
1. The ___ table is created by YACC. a. LALR parsing b. LL parsing c. GLR parsing d. None of the mentioned Ans- a. LALR parsing 2. The YACC takes C code as input and outputs_____ a. Top down parsers b. Bottom up parsers c. Machi…
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 …
1. A grammar with more than one parse tree is called: a. Unambiguous b. Ambiguous c. Regular d. None of the mentioned Ans- b. Ambiguous 2. The number of leaves in a parse tree with expression E*(E) where * and () are operators a…
1. Which of the theorem defines the existence of Parikhs theorem? a. Parikh's theorem b. Jacobi theorem c. AF+BG theorem d. None of the mentioned Ans- a. Parikh's theorem 2. Which of the following statements are correct …
1. Pick the odd one out of the given properties of a regular language: a. Kleene b. Reversal c. Homomorphism d. Membership Ans- d. Membership 2. Which of the following are decision properties? a. Emptiness b. Infiniteness c. Mem…
1. Which of the following obey the closure properties of Regular language? a. Homomorphism b. Inverse Homomorphism c. Reversal d. All of the mentioned Ans- d. All of the mentioned 2. Which among the following is the closure prop…
1. Which of the following is/are an example of pigeon hole principle? a. Softball team b. Sock picking c. Hair counting d. All of the mentioned Ans- d. All of the mentioned 2. The language of balanced paranthesis is: a. regular …
