Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. A spanning tree for a simple graph of order 24 has
a. 12 edges
b. 6 edges
c. 23 edges
d. None of above.
Q. If G is a connected planar graph of v vertices e edges and r regions then
a. v-e+r=2
b. e-v+r=2
c. v+e-r=2
d. None of above.
Q. A Hamiltonian cycle in a Hamiltonian graph of order 24 has
a. 12 edges.
b. 24 edges
c. 23 edges
d. None of above.
Q. P, Q, R are three languages. If P & R are regular and if PQ=R, then
a. Q has to be regular
b. Q cannot be regular
c. Q need not be regular
d. Q has to be a CFL
Q. Which of the following is true with respect to Kleene’s theorem?1 A regular language is accepted by a finite automaton.2 Every language is accepted by a finite automaton or a turingmachine.
a. 1 only
b. 2 only
c. Both 1 and 2 are true statements
d. None is true
Q. Automaton accepting the regular expression of any number of a ' s is:
a. a*
b. ab*
c. (a/b)*
d. a*b*c
Q. Grammars that can be translated to DFAs:
a. Left linear grammar
b. Right linear grammar
c. Generic grammar
d. All of these
Q. Regular expressions are
a. Type 0 language
b. Type 1 language
c. Type 2 language
d. Type 3 language
Q. The regular expression 0*(10)* denotes the same set as
a. (1*0)*1*
b. 0+(0+10)*
c. (0+1)*10(0+1)*
d. None of the above
Q. Which of the statements is true:
a. The complement of a regular language is always regular.
b. Homomorphism of a regular language is always regular.
c. Both of the above are true statements
d. None of the above
Q. The regular sets are closed under:
a. Union
b. Concatenation
c. Kleene closure
d. All of the above
Q. Any given transition graph has an equivalent:
a. regular
b. DFSM (Deterministic Finite State Machine)
c. NDFSM
d. All of them