In der Automaten-Theorie ist ein pushdown Automat (PDA) eine Schwankung des begrenzten Automaten, der von einem Stapel Gebrauch machen kann, der Daten enthält.

Operation

Automaten von Pushdown unterscheiden sich von Zustandsmaschinen auf zwei Weisen:

1. Sie können die Spitze des Stapels verwenden, um der Übergang zu entscheiden, zu nehmen.
2. Sie können den Stapel als ein Teil manipulieren, einen Übergang durchzuführen.

Automaten von Pushdown wählen einen Übergang durch das Indexieren eines Tisches durch das Eingangssignal, den aktuellen Staat und das Symbol an der Oberseite vom Stapel. Das bedeutet, dass jene drei Rahmen völlig den Übergang-Pfad bestimmen, der gewählt wird. Zustandsmaschinen schauen gerade auf das Eingangssignal und den aktuellen Staat: Sie haben keinen Stapel, um damit zu arbeiten. Automaten von Pushdown fügen den Stapel als ein Parameter für die Wahl hinzu.

Automaten von Pushdown können auch den Stapel als ein Teil manipulieren, einen Übergang durchzuführen. Zustandsmaschinen wählen einen neuen Staat, das Ergebnis von folgenden der Übergang. Die Manipulation kann sein, ein besonderes Symbol zur Spitze des Stapels zu stoßen, oder die Spitze des Stapels plötzlich zu verschwinden. Der Automat kann den Stapel wechselweise ignorieren, und ihn verlassen, wie es ist. Die Wahl der Manipulation (oder keiner Manipulation) wird durch den Übergang-Tisch bestimmt.

Stellen Sie zusammen: In Anbetracht eines Eingangssignals, aktuellen Staates und Stapel-Symbols, kann der Automat einem Übergang zu einem anderen Staat folgen, und fakultativ (Stoß oder Knall) den Stapel manipulieren.

Im Allgemeinen, pushdown Automaten kann mehrere Berechnung auf einer gegebenen Eingangsschnur haben, von der etwas in akzeptierenden Konfigurationen hinken kann, während andere nicht sind. So haben wir ein Modell, das als ein "nichtdeterministischer pushdown Automat" (NDPDA oder NPDA) technisch bekannt ist. Nichtdeterminismus bedeutet, dass es mehr geben kann als gerade ein Übergang, der verfügbar ist, um, in Anbetracht eines Eingangssignals, Staates und Stapel-Symbols zu folgen. Wenn in jeder Situation nur ein Übergang als Verlängerung der Berechnung verfügbar ist, dann ist das Ergebnis ein deterministischer pushdown Automat (DPDA), ein ausschließlich schwächeres Gerät.

Wenn wir einen begrenzten Automat-Zugang zu zwei Stapeln statt gerade ein erlauben, erhalten wir ein stärkeres Gerät, das in der Macht zu einer Maschine von Turing gleichwertig ist. Ein geradliniger begrenzter Automat ist ein Gerät, das stärker ist als ein pushdown Automat, aber weniger als eine Maschine von Turing.

Automaten von Pushdown sind zu Grammatiken ohne Zusammenhänge gleichwertig: Für jede Grammatik ohne Zusammenhänge, dort besteht ein pushdown solcher Automat, dass die durch die Grammatik erzeugte Sprache mit der Sprache identisch ist, die durch den Automaten erzeugt ist, der leicht ist sich zu erweisen. Die Rückseite, ist obwohl härter, wahr, um sich zu erweisen: Für jeden pushdown Automaten dort besteht eine solche Grammatik ohne Zusammenhänge, dass die durch den Automaten erzeugte Sprache mit der durch die Grammatik erzeugten Sprache identisch ist.

Formelle Definition

Ein PDA wird als ein 7-Tupel-formell definiert:

wo

• ist ein begrenzter Satz von
• ist ein begrenzter Satz, der den genannt wird

ist ein begrenzter Satz, der den genannt wird

• ist eine begrenzte Teilmenge, wo den Satz von Schnuren anzeigen und die leere Schnur anzeigt.
• ist der

ist der

• ist der Satz von

Ein Element ist ein Übergang dessen. Es hat das beabsichtigte Meinen, das, im Staat, mit auf dem Eingang und mit als höchstes Stapel-Symbol, lesen, den Staat zu, Knall ändern kann, es durch das Stoßen ersetzend. Der Brief (Epsilon) zeigt die leere Schnur an, und der Bestandteil der Übergang-Beziehung wird verwendet, um das zu formalisieren, der PDA kann entweder einen Brief vom Eingang lesen oder weitergehen, den Eingang unberührt verlassend.

