Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. The logic of pumping lemma is a good example of
a. Pigeon-hole principle
b. Divide-and-conquer technique
c. Recursion
d. Iteration
Q. For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by
a. (a + b ) * ab
b. ab (a + b ) *
c. a ( a + b ) * b
d. b (a + b ) * a
Q. Pumping lemma is generally used for proving that
a. Given grammar is regular
b. Given grammar is not regular
c. Whether two given regular expressions are equivalent or not
d. None of these
Q. What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc
a. Type 0
b. Type 1
c. Type 2
d. Type 3
Q. Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding productionA —>aB {print “(1)” A —> c {print “1”),B —>Ab {print *2”}.When parser is aaacbbb, then string printed
a. 0202021
b. 1202020
c. 1020202
d. None of these
Q. Basic limitation of FSM is that it
a. Cannot remember arbitrary large amount of information
b. Sometimes fails to recognize grammars that are regular
c. Sometimes recognizes grammars are not regular
d. None of these
Q. Which of the following are decidable?1) Whether the intersection of two regular language is infinite.2) Whether a given context free language is regular.3) Whether two push down automata accept the same language.4) Whether a given grammar is context free.
a. 1 and 2
b. 1 and 4
c. 2 and 3
d. 2 and 4
Q. If L and L¯ are recursively enumerable, then L is
a. Regular
b. Context free
c. Context sensitive
d. Recursive
Q. Which of the following problems is undecidable?
a. Membership problem for CFGs
b. Ambiguity problem for CFGs.
c. Finiteness problem for FSAs.
d. Equivalence problem for FSAs.
Q. Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)
a. Context Free Language
b. Context sensitive language
c. Regular language
d. Languages recognizable by Turing machine
Q. Which of the following statements is/are FALSE?(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.(2) Turing recognizable languages are closed under union and complementation.(3) Turing decidable languages are closed under intersection and complementation(4) Turing recognizable languages are closed under union and intersection.
a. 1 and 4 only
b. 1 and 3 only
c. 2 only
d. 3 only
Q. 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.
Q. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
a. Both DHAM3 and SHAM3 are NP-hard
b. SHAM3 is NP-hard, but DHAM3 is not
c. DHAM3 is NP-hard, but SHAM3 is not
d. Neither DHAM3 nor SHAM3 is NP-hard