Sind DPDAs ohne ein

16

In der formalen Beschreibung deterministischer Pushdown-Automaten erlauben sie Bewegungen, bei denen die Maschine Symbole auf den Stapel kopieren oder schieben kann, ohne ein Symbol von der Eingabe zu lesen. Wenn diese Bewegungen nicht zulässig sind und der Stapel nur einmal nach jedem Symbollesevorgang geändert werden kann, sind die resultierenden Automaten für DPDAs gleich stark?ϵϵϵ

Es kann etwas trivial sein , die ich in Bezug fehle die Powerset von zur Verwendung als Ihr neues , so dass Sie „komprimieren“ bewegt sich in die entsprechende Automaten ohne sie, ähnlich wie Sie komprimieren kann bewegt sich in eine DFA. Nur scheint eine solche Konvertierung nicht so einfach zu sein wie für DFAs, und ich bin mir nicht sicher, ob dies überhaupt möglich ist.Γ ϵ ϵΓΓϵϵ

Sind die beiden also gleich stark? Ich frage nur , weil jeder zu übernehmen scheint , dass DPDAs hat bewegt und ich frage mich , warum diese Annahme besteht, da es wie ein komplexeres Modell scheint.ϵ

Phylliida
quelle
Okay. Gibt es also einen Grund, warum wir nur solche mit Zügen lernen ? ϵ
Phylliida
1
Also habe ich gerade gemerkt, dass Sie tatsächlich . Sie beginnen einfach in einem akzeptierten Zustand. Wenn Sie das erste a lesen , drücken Sie & auf den Stapel, und wenn Sie das zweite a lesen , drücken Sie # auf den Stapel. Danach schreiben Sie einen ein auf den Stapel für jeden anderen ein Sie lesen, mit dem Start eine Sie nach dem Drücken # , um den Stapel zu lesen. L={a2nbn}aaaaa
Phylliida
Wenn Sie dann a lesen, während Sie wissen, dass Sie eine ungerade Zahl von a 's gelesen haben , lehnen Sie ab (sitzen in einem festgefahrenen Zustand), andernfalls wechseln Sie in einen anderen Zustand und drücken ein a vom Stapel. Sie wiederholen dies für jedes b Lesen. Wenn schließlich während eines Parsen b , # an der Spitze des Stapels anstelle eines ein , geben Sie einen Zustand annehmen. Geben Sie dann einen Ablehnungsstatus ein, wenn weitere Symbole gelesen werden. Geben Sie in jedem Fall, der sich von den oben beschriebenen unterscheidet, einen Ablehnungsstatus ein. Funktioniert es? baabba
Phylliida
Klingt gut für mich.
Klaus Draeger
1
Korrigiere mich, wenn ich falsch liege, aber ich stimme zu. Ich glaube auch , dass man kann erkennen mit einem DPDA , dass Sie immer auf dem Eingabeband bewegt (nie zu stoppen). Der einzige schwierige Teil ist, es im Endzustand zu beenden. Die Annahme von DPDAs kann schwierig sein. {a2nbn}
Michael Wehar

Antworten:

18

Vielleicht habe ich einige relevante Informationen gefunden in:

Jean-Michel Autebert, Luc Boasson, Jean Berstel; Kontextfreie Sprachen und Pushdown-Automaten; Handbuch der formalen Sprachen; 1997, S. 111-174

DPDAs ohne -Übergänge werden als deterministische Echtzeit-Pushdown-Automaten bezeichnet .ϵ

Sie sind beispielsweise weniger leistungsfähig als DPDAs

L={anbpcanp,n>0}{anbpdbpp,n>0}

ist deterministisch und kann von einem DPDA erkannt werden, kann jedoch von keinem Echtzeit- DPDA erkannt werden .

ϵ

ϵ

Marzio De Biasi
quelle
1
Super, danke! Das beantwortet also den ersten Teil meiner Frage. Der zweite Teil ist - warum studieren wir diese nicht? Jeder scheint sich auf Nicht-Echtzeit zu konzentrieren, und das erscheint mir merkwürdig.
Phylliida
2
@DanielleEnsign: Wenn Sie herum googeln, können Sie einige Ergebnisse zu RDPDAs finden, zum Beispiel ist das Äquivalenzproblem entscheidend . Aber ich stimme Ihnen zu, sie haben nicht viel Aufmerksamkeit erregt.
Marzio De Biasi