Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free language and outputs a deterministic pushdown automaton $N$ which accepts precisely the language accepted by $M$?


An equivalent problem would be to construct an algorithm which takes as input a pushdown automata $M$ (such that $L(M)$ is deterministic, as in the above) and a deterministic pushdown automata $N$. The output would be yes if $L(M) = L(N)$ and no if $L(M)\neq L(N)$


I believe that an algorithm solving the first would give an algorithm solving the second by the decidability of equivalence of deterministic pushdown automata. I think a solution to the second would imply a solution to the first as we enumerate all deterministic pushdown automata and run the algorithm on them one by one, once we get a yes instance we output that automaton.


I wonder if anyone knows anything about this? Maybe it's a known problem and/or has a known solution? As an aside, I believe it is decidable if you introduce the restriction which says that the language generated by the PDA is the word problem of a group.



Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Undecidable, see here: <https://cstheory.stackexchange.com/questions/6947/given-a-pda-m-such-that-lm-is-in-dcfl-construct-a-dpda-n-such-that-ln-lm>


