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