<p>Take a deterministic TM <span class="math-container">$M$</span> and a word <span class="math-container">$w$</span>. Consider its <a href="http://en.wikipedia.org/wiki/Computation_history#Decidability_results" rel="nofollow noreferrer">computation histories</a> for the word <span class="math-container">$w$</span>. Let <span class="math-container">$L$</span> be invalid histories (those which don't start with <span class="math-container">$w$</span>, don't end with acceptance or are invalid). Either <span class="math-container">$L = A^{\ast}$</span> (<span class="math-container">$M$</span> doesn't accept <span class="math-container">$w$</span>) or <span class="math-container">$L = A^{\ast} - \{h\}$</span> for some string <span class="math-container">$h$</span> (<span class="math-container">$M$</span> accepts <span class="math-container">$w$</span> with computation history <span class="math-container">$h$</span>). First of all, <span class="math-container">$L$</span> is effective CFL, in the sense that you can build a grammar/PDA recognising it. Moreover, <span class="math-container">$L$</span> is a (noneffective) DCFL, but you can't show a DPDA for it effectively. Even more, <span class="math-container">$L$</span> is (noneffective) regular.</p>

<p>Small clarification:</p>

<p>You asked if the following problem is decidable:</p>

<p>given PDA <span class="math-container">$M$</span> promised that <span class="math-container">$L(M)$</span> is a DCFL, and a DPDA <span class="math-container">$N$</span> determine if <span class="math-container">$L(M) = L(N)$</span>. </p>

<p>The answer is no, and in fact the following stronger fact holds: The following problem is undecidable:</p>

<p>given PDA <span class="math-container">$M$</span> promised that <span class="math-container">$L(M)$</span> is regular, determine if <span class="math-container">$L(M)=A^{\ast}$</span>.</p>

CC BY-SA 3.0
2011-06-09T22:06:51.650Z
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
CC BY-SA 3.0
2011-06-10T09:35:33.297Z
@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
CC BY-SA 3.0
2011-06-10T15:28:34.260Z
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
CC BY-SA 3.0
2011-06-10T18:36:29.117Z
I don't. The PDA for $L$ checks if the given history starts with $w$ (if not, it accepts), is the history consistent (if not, it accepts) and does it end with accepting state (if not, it accepts). Then $L = A^{\ast}$ iff $M$ doesn't accept $w$.
sdcvvc
CC BY-SA 3.0
2011-06-11T11:28:30.137Z
Why can't you show a DPDA effectively for it?  And I have some doubts about regularity as well.
Sylvain
CC BY-SA 3.0
2011-06-11T12:09:28.773Z
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
CC BY-SA 3.0
2011-06-11T12:30:41.667Z
OK got it at last.
Sylvain
CC BY-SA 3.0
2011-06-13T18:23:24.127Z
Ok, I was missing that you've fixed the word $w.$ Yes, I agree that it is undecidable. Thanks!
Sam Jones
CC BY-SA 4.0
2018-10-04T12:30:12.263Z
a minor remark: while you cannot effectively construct a finite automaton or DCFG for the regular language $L$, you can effectively construct a CFG for it.
Lorenzo
CC BY-SA 4.0
2018-10-23T18:26:12.340Z
Lorenzo: there is no such thing as DCFG. In this question, the PDA is already given as an input.
sdcvvc
CC BY-SA 4.0
2018-10-30T06:00:11.717Z
Right, but I was referring to the language $L$ that you use in the answer. BTW, there is a notion of DCFG, cf. https://en.m.wikipedia.org/wiki/Deterministic_context-free_grammar?wprov=sfla1
Lorenzo
CC BY-SA 4.0
2011-06-09T18:11:57.680Z
2018-10-30T14:45:37.900Z
2018-10-30T14:45:37.900Z
sdcvvc
<p>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$?</p>

<p>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 <em>yes</em> if $L(M) = L(N)$ and <em>no</em> if $L(M)\neq L(N)$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-09T20:11:35.687Z
Determinism and equivalence are well-known undecidable problems.  You will find them in [Hopcroft & Ullman (1979)](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) for instance.
Sylvain
CC BY-SA 3.0
2011-06-09T21:56:08.953Z
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
CC BY-SA 3.0
2011-06-10T16:12:35.300Z
my bad, I read your post too fast.  Interesting question actually.
Sylvain
<reference-request><computability><fl.formal-languages><automata-theory>
Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Sam Jones
# Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

(Asked by: username_0 on 2011-06-09)

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.

**Tags:** reference-request, computability, fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: Determinism and equivalence are well-known undecidable problems.  You will find them in [Hopcroft & Ullman (1979)](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) for instance.  
> **username_0**: 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.  
> **username_1**: my bad, I read your post too fast.  Interesting question actually.  

---

## 1 answers

### Answer by username_2 on 2011-06-09. Score: 9 | Accepted answer

Take a deterministic TM $M$ and a word $w$. Consider its [computation histories](http://en.wikipedia.org/wiki/Computation_history#Decidability_results) 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}$.

> **Comments:**
> **username_0**: 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?  
> **username_2**: @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.  
> **username_0**: 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.  
> **username_2**: I don't. The PDA for $L$ checks if the given history starts with $w$ (if not, it accepts), is the history consistent (if not, it accepts) and does it end with accepting state (if not, it accepts). Then $L = A^{\ast}$ iff $M$ doesn't accept $w$.  
> **username_1**: Why can't you show a DPDA effectively for it?  And I have some doubts about regularity as well.  
> **username_2**: 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.  
> **username_1**: OK got it at last.  
> **username_0**: Ok, I was missing that you've fixed the word $w.$ Yes, I agree that it is undecidable. Thanks!  
> **username_3**: a minor remark: while you cannot effectively construct a finite automaton or DCFG for the regular language $L$, you can effectively construct a CFG for it.  
> **username_2**: Lorenzo: there is no such thing as DCFG. In this question, the PDA is already given as an input.  
> **username_3**: Right, but I was referring to the language $L$ that you use in the answer. BTW, there is a notion of DCFG, cf. https://en.m.wikipedia.org/wiki/Deterministic_context-free_grammar?wprov=sfla1  

---

