Home / Engineering / Theory of Computation MCQs / Page 9

Theory of Computation MCQs | Page - 9

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. 81) The language L = {anbnan n≥ 1} is recognized by

(A) turing machine
(B) 2 pushdown automata
(C) post machine
(D) all are correct
View Answer Discuss Share

Q. 82) If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be

(A) recursive enumerable
(B) recursive
(C) context free language (cfl)
(D) none of them
View Answer Discuss Share

Q. 83) If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be

(A) recursive enumerable
(B) recursive
(C) context free language
(D) none of these
View Answer Discuss Share

Q. 84) Universal Turing machine (UTM) influenced the concepts of

(A) computability
(B) interpretive implementation of programming language
(C) program and data is in same memory
(D) all are correct
View Answer Discuss Share

Q. 85) The number of symbols necessary to simulate a Turing machine with m symbols and n states

(A) 4m × n + m
(B) 4m × n + n
(C) m+n
(D) none of them
View Answer Discuss Share

Q. 86) A universal Turing machine is a

(A) reprogrammable truing machine
(B) two-tape turing machine
(C) single tape turing machine
(D) none of them
View Answer Discuss Share

Q. 87) He difference between a read-only Turing machine and a two-way finite state machine is

(A) head movement
(B) finite control
(C) storage capacity
(D) power
View Answer Discuss Share

Q. 88) Which is correct regard an off-line Truing machine?

(A) an offline turing machine is a special type of multi-tape turing machine
(B) an offline turing machine is a kind of multi-tracks truing machine
(C) an offline turing machine is a kind of single-track turing machine
(D) none of them
View Answer Discuss Share

Q. 89) Which of the following statement is wrong?

(A) power of ntm and tm is same
(B) for n ≥ 2, npda has some power as a tm
(C) for n ≥ 2, npda and 2pda have same power
(D) power of ntm and tm is not same
View Answer Discuss Share

Q. 90) Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;

(A) (tm, 2pda)
(B) (computer, utm)
(C) (2pda, npda)
(D) (fa, pda)
View Answer Discuss Share