1. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L? 2n-1 n n+1 n-1 2. Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L? 2^(n+1) k+1 2^(k+1) n+1 3. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are A D B C 4. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression (a+b)* b*ab*ab b*a(a+b)* b*ab*ab*ab 5. A minimum state deterministic finite automation accepting the language L = {W |W EUR {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has 15 States 10 states 11 states 9 states 6. Which of the following statements is false? The set of all languages that are not recursively enumerable is countable. The families of recursively enumerable and recursive languages are closed under reversal The family of recursively enumerable languages is closed under union. Every context-sensitive language is recursive. 7. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? S=T ScT (S is a subset of T) TcS (T is a subset of S) SnT=Ø 8. Which is True about SR and RR-conflict: Known that CLR(1) has no RR-conflict, still RR-conflict might occur in LALR(1). RR-conflict might occur if lookahead for final items(reduce-moves) is same. If there is no SR-conflict in CLR(1) then definitely there will be no SR-conflict in LALR(1). All of the options . 9. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE? P3 is decidable if P1 is reducible to P3 P3 is undecidable if P3 is reducible to P2 P3 is undecidable if P2 is reducible to P3 P3 is decidable if P3 is reducible to P2's complement 10. Incremental-Compiler is a compiler compiles the whole source code to generate object code afresh which is written in a language that is different from the source language compiles only those portion of source code that have been modified. that runs on one machine but produces object code for another machine 11. Which one of the following is FALSE? Complement of every context-free language is recursive. Every NFA can be converted to an equivalent PDA. There is unique minimal DFA for every regular language Every nondeterministic PDA can be converted to an equivalent deterministic PDA. 12. The regular grammar for the language L = {anbm | n + m is even} is given by S ? S1 | S2 S1 ? aaa S1| aA1 S2 ? aaS2| A2 A1 ? b A1| ? A2 ? b A2| ? S ? S1 | S2 S1 ? a S1| aA1 S2 ? aaS2| A2 A1 ? b A1| ? A2 ? b A2| ? S ? S1 | S2 S1 ? aa S1| A1 S2 ? aaS2| A2 A1 ? bb A1| ? A2 ? bb A2| ? S ? S1 | S2 S1 ? a S1| A1 A1 ? b A1| ? S2 ? aaS2| A2 A2 ? b A2| ? 13. Which of the following statements in true? The complement of a context free language is context free The intersection of two context free languages is context free The union of two context free languages is context free If a language is context free it can always be accepted by a deterministic push-down automaton 14. The minimum state automaton equivalent to the above FSA has the following number of states 4 2 1 3 15. In a compiler, keywords of a language are recognized during parsing of the program the lexical analysis of the program dataflow analysis the code generation 16. Debugger is a program that does not allow execution of a segment of program allows to set breakpoints, execute a segment of program and display contents of register allows to examine and modify the contents of registers All of the options 17. Which of the following is true for the language {a^p} p is prine ? It is regular but not context free It is context free but not regular It is not accepted by a turing machine It is neither regular nor context free but accepted by a turing machine 18. The number of tokens in the following C statement is printf("i=%d, &i=%x", i&i); 6 10 9 13 19. Which of the following pairs have DIFFERENT expressive power? Single-tape Turing machine and multi-tape Turing machine Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine Deterministic push down automata (DPDA) and Non-deterministic pushdown automata Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA) 20. Which one of the following statements is FALSE? Type checking is done before parsing. Context-free grammar can be used to specify both lexical and syntax rules. High-level language programs can be translated to different Intermediate Representations. Arguments to a function can be passed using the program stack. 21. The grammar S ? aSa | bS | c is LL(1) but not LR(1) Both LL(1)and LR(1) Neither LL(1)nor LR(1) LR(1)but not LR(1) 22. Consider the regular language L =(111+11111)*. The minimum number of states 5 8 3 9 23. An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if the LR(1) parser for G has S-R conflicts the LR(0) parser for G has S-R conflicts the LALR(1) parser for G has reduce-reduce conflicts the SLR(1) parser for G has S-R conflicts 24. From the given data below : a b b a a b b a a b which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)? b a b b b a a b a b 25. The grammar A ? AA | (A) | e is not suitable for predictive-parsing because the grammar is right-recursive left-recursive an operator-grammar ambiguous 26. Which of the following is essential for converting an infix expression to the postfix from efficiently? An operator stack An operand stack An operand stack and an operator stack A parse tree 27. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? The set of all strings that begin and end with either 0 or 1. The set of all strings containing at most two 0s. The set of all strings containing at least two 0s. The set of all strings containing the substring 00. 28. Let L denotes the language generated by the grammar S OSO/00. Which of the following is true? L = O L is context free but not regular L is regular but not O L is not context free 29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0s in s and n1 (s)the number of ls in s. Which one of the following languages is not regular? L = {s EUR (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 } L = {s EUR (0 + 1)*n0 (s) is a 3-digit prime L = {s EUR (0 + 1)* | for every prefix s of s, l 0 (s) - n1 (s) | <= 2 } L={s EUR (0+1)* | n0(s) - n1(s) | <= 4} 30. Consider the languagesL1={0^{i}1^{j}|i != j},L2={0^{i}1^{j}|i = j},L3 = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true? Only L2 and L3 are context free All are context free Only L1 and L2 are context free Only L2 is context free 31. Let L = L1 \cap L2, where L1 and L2 are languages as defined below: L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is Regular Not recursive Context free but not regular Recursively enumerable but not context free. 32. Consider the language L1,L2,L3 as given below.L1={0^{p}1^{q} | p,q \in N}L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}Which of the following statements is NOT TRUE? Turing machine can be used to recognize all the three languages L1 is a regular language Push Down Automata (PDA) can be used to recognize L1 and L2 All the three languages are context free 33. Which of the following problems are decidable?1) Does a given program ever produce an output?2) If L is a context-free language, then is L’ (complement of L) also context-free?3) If L is a regular language, then is L’ also regular?4) If L is a recursive language, then, is L’ also recursive? 2, 3, 4 1, 2, 3, 4 1, 2 3, 4 34. The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is is not a deterministic CFL but a CFL not recurcise is a regular language is recursive and deterministic CFL 35. For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true? L is recursively enumerable, but not recursive L is context-free, but not regular L is recursive, but not context-free L is regular 36. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? Neither DHAM3 nor SHAM3 is NP-hard Both DHAM3 and SHAM3 are NP-hard DHAM3 is NP-hard, but SHAM3 is not SHAM3 is NP-hard, but DHAM3 is not 37. Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G? 1 and 3 1,2 and 3 1 only 2 and 3 38. Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false? L1 n L2 n L3 is recursively enumerable L1 n L2 is a deterministic CFL L1 U L2 is context free L3 n L1 is recursive 39. Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE? L2 is a deterministic CFL L3 is a deterministic CFL L3 is a CFL, but not a deterministic CFL L1 is a deterministic CFL 40. Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE? L1' is recursive and L2' is recursively enumerable L1' is recursively enumerable and L2' is recursive L1' and L2' are recursively enumerable L1' is recursive and L2' is not recursively enumerable 41. Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE? L1 and L2 are context-free languages L1 u L2 is a context-free language L1 n L2 is a context sensitive language L1 n L2 is a context-free language 42. Consider the following two problems on undirected graphs:α: Given G(V,E), does G have an independent set of size |v|—4?β: Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE? Both a and ß are NP-complete a is NP complete and ß is in P Both a and ß are in P a is in P and ß is NP-complete 43. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? L2 intersection L1 is recursively enumberable L2 L1 is recursively enumerable. L2 union L1 is recursively enumberable L1 L3 is recursively enumberable 44. S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of All odd length palindromes. All even length palindromes. Strings that begin and end with the same symbol All palindromes. 45. Match all items in Group 1 with correct options from those given in Group 2.List I List IIP. Regular Expression 1. Syntax analysisQ. Push down automata 2. Code GenerationR. Dataflow analysis 3. Lexical analysisS. Register allocation 4. Code optimization P-3, Q-4, R-1, S-2 P-4. Q-1, R-2, S-3 P-2, Q-1, R-4, S-3 P-3, Q-1, R-4, S-2 46. Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct? Both S1 and S2 are correct None of S1 and S2 is correct Only S1 is correct Only S2 is correct 47. Which of the following are decidable ?1. whether the intersection of two regular language is infinite.2. whether a give context free language is regular3. whether two push down automata accept the same language.4. whether a given grammar is context free 2 and 4 2 and 3 1 and 2 1 and 4 48. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rulesS --> aB S --> bAB --> b A --> aB --> bS A --> aSB --> aBB A --> bAAWhich of the following strings is generated by the grammar? aabbab abbbba aaaabb aabbbb 49. Which of the following are decidable?I. Whether the intersection of two regular languages is infiniteII. Whether a given context-free language is regularIII. Whether two push-down automata accept the same languageIV. Whether a given grammar is context-free II and IV I and IV II and III I and II 50. In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier? (L + D) * (L.D) * L(L + D) * L(L.D) * Submit Answers Retake Test More Computer Science Engineering Study Material › Computer Science Engineering Mock Tests with Answers Distributed Computing System Mock Test Software Project Management Mock TestArtificial Intelligence and Robotics Mock TestBasics of Database Management Mock TestC# Programming Mock TestC#.NET Programming Mock TestCloud Computing Mock TestCommunication Network Mock TestComputer Architecture Mock TestComputer Architecture and Organization Mock TestComputer Fundamentals Mock TestComputer Networking Mock TestComputer Networks Mock TestCPP Programming Mock TestData Analysis Mock TestData Communication and Computer Network Mock TestData Compression and Data Retrieval Mock TestData Mining and Business Intelligence Mock TestData Mining and Data Warehouse Mock TestData Structure and Algorithms Mock TestData Structures Mock TestDataBase Management System Mock TestDesign and Analysis of Algorithms Mock TestDigital Electronics and Logic Design Mock TestDigital Logic Circuits Mock TestDigital Principles and System Design Mock TestDiscrete Mathematics Mock TestDiscrete Structure Mock TestDotNet Technology Mock TestEmbedded Real Time Operating System Mock TestGreen Computing Mock TestHigh Performance Computing Mock TestInformation Cyber Security Mock TestInformation and Network Security Mock TestInformation Retrival Techniques Mock TestInformation Systems and Engineering Economics Mock TestMachine Learning Mock TestMicroprocessor and Interfacing Technique Mock TestMicroprocessors Mock TestMuli core Architectures and Pro Mock TestMulti core processors Mock TestNetwork Security Mock TestNeural Networks and Fuzzy Control Object Oriented Programming Mock TestOperating System Architecture Mock TestOperating System Mock TestProblem Solving and Python Programming Mock TestProgramming for Problem Solving Mock TestPython Programming Mock TestSoft Computing Mock TestSoftware Design Modeling Mock TestSoftware Engineering Mock TestSoftware Testing Mock TestSoftware Testing and Quality Assurance Mock TestTheory of Computation and Compiler Design Mock TestTheory of Computation Mock TestUbiquitous Computing System Mock Test Computer Science Engineering Mock Tests
