Theory of Computation (3160704) MCQs

MCQs of Turing Machine (TM)

Showing 11 to 20 out of 25 Questions
1 2 3
11.
Halting state of Turing machine are:
(a) Start and stop
(b) Accept and reject
(c) Start and reject
(d) Reject and allow
Answer:

Option (b)

12.
Which of the following is an extension to the basic model of Turing machine:
(a) Multi tape Turing machine
(b) Multi head Turing machine
(c) Nondeterministic Turing machine
(d) All of the above
Answer:

Option (d)

13.
An instantaneous description of Turing machine consists of:
(a) Present state and input to be processed
(b) Present state and entire input to be processed
(c) Present input only
(d) None of these
Answer:

Option (a)

14.
According to Chomsky hierarchy, which of the following is recognized by Recursively Enumerable language?
(a) Type 3
(b) Type 2
(c) Type 1
(d) Type 0
Answer:

Option (d)

15.
Why Turing machine is more powerful than Finite automata?
(a) Turing machine head movement is continued to one direction.
(b) Turing machine head moment is in both directions
(c) Turing machine has capability to remember arbitrary long sequence of input string.
(d) All are correct
Answer:

Option (c)

16.
A pushdown automata behaves like a Turing machine, when it has number of auxiliary memory.
(a) 0
(b) 2
(c) 2 or more
(d) Both b and c
Answer:

Option (c)

17.
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
Answer:

Option (d)

18.
Which of the following is true for the language: {ap | p is a prime}
(a) It is regular but not context-free
(b) It is neither regular nor context-free, but accepted by a Turing machine
(c) It is not accepted by a Turing Machine
(d) It is context-free but not regular
Answer:

Option (b)

19.
A universal Turing machine is a
(a) Single tape Turing machine
(b) Two-tape Turing machine
(c) Reprogrammable Truing machine
(d) None of them
Answer:

Option (c)

20.
A Turing machine that is able to simulate other Turing machines:
(a) Nested Turing machines
(b) Multi tap Turing machine
(c) Universal Turing machines
(d) None of these
Answer:

Option (c)

Showing 11 to 20 out of 25 Questions
1 2 3