12
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Determinism and equivalence are well-known undecidable problems. You will find them in Hopcroft & Ullman (1979) for instance. $\endgroup$
    – Sylvain
    Jun 9, 2011 at 20:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sam Jones
    Jun 9, 2011 at 21:56
  • $\begingroup$ my bad, I read your post too fast. Interesting question actually. $\endgroup$
    – Sylvain
    Jun 10, 2011 at 16:12

1 Answer 1

Reset to default
9
$\begingroup$

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}$.

Improve this answer
$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$
    – Sam Jones
    Jun 9, 2011 at 22:06
  • $\begingroup$ @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. $\endgroup$
    – sdcvvc
    Jun 10, 2011 at 9:35
  • $\begingroup$ 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. $\endgroup$
    – Sam Jones
    Jun 10, 2011 at 15:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – sdcvvc
    Jun 11, 2011 at 12:09
  • 1
    $\begingroup$ OK got it at last. $\endgroup$
    – Sylvain
    Jun 11, 2011 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.