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

## `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.

(A) 3
(B) 4
(C) 6
(D) 5

## `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.

## `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.

## ```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

## ```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

## ```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

## `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

## ```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

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.