Undecidability
Q2.
Choose the correct alternatives (More than one may be correct).It is undecidable whether:Q6.
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?Q8.
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)?Q9.
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)?Q10.
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?