Computer science: Theory Of computation MCQs

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?

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?

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

Consider the following deterministic finite state automaton M.

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

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?