# 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. Jun 9, 2011 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. Jun 9, 2011 at 21:56
• my bad, I read your post too fast. Interesting question actually. Jun 10, 2011 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$$). First of all, $$L$$ is effective CFL, in the sense that you can build a grammar/PDA recognising it. Moreover, $$L$$ is a (noneffective) DCFL, but you can't show a DPDA for it effectively. Even more, $$L$$ is (noneffective) 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? Jun 9, 2011 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. Jun 10, 2011 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. Jun 10, 2011 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. Jun 11, 2011 at 12:09
• OK got it at last. Jun 11, 2011 at 12:30