(1) From the options given below, the pair having different expressive power is
(A) Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)
(B) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)
(C) Single tape turning machine and multi tape turning machine.
(D) Deterministic single tape turning machine and Non-Deterministic single tape turning machine
ANSWER: Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)
(2) The problem that is undecidable –
(A) Finiteness problem for FSA’s
(B) Membership problem for CFG’s
(C) Equivalence problem for FSA’s
(D) Ambiguity problem for CFG’s
ANSWER: Ambiguity problem for CFG’s
(3) The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of
(A) Strings that begin and end with the same symbol
(B) All odd and even length palindromes
(C) All odd length palindromes
(D) All even length palindromes
ANSWER: All odd length palindromes
(4) Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
(A) π is NP-complete
(B) π is NP-hard but not NP-complete
(C) π is in NP but not NP-complete
(D) π is neither NP-hard nor in NP
ANSWER: π is NP-complete
(5) Out of the three problems S, Q and R, S is an NP-complete problem and Q and R are the two other problems not known to be in NP. Which one of the following statements is true if Q is polynomial time reducible to S and S is the polynomial time reducible to R?
(A) Q is NP-complete
(B) R is NP-complete
(C) Q is NP-hard
(D) R is NP-hard
ANSWER: R is NP-complete
(6) From the options given below the statement, which is not necessarily true if X1 is the recursive language and X2 and X3 are the languages that is recursively enumerable but not recursive is
(A) X2 ∩ X1 is recursively enumerable
(B) X2 ∪ X1 is recursively enumerable
(C) X2 – X1 is recursively enumerable
(D) X1 – X3 is recursively enumerable
ANSWER: X1 – X3 is recursively enumerable
(7) For the language {ap I P is a prime}, the statement which hold true is
(A) It is not regular but context free
(B) It is regular but not context free
(C) It is neither regular nor context free, but accepted by a turing machine
(D) It is not accepted by turing machine
ANSWER: It is neither regular nor context free, but accepted by a turing machine
(8) The statement that holds true is
(A) Infinite union of finite sets is regular
(B) The union of two non-regular set is not regular
(C) Every finite subset of a non-regular set is regular
(D) Every subset of a regular set is regular
ANSWER: Every finite subset of a non-regular set is regular
(9) The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of
(A) All strings containing at least two 1’s
(B) All strings containing at least two 0’s
(C) All strings that begin and end with either 0’s or 1’s
(D) All strings containing the substring 00
ANSWER: All strings containing at least two 0’s
(10) 3-SAT and 2-SAT problems are
(A) NP-complete and in P respectively
(B) Undecidable and NP-complete
(C) Both NP-complete
(D) Both in P
ANSWER: NP-complete and in P respectively