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:Q236.
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?Q238.
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 ?Q239.
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L (M) be the language accepted by a Turning machine M. Which of the following decision problems are undecidable ? I. Given a regular expression R and a string w, is w\in L(R)? II. Given a context-free grammar G, L(G)=\phi? III. Given a context-free grammar G, is L(G)=\Sigma* for some alphabet \Sigma? IV. Given a Turning machine M and a string w, is w\inL(M)?Q240.
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = \Phi? 2. G is a CFG. Is L(G) = \Sigma ^{*} ? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?