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