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.

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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

M

Mr. Dubey • 51.17K Points
Coach

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