Baumstapelautomat

Ein Baumstapel -Automaton^[a] (Plural: Baumstapelautomaten) ist a Formalismus Betrachtet in Automatenheorie. Es ist ein Finite State Automaton mit der zusätzlichen Fähigkeit, a zu manipulieren Baum-Shaped Stapel. Es ist ein Automat mit Speicher^[2] dessen Speicher ungefähr den Konfigurationen von a ähnelt Thread Automaton. Eine eingeschränkte Klasse von Baumstapelautomaten erkennt genau die Sprachen erzeugt durch mehrere Kontextfreie Grammatiken^[3] (oder lineare kontextfreie Umschreibungssysteme).

Definition

Baumstapel

Ein Baumstapel mit Stapelzeiger 1.2 und Domain {ε, 1, 42, 1,2, 1,5, 1.5.3}

Für ein endliches und nicht leeres Set $Γ$ , a Baumstapel vorbei $Γ$ ist ein Tupel $(t, p)$ wo

$t$ ist ein Teilfunktion Von Saiten positiver Ganzzahlen bis zum Set $Γ \cup {@$ } mit Präfix-abgeschlossen^[b] Domain (genannt Baum),
$@$ (genannt Bodensymbol) ist nicht in $Γ$ und erscheint genau an der Wurzel von $t$ , und
$p$ ist ein Element der Domäne von $t$ (genannt Stapelzeiger).

Das Set aller Baumstapel stapelt sich $Γ$ wird bezeichnet durch $Ts (Γ)$ .

Der Satz von Prädikate an $Ts (Γ)$ , bezeichnet durch $Pred (Γ)$ enthält die folgenden einstellig Prädikate:

$Stimmt$ Welches gilt für jeden Baumstapel $Γ$ ,
$Unterseite$ Welches gilt für Baumstapel, deren Stapelzeiger auf das untere Symbol zeigt, und
$gleich (γ)$ Das gilt für einen Baumstapel $(t, p)$ wenn $t (p) = γ$ ,

für jeden $γ \in Γ$ .

Der Satz von Anweisungen an $Ts (Γ)$ , bezeichnet durch $Instrument (Γ)$ , enthält die folgenden Teilfunktionen:

$ID: TS (Γ) \to ts (Γ)$ Welches ist die Identitätsfunktion auf $Ts (Γ)$ ,
$drücken n, γ : Ts (Γ) \to ts (Γ)$ was für einen bestimmten Baumstapel hinzugefügt wird $(t, p)$ ein Paar $(pn \mapsto γ)$ zum Baum $t$ und setzt den Stapelzeiger auf $pn$ (d. h. es drückt $γ$ zum $n$ -Th Kinderposition) wenn $pn$ ist noch nicht im Bereich von $t$ ,
$hoch n : Ts (Γ) \to ts (Γ)$ Dies ersetzt den aktuellen Stapelzeiger $p$ durch $pn$ (d. H. Es bewegt den Stapelzeiger auf die $n$ -Th Kinderposition) wenn $pn$ ist in der Domäne von $t$ ,
$Down: TS (Γ) \to ts (Γ)$ das das letzte Symbol aus dem Stapelzeiger entfernt (d. H. Es verschiebt den Stapelzeiger in die übergeordnete Position) und
$einstellen γ : Ts (Γ) \to ts (Γ)$ Dies ersetzt das Symbol derzeit unter dem Stapelzeiger durch $γ$ ,

Für jede positive Ganzzahl $n$ Und jeder $γ \in Γ$ .

Illustration der Anweisungs -ID auf einem Baumstapel

Illustration des Befehls auf einen Baumstapel

Illustration der Anweisungen auf einem Baumstapel nach oben und unten

Abbildung des Befehlssatzes auf einem Baumstapel

Baumstapel Automaten

A Baumstapelautomat ist ein 6-Tupel $A = (Q, Γ, Σ, q i, δ, Q f)$ wo

$Q$ , $Γ$ , und $Σ$ sind endliche Sets (deren Elemente genannt werden Zustände, Stapelsymbole, und Eingabymbole, beziehungsweise),
$q i \in Q$ (das Ausgangszustand),
$δ \subseteq Flosse. Q \times (Σ \cup {ε}) \times Pred (Γ) \times Instrument (Γ) \times Q$ (deren Elemente genannt werden Übergänge), und
$Q f \subseteq ts (Γ)$ (deren Elemente genannt werden letzte Zustände).

