Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. The production Grammar is {S->aSbb,S->abb} is
a. type-3 grammar
b. type-2 grammar
c. type-1 grammar
d. type-0 grammar
Q. Which one of the following is true regarding FOTRAN?
a. It is a context free language
b. It is a context sensitive language
c. It is a regular language
d. None of the above
Q. 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
Q. The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :
a. (0+1+2)*
b. 0*1*2*
c. 0* + 1 + 2
d. (0+1)*2*
Q. Suppose that a problem A is known to have a polynomial-time verificationalgorithm. Which of the following statements can be deduced.
a. A is in NP.
b. A is in NP but not P
c. A is in both NP and P.
d. A is NP-complete.
Q. Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.
a. Assertions (a) and (b) are both true.
b. Neither (a) nor (b) is true.
c. Both False
d. None of above
Q. A PC not connected to a network is equivalent to
a. A Deterministic Finite-State Automaton,
b. A Turing Machine,
c. A Push-Down Automaton,
d. None of the above.
Q. Recursively enumerable languages are not closed under:
a. Union
b. Intersection
c. Complementation
d. Concatenation
Q. Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
a. (L1)’ is recursive and (L2)’ is recursively enumerable
b. (L1)’ is recursive and (L2)’ is not recursively enumerable
c. (L1)’ and (L2)’ are recursively enumerable
d. (L1)’ is recursively enumerable and (L2)’ is recursive
Q. Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
a. R is NP-complete
b. R is NP-hard
c. Q is NP-complete
d. Q is NP-hard
Q. A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement
a. Turing machine
b. Pushdown automata
c. Context free languages
d. Regular languages
Q. Which of the following statement is true?
a. All languages can be generated by CFG
b. The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
c. Any regular languages have an equivalent CFG.
d. The class of CFG is not closed under union.
Q. Recursively enumerable languages are not closed under
a. Complementation
b. Union
c. Intersection
d. None of the above