Theory of Computation MCQs | Page - 14

Q. 131) Context free grammar is used for-

Q. 132) The set strings of 0's and 1's with atmost one pair consecutive one's-

Q. 133) The problem 3-SAT and 2-SAT are

Q. 134) Which of the following instances of the post correspondence problem has a viable sequence (a solution)?

Q. 135) Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?

Q. 136) Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.

Q. 137) Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?

Q. 138) Which one of the following is not decidable?

Q. 139) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

Q. 140) Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is