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
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share

Q. 104) If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

(A) yx
(B) xyx
(C) x
(D) xyxyx
View Answer Discuss Share

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
View Answer Discuss Share

Q. 106) If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

(A) L1 L2
(B) L1 ∩ L2
(C) L1 ∩ R
(D) L1 ∪ L2
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share