Computer science: Theory Of computation MCQs

1. Question

Ram and Shyam have been asked to show that a certain problem π is NP-complete. Ram shows a polynomial time reduction from the 3-S AT problem to π , and Shyam shows a polynomial time reduction from π to 3-S AT. Which of the following can be inferred from these reduction?




Answer
2. Question

Nobody knows yet if P=NP. Consider the language L defined as follows

L={ (0 + l)*if P = NP;

Ø otherwise;}

Which of the following statements is true?




Answer
3. Question

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?




Answer
4. Question

Consider the following deterministic finite state automaton M.

Untitled

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is




Answer
5. Question

Let G = ({S}, {a. b} R, S) be a context free grammar where the rule set R is

S→ a S b | SS | ε

Which of the following statements is true?




Answer

4 thoughts on “Computer science: Theory Of computation MCQs

Leave a Reply

Your email address will not be published. Required fields are marked *