Home / Engineering / Theory of Computation MCQs / Page 14

# Theory of Computation MCQs | Page - 14

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 131) Context free grammar is used for-`

(A) Lexical analyzer
(B) Document type definition (DTD)
(C) Text pattern searching
(D) Both a & c

M

Mr. Dubey • 51.17K Points
Coach

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

(A) (0+1)*(01)(10)(0+1)*
(B) (0+1)*(01)*(10)(0+1)*
(C) (0+1)*(01)(10)*(0+1)*
(D) (0+!)(01)*(10)*(0+1)

M

Mr. Dubey • 51.17K Points
Coach

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

(A) Both in P
(B) Both NP complete
(C) NP-complete and in P respectively
(D) Undecidable and NP-complete respectively

M

Mr. Dubey • 51.17K Points
Coach

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

(A) {(b, bb), (bb, bab), (bab, abb), (abb, babb)}
(B) {(ab, aba), (baa, aa), (aba, baa)}
(C) {(ab, abb), (ba, aaa), (aa, a)}
(D) none of the above

M

Mr. Dubey • 51.17K Points
Coach

## `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?`

(A) Both FHAM and DHAM are NP-hard
(B) FHAM is NP hard, but DHAM is not
(C) DHAM is NP hard, but FHAM is not
(D) Neither FHAM nor DHAM is NP hard

M

Mr. Dubey • 51.17K Points
Coach

## `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.`

(A) P3 has polynomial time solution if P1 is polynomial time reducible to P3
(B) P3 is NP complete if P3 is polynomial time reducible to P2
(C) P3 is NP complete if P2 is reducible to P3
(D) P3 has polynomial time complexity and P3 is reducible to P2

M

Mr. Dubey • 51.17K Points
Coach

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

(A) L is undecidable
(B) L is recursive
(C) L is a CSL
(D) L is a regular set

M

Mr. Dubey • 51.17K Points
Coach

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

(A) given a Turing machine M, a string s, and an integer k, M accepts s with k steps
(B) equivalence of two given Turing machines
(C) language accepted by a given DFSA is nonempty
(D) language generated by a CFG is nonempty

M

Mr. Dubey • 51.17K Points
Coach

## ```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.```

(A) 1, 2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only

M

Mr. Dubey • 51.17K Points
Coach

## `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`

(A) Only DHAM3 is NP-hard
(B) Only SHAM3 is NP-hard
(C) Both SHAM3 and DHAM3 are NP-hard
(D) Neither SHAM3 nor DHAM3 is NP-hard

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.