Sind DCFLs unter Umkehrung geschlossen?

Nach diesem Diagramm werden DCFLs unter Umkehrung geschlossen.

Ich bin jedoch nicht davon überzeugt, dass der intuitive Beweis (Umkehren der Pfeile der steuernden Finite-State-Maschine und Umschalten der Pushs und Pops) davon abhängt, dass bei der Auswahl des Nullübergangs aus dem Ausgangszustand (seit dem neuer Anfangszustand würde einen Nullübergang zu allen alten Endzuständen enthalten).

Dies würde den "umgekehrten PDA" einer DPDA nicht deterministisch machen, wenn es mehr als einen einzelnen Endzustand in der ursprünglichen DPDA gibt.

Was ist der Irrtum in meiner Argumentation? Oder gibt es einen anderen Weg, dies zu beweisen?

formal-languages context-free closure-properties pushdown-automata nondeterminism peteykun
quelle

Bitte lassen Sie mich wissen, ob meine StackOverflow-Antwort eine zusätzliche Erklärung erfordert. Das Problem bei Ihrem Beweisversuch ist folgendes: Der von Ihnen erstellte PDA ist nicht der einzige PDA für die Sprache, die er akzeptiert. Es könnte andere geben, die möglicherweise anders angekommen sind und deterministisch sind. Insbesondere können DCFLs von PDAs akzeptiert werden, die nicht deterministisch sind.

Patrick87

Richtig, deshalb ist mir klar, dass dies überhaupt kein "Beweis" ist, es hätte nur dann eine Bedeutung, wenn das Ergebnis immer eine DCFL wäre, was es nicht ist. Ich glaube, ich habe nur versucht, es mit der gleichen Methode zu beweisen, die für reguläre Sprachen verwendet wird, und bin gescheitert. Danke für das Gegenbeispiel!

Peteykun

L = b^{n} c^{n} \cap a b^{2} n c^{n}

$L={b^n c^n} \cap {a b^2n c^n}$

λ

$\lambda$

Antworten:

Ich habe Hopcroft und Ullman 1979 nachgeschlagen und auf Seite 281 steht, dass es nicht unter Umkehrung geschlossen ist. Aber ich fand keinen Beweis in meinem sehr schnellen Blick auf das relevante Kapitel.

Das Durchsuchen des Webs gibt auch eine negative Antwort mit einem Gegenbeispiel zum Stapelüberlauf durch ein Mitglied von CS (Notation angepasst):

$(a+b+c)^*WcW^R$ $W \in (a+b)^+$ $WcW$

$W^RcW(a+b+c)^*$ $W \in (a+b)^+$ $W^RcW$ $a$ $b$ $c$

Der Trick dabei ist, dass PDAs Eingaben von links nach rechts lesen müssen.

babou
quelle

Das ist absurd. Patrick87 lieferte die Beispiele, @Raphael erledigte die Hälfte der Bearbeitungsarbeit und ich bekam den Repräsentanten. Dann bekommen wir so wenig für echte Arbeit ... :)

Babou

Betrachten Sie es als "Findergebühr" :) Ich bin nur verwirrt, dass das System tatsächlich gut genug funktioniert, dass Sie meinen alten Beitrag gefunden haben. Das System funktioniert! Gegrüßet seist du SE!

Patrick87

{0^{i} 1^{i} 2^{j} ∣ i, j} \cup {0^{i} 1^{j} 2^{j} ∣ i, j}

$\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$

K = {0^{i} 1^{i} 2^{j} a ∣ i, j} \cup {0^{i} 1^{j} 2^{j} b ∣ i, j}

$K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$

K

$K$

a

$a$

b

$b$