Wenn ein PDA M gegeben ist, so dass L (M) in DCFL ist, konstruiere ein DPDA N, so dass L (N) = L (M)

Ist es möglich, einen Algorithmus zu konstruieren, der einen Pushdown-Automaten als Eingabe verwendet, zusammen mit dem Versprechen, dass die von diesem Automaten akzeptierte Sprache eine deterministische kontextfreie Sprache ist und einen deterministischen Pushdown-Automaten ausgibt, der genau die akzeptierte Sprache akzeptiert von ? $M$ $L(M)$ $N$ $M$

Ein äquivalentes Problem wäre, einen Algorithmus zu konstruieren, der eine Pushdown-Automate (mit dem Versprechen, dass wie oben deterministisch ist) und eine deterministische Pushdown-Automate als Eingabe verwendet . Die Ausgabe wäre ja, wenn und nein, wenn . $M$ $L(M)$ $N$ $L(M) = L(N)$ $L(M)\neq L(N)$

Ich glaube, dass ein Algorithmus, der den ersten löst, einen Algorithmus ergibt, der den zweiten durch die Entscheidbarkeit der Äquivalenz deterministischer Pushdown-Automaten löst. Ich denke, eine Lösung für die zweite würde eine Lösung für die erste bedeuten, da wir alle deterministischen Pushdown-Automaten aufzählen und den Algorithmus nacheinander ausführen, sobald wir eine Ja-Instanz erhalten, geben wir diesen Automaten aus.

Ich frage mich, ob jemand etwas darüber weiß. Vielleicht ist es ein bekanntes Problem und / oder hat eine bekannte Lösung? Abgesehen davon halte ich es für entscheidend, wenn Sie die Einschränkung einführen, die besagt, dass die vom PDA erzeugte Sprache das Wortproblem einer Gruppe ist.

reference-request computability fl.formal-languages automata-theory Sam Jones
quelle

Determinismus und Äquivalenz sind bekannte unentscheidbare Probleme. Sie finden sie beispielsweise in Hopcroft & Ullman (1979) .

Sylvain

Ja, es sind bekannte unentscheidbare Probleme, aber ich frage nicht, ob es möglich ist, über Determinismus zu entscheiden. Die Äquivalenz, die ich frage, ist von einem PDA, der definitiv eine deterministische Sprache und einen DPDA akzeptiert. Wenn ich nichts verpasst habe, gibt es keinen offensichtlichen Grund, warum dies unentscheidbar sein sollte. Ich kann nicht verstehen, warum es aus der Unentscheidbarkeit des Äquivalenzproblems für PDAs resultieren sollte.

Sam Jones

Mein schlechtes, ich habe deinen Beitrag zu schnell gelesen. Interessante Frage eigentlich.

Sylvain

Nehmen Sie ein deterministisches TM und ein Wort . Betrachten Sie die Berechnungshistorien für das Wort . Sei eine ungültige Geschichte (diejenigen, die nicht mit , nicht mit Akzeptanz enden oder ungültig sind). Entweder ( akzeptiert ) oder für eine Zeichenfolge ( akzeptiert mit dem Berechnungsverlauf ). Zuallererst ist eine effektive CFL in dem Sinne, dass Sie eine Grammatik / einen PDA erstellen können, der sie erkennt. Darüber hinaus ist $M$ $w$ $w$ $L$ $w$ $L = A^{\ast}$ $M$ $w$ $L = A^{\ast} - \{h\}$ $h$ $M$ $w$ $h$ $L$ $L$ ist eine (nicht effektive) DCFL, aber Sie können eine DPDA dafür nicht effektiv anzeigen. Darüber hinaus ist (nicht effektiv) regelmäßig. $L$

Kleine Klarstellung:

Sie haben gefragt, ob das folgende Problem entscheidbar ist:

gegebener PDA versprach, dass eine DCFL ist, und ein DPDA bestimmt, ob . $M$ $L(M)$ $N$ $L(M) = L(N)$

Die Antwort ist nein, und tatsächlich gilt die folgende stärkere Tatsache: Das folgende Problem ist unentscheidbar:

Wenn PDA versprochen hat, dass regulär ist, bestimmen Sie, ob . $M$ $L(M)$ $L(M)=A^{\ast}$

sdcvvc
quelle

A^{*}

$A^{*}$

w

$w$

A^{*}

$A^{\ast}$

M

$M$

w

$w$

L = A^{*}

$L=A^{*}$

L = A^{*} - {h}

$L=A^{*}-\{h\}$

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

OK, endlich.

Sylvain

Wenn ein PDA M gegeben ist, so dass L (M) in DCFL ist, konstruiere ein DPDA N, so dass L (N) = L (M)

Antworten: