Time Left - 15:00 mins

GATE Prev Year : Theory of Computation Test-1

Attempt now to get your rank among 766 students!

Question 1

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question 2

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

Question 3

Consider the languages

Which one of the following statements is true?

Question 4

Which one of the following problems is undecidable?

Question 5

Let SHAM₃ be the problem of finding a Hamiltonian cycle in a graph G = (V,E)with |V| divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Question 6

Consider the regular language L =(111 +11111)*. The minimum number of states in any DFA accepting this language is:

766 attempts
9 upvotes
26 comments

Tags :

GATE & PSU CS Theory of Computation

Jul 5GATE & PSU CS