Sind DPDAs ohne ein

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?$\epsilon$$\epsilon$

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.Γ ϵ $\Gamma$$\Gamma$$\epsilon$$\epsilon$

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.$\epsilon$

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 .$\epsilon$

Sie sind beispielsweise weniger leistungsfähig als DPDAs

$L = \{ a^n b^p c a^n \mid p,n > 0\} \cup \{ a^nb^pdb^p\mid p,n > 0 \}$

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

$\epsilon$

$\epsilon$