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.

📊 Theory of Computation
Q. = ∈{ } 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
💬 Discuss
✅ Correct Answer: (B) L2 is regular but not L1
📊 Theory of Computation
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.
💬 Discuss
✅ Correct Answer: (C) 23 edges
📊 Theory of Computation
Q. 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
💬 Discuss
✅ Correct Answer: (C) 6
📊 Theory of Computation
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.
💬 Discuss
✅ Correct Answer: (A) v-e+r=2
📊 Theory of Computation
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.
💬 Discuss
✅ Correct Answer: (B) 24 edges
📊 Theory of Computation
Q. 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
💬 Discuss
✅ Correct Answer: (B) is type 2 but not type 3
📊 Theory of Computation
Q. 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
💬 Discuss
✅ Correct Answer: (C) is type 1 but not type 2
📊 Theory of Computation
Q. 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
💬 Discuss
✅ Correct Answer: (A) is type 3
📊 Theory of Computation
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
💬 Discuss
✅ Correct Answer: (C) Q need not be regular
📊 Theory of Computation
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
💬 Discuss
✅ Correct Answer: (C) Both 1 and 2 are true statements

Jump to

Explore More Categories

Click on category to learn MCQs of that category.

📱 Download Our App

Learn MCQs on the go with our easy-to-use Android app

Get it on Google Play