Papier mit dem Beweis, dass nicht deterministisch kontextfrei ist?

Diese Vorlesungsfolien skizzieren einen Beweis dafür, dass von keinem deterministischen Pushdown akzeptiert werden kann Automat. Leider geben die Folien keinen Hinweis darauf, woher der Beweis stammt. $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$

Ich habe mich gefragt, ob jemand eine wissenschaftliche Arbeit oder ein Lehrbuch kennt, das einen vollständigen Beweis liefert. Ich würde es gerne zitieren können, aber ich konnte keinen finden.

formal-languages reference-request automata pushdown-automata nondeterminism jmite
quelle

Als Hinweis: Die Folien folgen demselben Argument wie das, das ich in einer verwandten Frage zu Pumping Lemma für deterministische CFL verwende. (Dies ist natürlich ein nicht pumpendes Argument.)

Hendrik

Antworten:

Das Ergebnis wird in Ginsburg und Greibach, Deterministische kontextfreie Sprachen , Inform. Control 9 (6), 620–648, 1966 , Theorem 4.1 auf Seite 24 (643). Der Beweis sieht jedoch etwas anders aus.

Yuval Filmus
quelle

Genial! Ich danke dir sehr! Ich hatte Verweise auf dieses Papier gesehen, hatte aber Probleme, eine PDF-Kopie zu finden.

Jmite

Wie haben Sie das aus Neugier gefunden? Wussten Sie nur spontan, in welchem Papier es sich befand, oder haben Sie irgendwie danach gesucht? Ich versuche, meine Fähigkeiten zur

Papiersuche

Ich habe "deterministisch kontextfrei" gegoogelt und es war eines der Top-Ergebnisse. Das Abstract sah nicht allzu vielversprechend aus, aber in der Einleitung erwähnen sie dieses Ergebnis.

Yuval Filmus