Home / Engineering / Theory of Computation MCQs / Page 10

Theory of Computation MCQs | Page - 10

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.

Q. 91) We think of a Turing machine’s transition function as a

(A) computer system
(B) software
(C) hardware
(D) all of them
View Answer Discuss Share

Q. 92) Church’s Thesis supports

(A) a turing machine as a general-purpose computer system
(B) a turing machine an algorithm and an algorithm as a turing machine
(C) both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
(D) none of them is correct
View Answer Discuss Share

Q. 93) A random access machine (RAM) and truing machine are different in

(A) power
(B) accessing
(C) storage
(D) both accessing and storage are correct
View Answer Discuss Share

Q. 94) Choose the correct statement

(A) recursive set ⊆ recursive enumerable set
(B) total function is same as partial function
(C) recursive sets are analogous to total functions
(D) both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.
View Answer Discuss Share

Q. 95) Given S = {a, b}, which one of the following sets is not countable?

(A) the set all strings over Σ
(B) the set of all language over Σ
(C) the set of all binary strings
(D) the set of all languages over Σ accepted by turing machines
View Answer Discuss Share

Q. 96) In which of the stated below is the following statement true? “For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”

(A) m1 is a non-deterministic finite automata
(B) m1 is a non-deterministic push-down automata
(C) m1 is a non-deterministic turing machine
(D) for no machine m1 use the above statement true
View Answer Discuss Share

Q. 97) Which of the following conversion is not possible (algorithmically)?

(A) regular grammar to context-free grammar
(B) non-deterministic finite state automata to deterministic finite state automata
(C) non-deterministic pushdown automata to deterministic pushdown automata
(D) none deterministic turing machine to deterministic turing machine
View Answer Discuss Share

Q. 98) Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

(A) NP hard
(B) NP complete
(C) Recursive
(D) Recursively enumerable
View Answer Discuss Share

Q. 99) Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?

(A) I only
(B) I and II
(C) I and III
(D) II and III
View Answer Discuss Share

Q. 100) Recursively enumerable languages are not closed under

(A) Union
(B) homomorphism
(C) complementation
(D) concatenation
View Answer Discuss Share