Theory of Computation questions and answers

1.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
X2 ∩ X1 is recursively enumerable X2 ∪ X1 is recursively enumerable X2 – X1 is recursively enumerable X1 – X3 is recursively enumerable

2.For the language {ap I P is a prime}, the statement which hold true is
It is not regular but context free It is regular but not context free It is neither regular nor context free, but accepted by a turing machine It is not accepted by turing machine

3.The statement that holds true is
Infinite union of finite sets is regular The union of two non-regular set is not regular Every finite subset of a non-regular set is regular Every subset of a regular set is regular

4.The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of
All strings containing at least two 1’s All strings containing at least two 0’s All strings that begin and end with either 0’s or 1’s All strings containing the substring 00

5.3-SAT and 2-SAT problems are
NP-complete and in P respectively Undecidable and NP-complete Both NP-complete Both in P

Theory of Computation questions and answers

1.From the options given below, the pair having different expressive power is
Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA) Single tape turning machine and multi tape turning machine Deterministic single tape turning machine and Non-Deterministic single tape turning machine

2.The problem that is undecidable -
Finiteness problem for FSA’s Membership problem for CFG’s Equivalence problem for FSA’s 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
Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even 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
π is NP-complete π is NP-hard but not NP-complete π is in NP but not NP-complete π is neither NP-hard nor in NP

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?
Q is NP-complete R is NP-complete Q is NP-hard R is NP-hard