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
(B) ACCEPT and READ
(C) ACCEPT AND START
(D) ACCEPT AND WRITE
View Answer Discuss Share

Q. 72) The part of an FA, where the input string is placed before it is run, is called _______

(A) State
(B) Transition
(C) Input Tape
(D) Output Tape
View Answer Discuss Share

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

(A) START or READ
(B) POP or REJECT
(C) READ or POP
(D) PUSH or POP
View Answer Discuss Share

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
View Answer Discuss Share

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 ∑
View Answer Discuss Share

Q. 76) How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?

(A) n+1
(B) n+2
(C) n
(D) 2n
View Answer Discuss Share

Q. 77) Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is

(A) 10
(B) 01
(C) 101
(D) 110
View Answer Discuss Share

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
View Answer Discuss Share

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.
View Answer Discuss Share

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
View Answer Discuss Share