Home / Engineering / Theory of Computation MCQs / Page 8

# Theory of Computation MCQs | Page - 8

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. 71) ___________ states are called the halt states.`

(A) ACCEPT and REJECT
(C) ACCEPT AND START
(D) ACCEPT AND WRITE

(A) State
(B) Transition
(C) Input Tape
(D) Output Tape

## `Q. 73) The PDA is called non-deterministic PDA when there are more than one out going edges from……… state`

(B) POP or REJECT
(D) PUSH or POP

## `Q. 74) If an effectively solvable problem has answered in yes or no, then this solution is called`

(A) Decision procedure
(B) Decision method
(C) Decision problem
(D) Decision making

## `Q. 75) The set which is not countable if we have ∑ = {a, b}, is`

(A) Set of all languages over ∑ accepted by turing machine
(B) Set of all regular languages over ∑
(C) Set of all strings over ∑
(D) Set of all languages over ∑

(A) n+1
(B) n+2
(C) n
(D) 2n

(A) 10
(B) 01
(C) 101
(D) 110

## `Q. 78) The set that can be recognized by a deterministic finite state automaton is`

(A) The set {1, 101, 11011, 1110111, …….}
(B) The set of binary string in which the number of 0’s is same as the number of1’s
(C) 1, 2, 4, 8……2n ….. written in binary
(D) 1, 2, 4, 8……2n ….. written in unary

## `Q. 79) What is the reason behind a Turing machine is more powerful than finite state machine FSM?`

(A) turing machine head movement is continued to one direction.
(B) turing machine head moment is in both directions i.e. left moment and right moment as well.
(C) turing machine has capability remember arbitrary long sequence of input string.
(D) all are correct.

## `Q. 80) A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.`

(A) 0
(B) exectly 2
(C) 2 or more
(D) both exectly 2 or more are correct

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