Pushdown -Automaten

In dem Theorie der Berechnungein Zweig von Theoretische Informatik, a Pushdown -Automaten (PDA) ist eine Art von Art von Automat das beschäftigt a Stapel.

Pushdown -Automaten werden in Theorien darüber verwendet, was von Maschinen berechnet werden kann. Sie sind fähiger als Finite-State-Maschinen aber weniger fähig als Turing -Maschinen (sehen unter).Deterministische Pushdown -Automaten kann alle erkennen deterministische kontextfreie Sprachen Während nicht deterministische Kontextfreie Sprachen, mit dem ersteren oft verwendet in Parser Entwurf.

Der Begriff "Pushdown" bezieht sich auf die Tatsache, dass die Stapel kann als "geschoben" wie ein Tablettspender in einer Cafeteria angesehen werden, da die Operationen nie mit anderen Elementen als dem Top -Element funktionieren. EIN StackautomatonIm Gegensatz dazu ermöglicht es den Zugang zu und Operationen auf tiefere Elemente. Stack Automata kann einen streng größeren Satz von Sprachen erkennen als Pushdown -Automaten.^[1] EIN verschachtelter Stackautomaton Ermöglicht den vollen Zugriff und ermöglicht auch, dass gestapelte Werte ganze Substacks sein und nicht nur einzelne endliche Symbole.

Informelle Beschreibung

A Finite-State-Maschine Betrachtet man nur das Eingangssignal und den aktuellen Zustand: Es hat keinen Stapel zum Arbeiten. Es wählt einen neuen Zustand, das Ergebnis der Befolgung des Übergangs. EIN Pushdown -Automat (PDA) unterscheidet sich von einer endlichen Zustandsmaschine auf zwei Arten:

1. Es kann die Oberseite des Stapels verwenden, um zu entscheiden, welcher Übergang erforderlich ist.
2. Es kann den Stapel im Rahmen der Durchführung eines Übergangs manipulieren.

Ein Pushdown -Automaton liest eine bestimmte Eingangszeichenfolge von links nach rechts. In jedem Schritt wählt es einen Übergang, indem eine Tabelle nach Eingabesymbol, aktuellem Zustand und dem Symbol oben im Stapel indiziert wird. Ein Pushdown -Automat kann auch den Stapel im Rahmen der Durchführung eines Übergangs manipulieren. Die Manipulation kann darin bestehen, ein bestimmtes Symbol auf die Oberseite des Stapels zu schieben oder die Oberseite des Stapels abzubrechen. Der Automat kann den Stapel alternativ ignorieren und ihn so lassen.

Zusammenstellen: Bei einem Eingangsymbol, einem aktuellen Zustand und einem Stapelsymbol kann der Automat einem Übergang zu einem anderen Zustand folgen und den Stapel optional manipulieren (drücken oder pop).

Wenn in jeder Situation höchstens ein solcher Übergangsmaßnahme möglich ist, wird der Automat genannt Deterministischer Pushdown -Automaten (DPDA). Wenn im Allgemeinen mehrere Aktionen möglich sind, wird der Automaton a genannt Allgemeines, oder Nichtdeterministisch, PDA. Eine bestimmte Eingangszeichenfolge kann einen nicht deterministischen Pushdown -Automat zu einer von mehreren Konfigurationssequenzen führen. Wenn einer von ihnen nach dem Lesen der vollständigen Eingangszeichenfolge zu einer akzeptierenden Konfiguration führt, soll der letztere zu dem gehören Sprache, die vom Automaten akzeptiert wird.

Formale Definition

Wir verwenden Standard -formelle Sprachnotation: ${\ displaystyle \ gamma ^{*}}$ bezeichnet den Satz der endlichen Länge Saiten über Alphabet ${\ displayStyle \ gamma}$ und ${\ displayStyle \ varepsilon}$ bezeichnet die leerer String.

Eine PDA wird offiziell als 7-Tupel definiert:

${\ displayStyle m = (q, \ sigma, \ gamma, \ delta, q_ {0}, z, f)}$ wo

