Undecidability
Q11.
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?Q12.
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?Q13.
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-freeQ14.
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is true?Q15.
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet {0, 1}. S2: Set of all syntactically valid C programs. S3: Set of all languages over the alphabet {0, 1}. S4: Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?Q17.
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi? II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = \phi?