In vielen Texten wird die Übergang-Beziehung durch eine (gleichwertige) Formalisierung, wo ersetzt

• ist, in begrenzte Teilmengen dessen kartografisch darstellend.

Hier enthält alle möglichen Handlungen im Staat mit auf dem Stapel, während man auf dem Eingang liest. Man schreibt für die Funktion genau wenn für die Beziehung. Bemerken Sie, dass in dieser Definition notwendig ist.

Berechnung

Um die Semantik des pushdown Automaten zu formalisieren, wird eine Beschreibung der aktuellen Situation eingeführt. Irgendwelcher 3-Tupel-wird eine sofortige Beschreibung (ID) dessen genannt, der den aktuellen Staat, den Teil des Eingangsbandes einschließt, das, und der Inhalt des Stapels (höchstes Symbol schriftlich erst) nicht gelesen worden ist. Die Übergang-Beziehung definiert die Stiefbeziehung auf sofortigen Beschreibungen. Für die Instruktion dort besteht ein Schritt, für jeder und jeder.

In allgemeinen pushdown Automaten sind das nichtdeterministische Meinen dass in einer gegebenen sofortigen Beschreibung es kann mehrere mögliche Schritte geben. Einige dieser Schritte kann in einer Berechnung gewählt werden.

Mit der obengenannten Definition in jedem Schritt immer wird ein einzelnes Symbol (Spitze des Stapels) knallen gelassen, es mit so vielen Symbolen ersetzend, wie notwendig. Demzufolge wird kein Schritt definiert, wenn der Stapel leer ist.

Die Berechnung des pushdown Automaten ist Folgen von Schritten. Die Berechnung fängt im anfänglichen Staat mit dem anfänglichen Stapel-Symbol auf dem Stapel und einer Schnur auf dem Eingangsband so mit der anfänglichen Beschreibung an.

Es gibt zwei Weisen des Annehmens. Der pushdown Automat entweder akzeptiert durch den Endstaat, was nach dem Lesen seines Eingangs bedeutet, in dem der Automat einen akzeptierenden Staat erreicht, oder es durch den leeren Stapel akzeptiert , was nach dem Lesen seines Eingangs bedeutet, entleert der Automat seinen Stapel. Die erste Annahmeweise verwendet das innere Gedächtnis (Staat), das zweite das Außengedächtnis (Stapel).

Formell definiert man

1. mit und (Endstaat)

1. mit (leerer Stapel)

Hier vertritt den reflexiven und transitiven Verschluss der Schritt-Beziehung, die jede Zahl von Konsekutivschritten (Null, ein oder mehr) bedeutet.

Für jeden einzelnen pushdown Automaten müssen diese zwei Sprachen keine Beziehung haben: Sie können gleich sein, aber gewöhnlich ist das nicht der Fall. Eine Spezifizierung des Automaten sollte auch die beabsichtigte Weise der Annahme einschließen. Übernommen alle pushdown Automaten definieren beide Annahmebedingungen dieselbe Sprachfamilie.

Lehrsatz. Für jeden pushdown Automaten kann man einen pushdown solchen Automaten bauen, dass, und umgekehrt für jeden pushdown Automaten man einen pushdown solchen Automaten dass bauen kann

Beispiel

Der folgende ist die formelle Beschreibung des PDA, der die Sprache durch den Endstaat anerkennt:

, wo

besteht aus den folgenden sechs Instruktionen:

, und

.

In Wörtern, im Staat für jedes gelesene Symbol, wird eines auf den Stapel gestoßen. Das Stoßen des Symbols oben auf einem anderen wird als das Ersetzen der Spitze dadurch formalisiert. Im Staat für jedes gelesene Symbol wird eines knallen gelassen. Jederzeit kann sich der Automat vom Staat bis Staat bewegen, während es sich vom Staat bis akzeptierenden Staat nur bewegen kann, wenn der Stapel aus einer Single besteht.

Es scheint, keine allgemein verwendete Darstellung für PDA zu geben. Hier haben wir die Instruktion durch einen Rand vom Staat bis Staat gezeichnet, der dadurch etikettiert ist (gelesen; ersetzen Sie durch).

Das Verstehen des Berechnungsprozesses

Der folgende illustriert, wie der obengenannte PDA auf verschiedenen Eingangsschnuren rechnet. Die Subschrift vom Schritt-Symbol wird hier weggelassen.