• ${\ displayStyle q}$ ist ein endlicher Satz von Zustände
• ${\ displayStyle \ sigma}$ ist ein endliches Set, das als das bezeichnet wird Alphabet eingeben
• ${\ displayStyle \ gamma}$ ist ein endliches Set, das als das bezeichnet wird Stack Alphabet
• ${\ displayStyle \ Delta}$ ist eine endliche Teilmenge von $oder$, das Übergangsbeziehung
• ${\ displayStyle q_ {0} \ in q}$ ist der Staat starten
• ${\ displayStyle z \ in \ gamma}$ ist der Erstes Stapelsymbol
• ${\ displayStyle f \ subseteq q}$ ist der Satz von Staaten akzeptieren

Ein Element ${\ displayStyle (p, a, a, q, \ alpha) \ in \ delta}$ ist ein Übergang von ${\ displayStyle m}$. Es hat die beabsichtigte Bedeutung, dass ${\ displayStyle m}$im Zustand ${\ displayStyle p \ in q}$auf der Eingabe ${\ displayStyle a \ in \ sigma \ cup \ {\ varepsilon \}}$ und mit ${\ displayStyle a \ in \ gamma}$ als oberste Stacksymbol kann lesen ${\ displayStyle a}$, ändern Sie den Staat auf ${\ displayStyle q}$, Pop ${\ displayStyle a}$ersetzen es durch Schieben ${\ displaystyle \ alpha \ in \ gamma ^{*}}$. Das ${\ displayStyle (\ sigma \ cup \ {\ varepsilon \})}$ Die Komponente der Übergangsbeziehung wird verwendet, um zu formalisieren, dass die PDA entweder einen Buchstaben aus der Eingabe lesen kann oder die Eingabe unberührt bleibt.

In vielen Texten^{[2]: 110} Die Übergangsbeziehung wird durch eine (äquivalente) Formalisierung ersetzt, wo

• ${\ displayStyle \ Delta}$ ist der Übergangsfunktion, Kartierung ${\ displayStyle q \ times (\ sigma \ cup \ {\ varepsilon \}) \ Times \ gamma}$ in endliche Untergruppen von ${\ displayStyle q \ times \ gamma ^{*}}$

Hier ${\ displayStyle \ Delta (p, a, a)}$ enthält alle möglichen Handlungen im Zustand ${\ displayStyle p}$ mit ${\ displayStyle a}$ Auf dem Stapel beim Lesen ${\ displayStyle a}$ auf der Eingabe. Man schreibt zum Beispiel ${\ displayStyle \ Delta (p, a) = \ {(q, ba) \}}$ Genau wann ${\ displayStyle (q, ba) \ in \ {(q, ba) \}, (q, ba) \ in \ delta (p, a, a),}$ Weil ${\ displayStyle ((p, a, a), \ {(q, ba) \}) \ in \ delta}$. Beachten Sie, dass endlich In dieser Definition ist wichtig.

Berechnungen

Um die Semantik des Pushdown -Automatens zu formalisieren, wird eine Beschreibung der aktuellen Situation eingeführt. Jeder 3-Tupel ${\ displayStyle (p, w, \ beta) \ in q \ times \ sigma ^{*} \ times \ gamma ^{*}}$ wird eine sofortige Beschreibung (ID) von genannt ${\ displayStyle m}$, einschließlich des aktuellen Zustands, des Teils des Eingabebandes, das nicht gelesen wurde, und den Inhalt des Stapels (oberste Symbol zuerst geschrieben). Die Übergangsbeziehung ${\ displayStyle \ Delta}$ Definiert die Stufenbeziehung ${\ displayStyle \ vdash _ {m}}$ von ${\ displayStyle m}$ auf sofortige Beschreibungen. Für Anweisungen ${\ displayStyle (p, a, a, q, \ alpha) \ in \ delta}$ Es gibt einen Schritt ${\ displayStyle (p, ax, a \ gamma) \ vdash _ {m} (q, x, \ alpha \ gamma)}$, für jeden ${\ displaystyle x \ in \ sigma ^{*}}$ Und jeder ${\ displaystyle \ gamma \ in \ gamma ^{*}}$.

Im Allgemeinen sind Pushdown -Automaten nicht deterministisch ${\ displayStyle (p, w, \ beta)}}$ Es kann mehrere mögliche Schritte geben. Alle dieser Schritte können in einer Berechnung ausgewählt werden. Mit der obigen Definition in jedem Schritt wird immer ein einzelnes Symbol (oben am Stapel) aufgetaucht und ersetzt es durch so viele Symbole, wie dies erforderlich ist. Infolgedessen wird kein Schritt definiert, wenn der Stapel leer ist.

