Home / Engineering / Theory of Computation MCQs / Page 1

Theory of Computation MCQs | Page - 1

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. 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?

(A) L1 is regular but not L2
(B) L2 is regular but not L1
(C) Both L1 and L2 are regular
(D) Neither L1 nor L2 are regular
View Answer Discuss Share

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

(A) 12 edges
(B) 6 edges
(C) 23 edges
(D) None of above.
View Answer Discuss Share

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

(A) 3
(B) 4
(C) 6
(D) 5
View Answer Discuss Share

Q. 4) 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.
View Answer Discuss Share

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

(A) 12 edges.
(B) 24 edges
(C) 23 edges
(D) None of above.
View Answer Discuss Share

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

(A) is type 3
(B) is type 2 but not type 3
(C) is type 1 but not type 2
(D) is type 0 but not type 1
View Answer Discuss Share

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

(A) is type 3
(B) is type 2 but not type 3
(C) is type 1 but not type 2
(D) is type 0 but not type 1
View Answer Discuss Share

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

(A) is type 3
(B) is type 2 but not type 3
(C) is type 1 but not type 2
(D) is type 0 but not type 1
View Answer Discuss Share

Q. 9) 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
View Answer Discuss Share

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.

(A) 1 only
(B) 2 only
(C) Both 1 and 2 are true statements
(D) None is true
View Answer Discuss Share