Theory of Computation MCQs | Page - 1

Q. 1) = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

Q. 2) A spanning tree for a simple graph of order 24 has

Q. 3) If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

Q. 4) If G is a connected planar graph of v vertices e edges and r regions then

Q. 5) A Hamiltonian cycle in a Hamiltonian graph of order 24 has

Q. 6) The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S → aSa
S → aAa
A → bB
B → bB
B → c is

Q. 7) The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
AB → CD
CD → CE
C → aC
C → b
bE → bc is

Q. 8) The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S → aS
A → bB
B → cC
C → a is

Q. 9) P, Q, R are three languages. If P & R are regular and if PQ=R, then

Q. 10) 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.