Berechnungen des Pushdown -Automatiks sind Sequenzen von Schritten. Die Berechnung beginnt im Anfangszustand ${\ displayStyle q_ {0}}$ Mit dem ersten Stapelsymbol ${\ displayStyle z}$ auf dem Stapel und eine Schnur ${\ displayStyle W}$ Auf dem Eingangsband, somit mit anfänglicher Beschreibung ${\ displayStyle (q_ {0}, w, z)}$. Es gibt zwei Akzeptanzmodi. Der Pushdown -Automaton akzeptiert entweder nach dem endgültigen Zustand, was bedeutet, dass der Automaton nach dem Lesen des Eingangs einen Akzeptanzstatus erreicht (in ${\ displayStyle f}$) oder es akzeptiert durch leeren Stack (${\ displayStyle \ varepsilon}$), was bedeutet, dass der Automaton nach dem Lesen seines Eingangs seinen Stapel entleert. Der erste Akzeptanzmodus verwendet den internen Speicher (Status), das zweite der externe Speicher (Stack).

Formal definiert man

1. $oder$ mit ${\ displayStyle f \ in f}$ und ${\ displayStyle \ gamma \ in \ gamma ^{*} \}}$ (endgültiger Zustand)
2. $oder$ mit ${\ displayStyle q \ in q \}}$ (leerer Stapel)

Hier ${\ displayStyle \ vdash _ {m}^{*}}$ repräsentiert die reflexiv und Transitive Schließung der Stufenbeziehung ${\ displayStyle \ vdash _ {m}}$ bedeutet eine beliebige Anzahl aufeinanderfolgender Schritte (Null, eine oder mehrere).

Für jeden einzelnen Pushdown -Automaten müssen diese beiden Sprachen keine Beziehung haben: Sie können gleich sein, aber dies ist normalerweise nicht der Fall. Eine Spezifikation des Automatons sollte auch die beabsichtigte Akzeptanzart enthalten. Beide Akzeptanzbedingungen übernommen alle Pushdown -Automaten definieren dieselbe Sprachenfamilie.

Satz. Für jeden Pushdown -Automaton ${\ displayStyle m}$ Man kann einen Pushdown -Automaten erstellen ${\ displayStyle m '}$ so dass ${\ displayStyle l (m) = n (m ')}}$und umgekehrt für jeden Pushdown -Automaton ${\ displayStyle m}$ Man kann einen Pushdown -Automaten erstellen ${\ displayStyle m '}$ so dass ${\ displayStyle n (m) = l (m ')}}$

Beispiel

Das Folgende ist die formale Beschreibung der PDA, die die Sprache erkennt ${\ displayStyle \ {0^{n} 1^{n} \ Mid N \ Geq 0 \}}}$ nach dem endgültigen Zustand:

${\ displayStyle m = (q, \ \ sigma, \ \ gamma, \ \ delta, \ q_ {0}, \ z, \ f)}$, wo

• Zustände: ${\ displayStyle q = \ {p, q, r \}}$
• Alphabet eingeben: ${\ displayStyle \ sigma = \ {0,1 \}}$
• Stack Alphabet: ${\ displayStyle \ gamma = \ {a, z \}}$
• Zustand starten: ${\ displayStyle q_ {0} = p}$
• Starten Sie Stacksymbol: Z
• Staaten akzeptieren: ${\ displayStyle f = \ {r \}}$

Die Übergangsbeziehung ${\ displayStyle \ Delta}$ besteht aus den folgenden sechs Anweisungen:

${\ displayStyle (p, 0, z, p, az)}$,

${\ displayStyle (p, 0, a, p, aa)}$,

${\ displayStyle (p, \ epsilon, z, q, z)}$,

${\ displayStyle (p, \ epsilon, a, q, a)}$,

${\ displayStyle (q, 1, a, q, \ epsilon)}$, und

${\ displayStyle (q, \ epsilon, z, r, z)}$.

