Theory of Computation
Q231.
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?Q232.
Choose the correct alternatives (More than one may be correct).It is undecidable whether:Q233.
Consider two languages L1 and L2 each on the alphabet \Sigma. Let f:\Sigma \rightarrow \Sigma be a polynomial time computable bijection such that (\forall x)[x \in L1 \; \; if \; \; f(x) \in L2]. Further, let f^{-1} be also polynomial time computable. Which of the following CANNOT be true?Q234.
Define languages L0 and L1 as follows : L0 = {< M, w, 0 > | M halts on w} L1 = {< M, w, 1 > | M does not halts on w} Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L=L0 \cup L1. Which of the following is true ?Q235.
Let A \leq _{m}B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?Q236.
Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-freeQ238.
Let \Sigma be a finite non-empty alphabet and let 2^{\Sigma^{*}} be the power set of \Sigma^{*} . Which one of the following is TRUE?Q239.
Consider the following problem x . Given a Turing machine M over the input alphabet \Sigma, any state q of M. And a word w \in \Sigma *) does the computation of M on w visit the state q ? Which of the following statements about x is correct ?Q240.
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is \bar{L} also context-free? 3) If L is a regular language, then, is \bar{L} also regular? 4) If L is a recursive language, then, is \bar{L} also recursive?