(a) Eingangsschnur = 0011. Es gibt verschiedene Berechnung abhängig vom Moment, der die Bewegung vom Staat bis Staat gemacht wird. Nur ein von diesen akzeptieren.

: (i). Der Endstaat akzeptiert, aber der Eingang wird dieser Weg nicht akzeptiert, weil es nicht gelesen worden ist.

: (ii). Keine weiteren möglichen Schritte.

: (iii). Das Annehmen der Berechnung: Enden im akzeptierenden Staat, während ganzer Eingang gelesen worden ist.

(b) Eingangsschnur = 00111. Wieder gibt es verschiedene Berechnung. Keiner von diesen akzeptiert.

: (i). Der Endstaat akzeptiert, aber der Eingang wird dieser Weg nicht akzeptiert, weil es nicht gelesen worden ist.: (ii). Keine weiteren möglichen Schritte.

: (iii). Der Endstaat akzeptiert, aber der Eingang wird dieser Weg nicht akzeptiert, weil es nicht (völlig) gelesen worden ist.

PDA und Sprachen ohne Zusammenhänge

Jede Grammatik ohne Zusammenhänge kann in einen gleichwertigen pushdown Automaten umgestaltet werden. Der Abstammungsprozess der Grammatik wird auf eine leftmost Weise vorgetäuscht. Wo die Grammatik ein Nichtterminal umschreibt, nimmt der PDA das höchste Nichtterminal von seinem Stapel und ersetzt es durch den rechten Teil einer grammatischen Regel (breitet sich aus). Wo die Grammatik ein Endsymbol erzeugt, liest der PDA ein Symbol vom Eingang, wenn es das höchste Symbol auf dem Stapel (Match) ist. Gewissermaßen enthält der Stapel des PDA die unverarbeiteten Daten der Grammatik entsprechend einem Vorordnungstraversal eines Abstammungsbaums.

Technisch, in Anbetracht einer Grammatik ohne Zusammenhänge, wird der PDA wie folgt gebaut.

1. für jede Regel

1. für jedes Endsymbol

Infolgedessen erhalten wir einen einzelnen Staat pushdown Automat, der Staat hier ist, die Sprache ohne Zusammenhänge durch den leeren Stapel akzeptierend. Sein anfängliches Stapel-Symbol kommt dem Axiom der Grammatik ohne Zusammenhänge gleich.

Das gegenteilige, eine Grammatik für einen gegebenen PDA findend, ist so nicht leicht. Der Trick soll zwei Staaten des PDA in die Nichtterminals der Grammatik codieren.

Lehrsatz. Für jeden pushdown Automaten kann man eine solche Grammatik ohne Zusammenhänge dass bauen.

Verallgemeinerter Pushdown Automat (GPDA)

Ein GPDA ist ein PDA, der eine komplette Schnur von etwas bekannter Länge zum Stapel schreibt oder eine komplette Schnur vom Stapel in einem Schritt entfernt.

Ein GPDA wird als ein 6-Tupel-formell definiert:

:

wo Q, q und F derselbe Weg als ein PDA definiert werden.

::

ist die Übergang-Funktion.

Berechnungsregeln für einen GPDA sind dasselbe als ein PDA, außer dass der a's und b's jetzt Schnuren statt Symbole sind.

GPDA'S und PDA'S sind darin gleichwertig, wenn eine Sprache durch einen PDA anerkannt wird, wird es auch durch einen GPDA und umgekehrt anerkannt.

Man kann einen analytischen Beweis für die Gleichwertigkeit des Verwendens von GPDA und PDA der folgenden Simulation formulieren:

Lassen Sie (q, w, xx... x) (q, yy... y), ein Übergang des GPDA sein

wo.

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

:: (q, w, x) (p,)

:: (p, x) (p,)

::::

:: (p, x) (p,)

:: (p,) (p, y)

:: (p,) (p, y)::::

:: (p,) (q, y)

Siehe auch

• Stapel-Maschine
• Grammatik ohne Zusammenhänge
• Begrenzter Automat

• Abschnitt 2.2: Pushdown Automaten, pp.101-114.
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Sprachen ohne Zusammenhänge und Automaten des Stoßes unten, in:G. Rozenberg, A. Salomaa (Hrsg.). Handbuch von Formellen Sprachen, Vol. 1, Springer-Verlag, 1997, 111-174.

Links

• nichtdeterministischer pushdown Automat, auf der Planet-Mathematik.
• JFLAP, Simulator für mehrere Typen von Automaten einschließlich nichtdeterministischer pushdown Automaten