In Worten sagen die ersten beiden Anweisungen das im Zustand p Jedes Mal das Symbol 0 ist gelesen, einer A wird auf den Stapel gedrückt. Schubsymbol A über einen anderen A wird formalisiert als Ersatztoper A durch Aa (Und ähnlich zum Schieben des Symbols A über a Z).

Die dritte und vierte Anleitung besagt, dass der Automaten jederzeit vom Staat wechseln kann p zu sagen q.

Die fünfte Anweisung besagt das im Staat qfür jedes Symbol 1 Lesen Sie, einer A ist geknallt.

Schließlich besagt der sechste Anweis q Staat zu akzeptieren r Nur wenn der Stapel aus einer einzigen besteht Z.

Es scheint keine allgemein verwendete Darstellung für PDA zu geben. Hier haben wir die Anweisung dargestellt ${\ displayStyle (p, a, a, q, \ alpha)}$ durch eine Kante vom Staat p zu sagen q beschriftet von ${\ displayStyle a; a/\ alpha}$ (lesen a; ersetzen A durch ${\ displayStyle \ alpha}$).

Verständnis des Berechnungsprozesses

Das Folgende zeigt, wie die obige PDA auf verschiedenen Eingangszeichenfolgen berechnet. Das Index M Aus dem Schrittsymbol ${\ displayStyle \ vdash}$ ist hier weggelassen.

PDA und kontextfreie Sprachen

Jeder Kontextfreie Grammatik Kann in einen äquivalenten nicht deterministischen Pushdown -Automaten umgewandelt werden. Der Ableitungsprozess der Grammatik wird in links links simuliert. Wo die Grammatik einen Nicht-Terminal umschreibt, nimmt die PDA den obersten Nicht-terminalen aus ihrem Stapel und ersetzt sie durch den rechten Teil einer grammatikalischen Regel (erweitern). Wenn die Grammatik ein Terminalsymbol erzeugt, liest die PDA ein Symbol aus der Eingabe, wenn es das oberste Symbol auf dem Stapel ist (passen). In gewissem Sinne enthält der Stapel der PDA die unverarbeiteten Daten der Grammatik, die einer Vorbestellung eines Derivationsbaums entsprechen.

Technisch gesehen hat die PDA bei einer kontextfreien Grammatik einen einzelnen Zustand 1, und ihre Übergangsbeziehung wird wie folgt konstruiert.

1. ${\ displayStyle (1, \ varepsilon, a, 1, \ alpha)}$ Für jede Regel ${\ displayStyle a \ to \ alpha}$ (erweitern)
2. ${\ displayStyle (1, a, a, 1, \ varepsilon)}}$ Für jedes Terminalsymbol ${\ displayStyle a}$ (passen)

Die PDA akzeptiert mit leerem Stapel. Sein anfängliches Stapelsymbol ist das Startsymbol der Grammatik.

Für eine kontextfreie Grammatik in Greibach Normale Form, definieren (1, γ) ∈ δ (1,a,A) Für jede Grammatikregel A → aγ liefert auch einen äquivalenten nicht -detterministischen Pushdown -Automat.^{[2]: 115}

Das Gegenteil, eine Grammatik für eine bestimmte PDA zu finden, ist nicht so einfach. Der Trick besteht darin, zwei Zustände der PDA in die Nicht -Terminals der Grammatik zu versetzen.

Satz. Für jeden Pushdown -Automaton ${\ displayStyle m}$ Man kann eine kontextfreie Grammatik konstruieren ${\ displayStyle g}$ so dass ${\ displayStyle n (m) = l (g)}$.^{[2]: 116}

Die Sprache der Strings, die durch einen deterministischen Pushdown -Automat (DPDA) akzeptiert wird deterministische kontextfreie Sprache. Nicht alle kontextfreien Sprachen sind deterministisch.^{[Anmerkung 1]} Infolgedessen ist die DPDA eine streng schwächere Variante der PDA. Sogar für reguläre SprachenEs gibt ein Problem der Größenexplosion: für jeden rekursive Funktion ${\ displayStyle f}$ und für willkürlich große ganze Zahlen ${\ displayStyle n}$Es gibt eine PDA mit Größe ${\ displayStyle n}$ Beschreibung einer regulären Sprache, deren kleinste DPDA zumindest hat ${\ displayStyle f (n)}$ Zustände.^[4] Für viele nicht reguläre PDAs würde jede äquivalente DPDA eine unbegrenzte Anzahl von Zuständen erfordern.

