1. A spanning tree for a simple graph of order 24 has 23 edges 6 edges 12 edges none of the options 2. Type-1 Grammar is known as_____________ REGULAR CSG CFG All of the options 3. A Hamiltonian cycle in a Hamiltonian graph of order 24 has 12 edges. 24 edges 23 edges none of the options 4. Which of the following is TRUE? Infinite union of finite sets is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Every subset of a regular set is regular 5. Any given transition graph has an equivalent: regular NDFSM DFSM (Deterministic Finite State Machine) all of the options 6. A language L is accepted by a FSA iff it is CFL Regular Recursive CSL 7. The minimum state automaton equivalent to the above FSA has the following number of states 3 1 4 2 8. The regular sets are closed under: Union Kleene closure Concatenation All of the options 9. Which of the following statement is wrong Some non-regular languages cannot be generated by any CFG Any regular language can be generated by a context-free grammar All non-regular languages can be generated by CFGs. the intersection of a CFL and regular set is a CFL 10. Which of the following are regular sets? I and III only IV only I and IV only I only 11. A language is regular if and only if Accepted by LBA Accepted by PDA Accepted by DFA Accepted by Turing machine 12. P, Q, R are three languages. If P & R are regular and if PQ=R, then Q has to be a CFL Q cannot be regular Q has to be regular Q need not be regular 13. Which one of the following statement is FALSE? context-free languages are closed under concatenation context-free languages are closed under union context-free languages are closed under intersection context-free languages are closed under Kleene closure 14. Grammars that can be translated to DFAs: Right linear grammar Generic grammar Left linear grammar All of the options 15. Regular expressions are Type 0 language Type 2 language Type 1 language Type 3 language 16. Which of the following problems is undecidable Finiteness problem for Finite state automata FSAs Ambiguity problem for CFGs Membership problem for CFGs Equivalence problem for FSAs 17. Recursively enumerable languages are not closed under. Union concatenation homomorphism complementation 18. The concept of FSA is much used in this part of the compiler Parser Code generation Code optimization Lexical analysis 19. PCP is: Undecidable Sometimes Decidable Decidable None of the options 20. Which of the following statement is wrong? Intersection of context free language and a regular language is always context-free Some non-regular languages cant be generated by any context-free grammar Any regular language has an equivalent context-free grammar. All languages can be generated by context- free grammar 21. Recursive languages are Always recognized by FSA A proper superset of CFL Always recognized by PDA Are also called type 0 languages 22. The Family of recursive language is not closed under which of the following operations: Complementation Intersection Union None of the options 23. Grammar that produce more than one Parse tree for same sentence is: Unambiguous Ambiguous Concatenation Complementation 24. Any Language generated by an unrestricted grammar is: Recursive Not Recursive Recursively Enumerable None of the options 25. Which of the following statements is wrong? The class of regular sets is closed under substitution The regular sets are closed under intersection The class of regular sets is closed under homomorphism Context Sensitive Grammar(CSG) can be recognized by Finite State Machine 26. If PCP is decidable then MPCP is Undecidable Decidable Cant Say None of the options 27. The language accepted by a Push down Automata: Type 1 Type 2 Type 0 Type 3 28. Which of the following problem is undecidable? Membership problem for CFL Membership problem for type 0 languages Membership problem for regular sets Membership problem for CSL 29. 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 finite automata (DFA) and Non-Deterministic finite automata(NFA) Deterministic push down automata (DPDA) and Non-deterministic pushdown automata 30. Context free grammar is not closed under kleene star Product operation Union Complementation 31. Recursively enumerable languages are not closed under Union Intersection Complementation None of the options 32. Which statement is true The PDA must have one accept state and one reject state There is no reject state in the PDA. The PDA must have one accept state and two reject state The PDA must have two accept state and two reject state 33. The logic of pumping lemma is a good example of Iteration Divide-and-conquer technique Recursion Pigeon-hole principle 34. If L and L- are recursively enumerable, then L is Recursive Context free Context sensitive Regular 35. Recursively enumerable languages are not closed under: Intersection Concatenation Union Complementation 36. Basic limitation of FSM is that it Sometimes fails to recognize grammars that are regular Cannot remember arbitrary large amount of information Sometimes recognizes grammars are not regular None of the options 37. Pumping lemma is generally used for proving that Given grammar is not regular Whether two given regular expressions are equivalent or not Given grammar is regular None of the options 38. A PC not connected to a network is equivalent to A Turing Machine, A Push-Down Automaton, A Deterministic Finite-State Automaton, None of the options 39. Which of the following problems is undecidable? Membership problem for CFGs Equivalence problem for FSAs. Finiteness problem for FSAs. Ambiguity problem for CFGs. 40. The production Grammar is {S->aSbb,S->abb} is type-3 grammar type-2 grammar type-1 grammar type-0 grammar 41. TM is more powerful than FSM because The tape movement is confined to one direction It has the capability to remember arbitrary long sequences of input symbols It has no finite state control None of the options 42. ___________ states are called the halt states. ACCEPT AND START ACCEPT AND WRITE ACCEPT and READ ACCEPT and REJECT 43. Left hand side of a production in CFG consists of: Terminals and non-terminals One non-terminal One terminal More than one terminal 44. Which statement is true? The tape of turing machine is finite. The tape of turing machine is infinite. The tape of turing machine is finite when the language is nonregular. The tape of turing machine is infinite when the language is regular 45. The part of an FA, where the input string is placed before it is run, is called _______ Output Tape Transition State Input Tape 46. Universal Turing machine (UTM) influenced the concepts of computability interpretive implementation of programming language program and data is in same memory all of the options 47. We think of a Turing machines transition function as a hardware software computer system all of the options 48. Which is correct regard an off-line Truing machine? an offline turing machine is a special type of multi-tape turing machine an offline turing machine is a kind of multi-tracks truing machine an offline turing machine is a kind of single-track turing machine None of the options 49. Which of the following conversion is not possible (algorithmically)? regular grammar to context-free grammar none deterministic turing machine to deterministic turing machine non-deterministic finite state automata to deterministic finite state automata non-deterministic pushdown automata to deterministic pushdown automata 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
