Home / Engineering / Theory of Computation MCQs / Page 13

Theory of Computation MCQs | Page - 13

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. 121) Which statement is true?

(A) The PDA must have one accept state and one reject state
(B) The PDA must have one accept state and two reject state
(C) The PDA must have two accept state and two reject state
(D) There is no reject state in the PDA.
View Answer Discuss Share

Q. 122) TM is more powerful than FSM because

(A) The tape movement is confined to one direction
(B) It has no finite state control
(C) It has the capability to remember arbitrary long sequences of input symbols
(D) None of these
View Answer Discuss Share

Q. 123) The symbols that can’t be replaced by anything are called -----------------

(A) Productions
(B) Terminals
(C) Non-terminals
(D) All of above
View Answer Discuss Share

Q. 124) Left hand side of a production in CFG consists of:

(A) One terminal
(B) More than one terminal
(C) One non-terminal
(D) Terminals and non-terminals
View Answer Discuss Share

Q. 125) Choose the incorrect statement:

(A) (a+b)aa(a+b)generates Regular language.
(B) A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language
(C) Every language that can be expressed by FA can also be expressed by RE
(D) None of these
View Answer Discuss Share

Q. 126) Choose the incorrect statement.

(A) A Mealy machine generates no language as such
(B) A Mealy machine has no terminal state
(C) For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine
(D) All of these
View Answer Discuss Share

Q. 127) In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

(A) Dead State
(B) Waste Basket
(C) Davey John Locker
(D) All of these
View Answer Discuss Share

Q. 128) Which statement is true?

(A) The tape of turing machine is infinite.
(B) The tape of turing machine is finite.
(C) The tape of turing machine is infinite when the language is regular
(D) The tape of turing machine is finite when the language is nonregular.
View Answer Discuss Share

Q. 129) If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:

(A) (r1)(r2)
(B) (r1 + r2)
(C) (r2)(r1)
(D) (r1)
View Answer Discuss Share

Q. 130) Which of the following will be used for text searching application-?

(A) NFA
(B) DFA
(C) PDA
(D) None of these
View Answer Discuss Share