Ein endlicher Automat mit Zugriff auf zwei Stapel ist ein leistungsfähigeres Gerät, das mit der Stromversorgung von A entspricht Turing Maschine.^{[2]: 171} EIN linear begrenzter Automaten ist ein Gerät, das leistungsfähiger ist als ein Pushdown -Automat, aber weniger als eine Turing -Maschine.^{[Anmerkung 2]}

PDA- und Turing -Maschinen

Ein Pushdown-Automaton entspricht rechnerisch zu einer "eingeschränkten" Turing-Maschine (TM) mit zwei Bändern, die auf folgende Weise eingeschränkt sind. Auf dem ersten Band kann der TM nur die Eingabe lesen und sich von links nach rechts bewegen (es kann keine Änderungen vornehmen ). Auf dem zweiten Band kann es nur "Push "- und Pop" -Daten. Oder äquivalent kann es mit der Einschränkung gelesen, schreiben und sich nach rechts bewegen, dass die einzige Aktion, die es bei jedem Schritt ausführen kann -Das meiste Zeichen in der Saite (Push).

Dass eine PDA schwächer ist als ein TM kann auf die Tatsache gebracht werden, dass das Verfahren einige Daten löscht. Um eine PDA so stark wie ein TM zu machen, müssen wir die Daten speichern, die durch 'Pop' verloren gehen. Wir können dies erreichen, indem wir einen zweiten Stapel einführen. Im TM-Modell von PDA des letzten Absatzes entspricht dies einem TM mit 3 Bändern, wobei das erste Band das schreibgeschützte Eingangsband ist, und das 2. und das 3. Band sind die "Push and Pop" (Stapel) Bänder (Stapel) . Damit eine solche PDA eine bestimmte TM simuliert, geben wir das erste Band die Eingabe der PDA und halten beide Stapel leer. Anschließend drückt es den gesamten Eingang vom Eingangsband zum ersten Stapel. Wenn der gesamte Eingang in den 1. Stapel übertragen wird, gehen wir jetzt wie ein normales TM fort, wobei das Bewegung rechts am Klebeband das gleiche ist wie ein Symbol aus dem 1. Stapel und das Schieben eines (möglicherweise aktualisierten) Symbols in den zweiten Stapel, und Das Linken entspricht dem Sturz eines Symbols aus dem 2. Stapel und dem Schieben von (möglicherweise aktualisiertem) Symbol in den ersten Stapel. Wir haben daher eine PDA mit 2 Stapeln, die jeden TM simulieren können.

Generalized Pushdown Automaton (GPDA)

Eine GPDA ist eine PDA, die eine ganze Reihe bekannter Länge in den Stapel schreibt oder eine ganze Saite in einem Schritt aus dem Stapel entfernt.

Eine GPDA wird offiziell als 6-Tupel definiert:

${\ displayStyle m = (q, \ \ sigma, \ \ gamma, \ \ delta, \ q_ {0}, \ f)}$

wo ${\ displayStyle q, \ sigma \ ,, \ gamma \ ,, q_ {0}}$, und ${\ displayStyle f}$ sind genauso definiert wie eine PDA.

${\ displayStyle \, \ Delta}$: $oder$

ist die Übergangsfunktion.

Berechnungsregeln für eine GPDA sind die gleichen wie eine PDA, außer dass die ${\ displayStyle a_ {i+1}}$und ${\ displayStyle b_ {i+1}}$'S sind jetzt Saiten statt Symbole.

GPDAs und PDAs sind insofern gleichwertig, wenn eine Sprache von einer PDA erkannt wird, sie auch von einer GPDA erkannt wird und umgekehrt.

Man kann einen analytischen Beweis für die Äquivalenz von GPDAs und PDAs unter Verwendung der folgenden Simulation formulieren:

Lassen ${\ displaystyle \ delta (q_ {1}, w, x_ {1} x_ {2} \ cdot x_ {m}) \ longrightarrow (q_ {2}, y_ {1} y_ {2} ... y_ {n })}$ ein Übergang der GPDA sein