A Konfiguration von $A$ ist ein Tupel $(q, c, w)$ wo

$q$ ist ein Staat (der aktuellen Zustand),
$c$ ist ein Baumstapel (der Aktueller Baumstapel), und
$w$ ist ein Wort vorbei $Σ$ (das verbleibendes Wort gelesen werden).

Ein Übergang $τ = (q 1, u, p, f, q 2)$ ist zutreffend zu einer Konfiguration $(q, c, w)$ wenn

$q 1 = q$ ,
$p$ ist wahr auf $c$ ,
$f$ ist definiert für $c$ , und
$u$ ist ein Präfix von $w$ .

Das Übergangsbeziehung von $A$ ist der binäre Beziehung $⊢$ auf Konfigurationen von $A$ Das ist die Vereinigung aller Beziehungen $⊢ τ$ für einen Übergang $τ = (q 1, u, p, f, q 2)$ wo, wann immer $τ$ ist anwendbar auf $(q, c, w)$ , wir haben $(q, c, w) ⊢ τ (q 2, f (c), v)$ und $v$ wird von $w$ Durch Entfernen des Präfixes $u$ .

Das Sprache von $A$ ist die Menge aller Wörter $w$ Für das gibt es einen Staat $q \in Q f$ und etwas Baumstapel $c$ so dass $(q i, c i, w) ⊢ * (q, c, ε)$ wo

$⊢ *$ ist der Reflexive transsitive Schließung von $⊢$ und
$c i = (t i, ε)$ so dass $t i$ zugewiesen für $ε$ das Symbol $@$ und ist sonst undefiniert.

Anmerkungen

^ Nicht zu verwechseln mit einem Gerät mit dem gleichen Namen, der 1990 von Wolfgang Golubski und Wolfram-M eingeführt wurde. Lippe ^[1]
^ Eine Reihe von Saiten ist Präfix geschlossen Wenn für jedes Element $w$ Im Set alle Präfixe von $w$ sind auch im Set.

Verweise

^ Golubski, Wolfgang und Lippe, Wolfram-M. (1990). Baumstapelautomaten. Verfahren des 15. Symposiums über mathematische Grundlagen der Informatik (MFCS 1990). Vorlesungsnotizen in Informatik, Vol. 452, Seiten 313–321, doi: 10.1007/bfb0029624.
^ Scott, Dana (1967). Einige Definitionsvorschläge für die Automatentheorie. Journal of Computer and System Sciences, Vol. 1 (2), Seiten 187–212, doi: 10.1016/s0022-0000 (67) 80014-x.
^ ^a ^b Denkinger, Tobias (2016). Eine Automatencharakterisierung für mehrere kontextfreie Sprachen. Proceedings der 20. Internationalen Konferenz über Entwicklungen in der Sprachtheorie (DLT 2016). Vorlesungsnotizen in Informatik, Vol. 9840, Seiten 138–150, doi: 10.1007/978-3-662-53132-7_12.

[2] Nicht zu verwechseln mit einem Gerät mit dem gleichen Namen, der 1990 von Wolfgang Golubski und Wolfram-M eingeführt wurde. Lippe ^[1]

[5] Eine Reihe von Saiten ist Präfix geschlossen Wenn für jedes Element $w$ Im Set alle Präfixe von $w$ sind auch im Set.

[GolLip90-1] Golubski, Wolfgang und Lippe, Wolfram-M. (1990). Baumstapelautomaten. Verfahren des 15. Symposiums über mathematische Grundlagen der Informatik (MFCS 1990). Vorlesungsnotizen in Informatik, Vol. 452, Seiten 313–321, doi: 10.1007/bfb0029624.

[Sco67-3] Scott, Dana (1967). Einige Definitionsvorschläge für die Automatentheorie. Journal of Computer and System Sciences, Vol. 1 (2), Seiten 187–212, doi: 10.1016/s0022-0000 (67) 80014-x.

[Den16-4] Denkinger, Tobias (2016). Eine Automatencharakterisierung für mehrere kontextfreie Sprachen. Proceedings der 20. Internationalen Konferenz über Entwicklungen in der Sprachtheorie (DLT 2016). Vorlesungsnotizen in Informatik, Vol. 9840, Seiten 138–150, doi: 10.1007/978-3-662-53132-7_12.

[a]

[2]

[3]

[b]

[1]