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.

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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

M

Mr. Dubey • 51.32K Points
Coach

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