Theory of Computation (3160704) MCQs

MCQs of Turing Machine (TM)

Showing 21 to 25 out of 25 Questions
1 2 3
21.
The language L = {anbn| n≥ 1} is recognized by
(a) Turing machine
(b) Pushdown automata
(c) Post machine
(d) All are correct
Answer:

Option (d)

22.
A Turing machine with several tapes in known as:
(a) Multi-tape Turing machine
(b) Universal Turing machine
(c) Poly-tape Turing machine
(d) All of the mentioned
Answer:

Option (a)

23.
Church’s Thesis supports
(a) Both TM is an general-purpose computer and TM is an algorithm and vice-versa are correct
(b) A Turing machine an algorithm and an algorithm as a Turing machine
(c) A Turing machine as a general-purpose computer system
(d) None of them is correct
Answer:

Option (a)

24.
Which of the following conversion is not possible (algorithmically)?
(a) Regular grammar to context-free grammar
(b) Non-deterministic pushdown automata to deterministic pushdown automata
(c) Non-deterministic finite state automata to deterministic finite state automata
(d) Non deterministic Turing machine to deterministic Turing machine
Answer:

Option (b)

25.
Any function whose values can be computed by an algorithm, can be computed by a Turing machine.
(a) Smn theorem
(b) Structured Program theorem
(c) Church-Turing thesis
(d) None of the mentioned
Answer:

Option (c)

Showing 21 to 25 out of 25 Questions
1 2 3