# Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the promise 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$ (with the promise that $L(M)$ is deterministic, as 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.

-
Determinism and equivalence are well-known undecidable problems. You will find them in Hopcroft & Ullman (1979) for instance. –  Sylvain Jun 9 '11 at 20:11
Yes, they are well known undecidable problems but I'm not asking whether it's possible to decide determinism. The equivalence which I'm asking is of a PDA which definitely accepts a deterministic language and a DPDA. Unless I've missed something there's no obvious reason why that should be undecidable, I can't see why it should follow from the undecidability of the equivalence problem for PDAs. –  Sam Jones Jun 9 '11 at 21:56
my bad, I read your post too fast. Interesting question actually. –  Sylvain Jun 10 '11 at 16:12

Take a deterministic TM $M$ and a word $w$. Consider its computation histories for the word $w$. Let $L$ be invalid histories (those which don't start with $w$, don't end with acceptance or are invalid). Either $L = A^{\ast}$ ($M$ doesn't accept $w$) or $L = A^{\ast} - \{h\}$ for some string $h$ ($M$ accepts $w$ with computation history $h$). $L$ is a DCFL, but you can't show a DPDA for it effectively. Even more, $L$ is regular.

Small clarification:

You asked if the following problem is decidable:

given PDA $M$ promised that $L(M)$ is a DCFL, and a DPDA $N$ determine if $L(M) = L(N)$.

The answer is no, and in fact the following stronger fact holds: The following problem is undecidable:

given PDA $M$ promised that $L(M)$ is regular, determine if $L(M)=A^{\ast}$.

-
I don't understand what you are doing. What is A? if A is the alphabet for the input of the TM then saying that the invalid histories is $A^{*}$ is saying that the TM accepts the empty set. Also what is a DCFG? Do you mean a DPDA? –  Sam Jones Jun 9 '11 at 22:06
@Sam Jones: Consider any computation history that doesn't start with word $w$ as invalid. Then invalid histories are $A^{\ast}$ if and only if $M$ doesn't accept word $w$. Yes, I meant DPDA. –  sdcvvc Jun 10 '11 at 9:35
You seem to be assuming that a Turing Machine can accept at most one word. You also haven't proved that you can't show a DPDA for $L=A^{*}$ or for $L=A^{*}-\{h\}$ you've simply stated it. I actually know how to construct DPDAs which accept each of those languages. –  Sam Jones Jun 10 '11 at 15:28
Because you could effectively compare it with all-accepting automaton, and determine if $M$ halts on $w$. If you want you can restrict $M$ itself to a machine that can accept at most $w$ (no other words), but this doesn't change anything. The only important thing is that $M$ is deterministic. –  sdcvvc Jun 11 '11 at 12:09
OK got it at last. –  Sylvain Jun 11 '11 at 12:30