Gibt es Varianten von sichtbaren Pushdown-Automaten, mit denen Wörter auf den Stapel geschoben werden können?

Ich frage mich, ob es Papiere oder Forschungsergebnisse gibt, die sich mit sichtbaren Pushdown-Automaten befassen, aber es erlaubt, dass Wörter anstatt einzelner Buchstaben auf den Stapel geschoben werden.

Alternativ könnte eine Konstruktion, mit der Symbole auf symbols- verschoben werden können, dasselbe Ziel erreichen. $\epsilon$

Offensichtlich können solche Variationen gebildet werden, aber ich frage mich, ob sie die Schließ- und Entscheidbarkeitseigenschaften ruinieren, die VPAs interessant machen.

Ich betrachte eine Konstruktion, bei der der Stapel als Zähler verwendet wird, wobei er um Konstanten erhöht wird, die auf den gelesenen Anfangssymbolen basieren, und dann auf anderen gelesenen Symbolen heruntergezählt wird.

Für alle, die es nicht wissen, sind Pushdown-Automaten sichtbar, bei denen das Alphabet in Push-Symbole, Popp-Symbole und Symbole unterteilt werden kann, die den Stapel überhaupt nicht beeinflussen. Die Wahl zwischen Push und Popping wird vollständig durch das aktuell gelesene Symbol bestimmt. Sie sind unter Kreuzung, Vereinigung, Verkettung, Stern und Ergänzung geschlossen, was ihnen eine Fülle entscheidbarer Eigenschaften verleiht. Weitere Informationen finden Sie in diesem Artikel .

reference-request fl.formal-languages automata-theory context-free context-free-languages jmite
quelle

es scheint die offensichtliche Frage zu sein, ob solche Automaten Standard-Pushdown-Automaten mit den "Wörtern" entsprechen, die in Folgen von Zuständen umgewandelt wurden. Afaik, ja? Wenn nicht, wäre ein anschauliches Beispiel für einen Fall hilfreich, in dem dies fehlschlägt.

vzn

@vzn Sie können nicht gleichwertig sein. Diese sichtbaren PDAs scheinen strikt schwächer zu sein. Als ich das letzte Mal nachgesehen habe, wurden CFLs nicht unter Kreuzung geschlossen.

Kai

R E G

$REG$

D C F L

$DCFL$

Dieser Artikel dx.doi.org/10.1145/1516512.1516518 enthält eine grammatikalische Charakterisierung von VPDAs und eine Konstruktion für die Konvertierung zwischen Grammatik und VPDAs. Möglicherweise kann die Grammatik verwendet werden, um das Drücken ganzer Wörter zu simulieren?

Evgenij Thorstensen

Warum ist das Drücken eines Wortes auf ein Symbol gleichbedeutend mit dem Ermöglichen von Drücken auf Eps-Übergängen?

Domotorp

Mit epsilon drückt

Für die Version mit Push-on-Epsilon-Übergängen kann der Unentscheidbarkeitsnachweis der Pushdown-Automaten an diese neue Einstellung angepasst werden, sodass wir zumindest die folgenden Eigenschaften verlieren: Abschluss unter Komplementierung, Bestimmbarkeit, Entscheidbarkeit der Universalität und Inklusion.

$M$ $A$

$A$

# C_{0} & C_{0} $ (\bar{C_{0}})^{R} # C_{1} & C_{1} $ (\bar{C_{1}})^{R} # C_{2} & C_{2} $ (\bar{C_{2}})^{R} \dots # C_{n} & C_{n} $ (\bar{C_{n}})^{R}

$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$

$C_i$ $M$
$C_0$ $C_n$
$u^R$ $u$
$\overline{u}$ $u$
$\#,\&,\$$ $M$
$C_i\to C_{i+1}$ $M$

$A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ $C_i$ $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Worte schieben

$(S,R,u)$ $u\in A^*$ $a$ $(S,R,va)$ $(S',R',v)$ $S'$ $R'$

Denis
quelle

Gibt es Varianten von sichtbaren Pushdown-Automaten, mit denen Wörter auf den Stapel geschoben werden können?

Antworten: