Theory of Computation MCQs | Page - 11

Q. 101) Which of the following problem is undecidable?

Q. 102) Recursive languages are

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?

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 ?

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

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?

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

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

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

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