wo ${\ displayStyle q_ {1}, q_ {2} \ in q, w \ in \ sigma _ {\ epsilon}, x_ {1}, x_ {2}, \ ldots, x_ {m} \ in \ gamma ^{{{ *}, m \ geq 0, y_ {1}, y_ {2}, \ ldots, y_ {n} \ in \ gamma ^{*}, n \ geq 0}$.

Erstellen Sie die folgenden Übergänge für die PDA:

$oder }, \ epsilon, x_ {2}) & \ longrightarrow & (p_ {2}, \ epsilon) \\ & \ vdots & \\\ Delta '(p_ {m-1}, \ epsilon, x_ {m}) & \ longrightarrow & (p_ {m}, \ epsilon) \\\ delta '(p_ {m}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m+1}, y_ {n}) \\\\ Delta '(p_ {m+1}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m+2}, y_ {n-1}) \\ & \ vdots & \\\ Delta' (p_ {m) +n-1}, \ epsilon, \ epsilon) & \ longrightarrow & (q_ {2}, y_ {1}). \ end {array}}}$

Stackautomaton

Als Verallgemeinerung von Pushdown -Automaten, Ginsburg, Greibach und Harrison (1967) untersuchten Stack Automata, die zusätzlich nach links oder rechts in die Eingangszeichenfolge (umgeben von Sondermarkierungssymbolen umgeben sind, um das Ausrutschen zu verhindern) und im Stapel im schreibgeschützten Modus nach oben oder unten steigen.^[5][6] Ein Stack -Automat wird genannt Nichtzufer Wenn es nie aus dem Stapel kommt. Die Klasse von Sprachen, die von nicht deterministischen, nicht erasierten Stapelautomaten akzeptiert werden, ist Nspace(n²), was ein Superset der ist Kontextsensitive Sprachen.^[1] Die Klasse von Sprachen, die durch deterministische, nicht erasierte Stack -Automata akzeptiert werden, ist DSpace(n≤ log (n)).^[1]

Wechselnde Pushdown -Automaten

Ein Wechselnder Pushdown -Automaten (APDA) ist ein Pushdown -Automat mit einem Zustandssatz

• ${\ displayStyle q = q _ {\ existiert} \ cup q _ {\ forall}}$ wo $oder$.

Staaten in ${\ displayStyle q _ {\ existiert}}$ und ${\ displayStyle q _ {\ forall}}$ werden genannt existenziell bzw. Universal-. In einem existenziellen Zustand wählt eine APDA -Nichtdeterministisch den nächsten Zustand und akzeptiert, ob mindestens ein der resultierenden Berechnungen akzeptieren. In einem universellen Staat bewegt sich APDA in alle nächsten Zustände und akzeptiert, ob alle Die resultierenden Berechnungen akzeptieren.

Das Modell wurde von vorgestellt von Chandra, Kozen und Stockmeyer.^[7] Ladner, Lipton und Stockmeyer^[8] bewies, dass dieses Modell gleichwertig ist Nachfolger d.h. eine Sprache wird von einer APDA akzeptiert dann und nur dann, wennEs kann durch einen Exponential-Zeit-Algorithmus entschieden werden.

Aizikowitz und Kaminski^[9] eingeführt Synchronisierte alternierende Pushdown -Automata (SAPDA), die gleichwertig sind Konjunktivgrammatiken genauso wie nicht deterministische PDA entsprechen kontextfreien Grammatiken.

Siehe auch

• Stapelmaschine
• Kontextfreie Grammatik
• Finite Automaton
• Kontrollautomaton
• Warteschlangenautomat

Anmerkungen

Verweise

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Abschnitt 2.2: Pushdown Automata, S. 101–114.
• Jean-Michel Autert, Jean Berstel, Luc Boasson, Kontextfreie Sprachen und Push-Down-AutomatenIn: G. Rozenberg, A. Salomaa (Hrsg.), Handbuch der formalen Sprachen, vol. 1, Springer-Verlag, 1997, 111–174.

Externe Links

• JFLAP, Simulator für verschiedene Arten von Automata, einschließlich nicht deterministischer Pushdown -Automaten
• Koan, ein weiterer Simulator für mehrere Maschinentypen, einschließlich nicht deterministischer Pushdown -Automaten (C ++, Windows, Linux, MacOS)