Question

Consider the following problems regarding decidability.
I. Given a Turing Machine M, whether L(M) is context free.
II. Given a Non-deterministic PDA P, whether there exists a Deterministic Turing Machine M Such that both P and M accept the same languge.
III. Given a deterministic Turing Machine M, wheather there exists a Non Deterministic PDA P such that both P and M accept the same languge.
IV. Given a regular languge L, whether the complement of L is a DCFL
Which of the above problems are decidable ?

Answer 1

I is clearly undecidable.

II is decidable because the expressive power of Turing Machine is much higher than that of NPDAs. Turing Machine can handle all the way upto RE. so we can say that for every PDA N, there exists a DTM T which accepts L(N).

III. is undecible as the given Turing Machine may or may not be context free. If it is context free, then we can say yes, but if it is not context free, then there wont be any PDA for it. So the answer will be sometimes yes and sometimes no and hence Rice's Theorem applies and thus such a problem falls under the domain of nontrivial questions and therefore is undecidable.

IV . is trivally decidable as regular languges are closed under complemention and if we know that L is regular, we can say that every regular languge is a DCFL and the answer to this question will always be YES therefore this is a trival question and is therefore decidable.