Home / Engineering / Theory of Computation MCQs / Page 11

# Theory of Computation MCQs | Page - 11

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. 101) Which of the following problem is undecidable?`

(A) Membership problem for CFL
(B) Membership problem for regular sets
(C) Membership problem for CSL
(D) Membership problem for type 0 languages

## `Q. 102) Recursive languages are`

(A) A proper superset of CFL
(B) Always recognized by PDA
(C) Are also called type 0 languages
(D) Always recognized by FSA

## `Q. 103) Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?`

(A) X is decidable
(B) X is undecidable but partially decidable
(C) X is undecidable and not even partially decidable
(D) X is not a decision problem

(A) yx
(B) xyx
(C) x
(D) xyxyx

## `Q. 105) Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively`

(A) Regular, regular
(B) Not regular, regular
(C) Regular, not regular
(D) Context free, not regular

(A) L1 L2
(B) L1 ∩ L2
(C) L1 ∩ R
(D) L1 ∪ L2

## `Q. 107) The logic of pumping lemma is a good example of`

(A) Pigeon-hole principle
(B) Divide-and-conquer technique
(C) Recursion
(D) Iteration

## `Q. 108) For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by`

(A) (a + b ) * ab
(B) ab (a + b ) *
(C) a ( a + b ) * b
(D) b (a + b ) * a

## `Q. 109) Pumping lemma is generally used for proving that`

(A) Given grammar is regular
(B) Given grammar is not regular
(C) Whether two given regular expressions are equivalent or not
(D) None of these

## `Q. 110) What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc`

(A) Type 0
(B) Type 1
(C) Type 2
(D) Type 3

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