Pushdown-Automaten Einführung
Grundstruktur des PDA
Ein Pushdown-Automat ist eine Möglichkeit, eine kontextfreie Grammatik auf ähnliche Weise zu implementieren, wie wir DFA für eine reguläre Grammatik entwerfen. Ein DFA kann sich an eine endliche Menge an Informationen erinnern, ein PDA kann sich jedoch an eine unendliche Menge an Informationen erinnern.
Grundsätzlich ist ein Pushdown-Automat -
"Finite state machine" + "a stack"
Ein Pushdown-Automat besteht aus drei Komponenten:
- ein Eingabeband,
- eine Steuereinheit und
- ein Stapel mit unendlicher Größe.
Der Stapelkopf scannt das obere Symbol des Stapels.
Ein Stapel führt zwei Operationen aus -
Push - Oben wird ein neues Symbol hinzugefügt.
Pop - Das obere Symbol wird gelesen und entfernt.
Ein PDA kann ein Eingabesymbol lesen oder nicht, muss jedoch bei jedem Übergang die Oberseite des Stapels lesen.
Ein PDA kann formal als 7-Tupel beschrieben werden (Q, ∑, S, δ, q 0 , I, F) -
Q ist die endliche Anzahl von Zuständen
∑ ist das eingegebene Alphabet
S ist Stapelsymbole
δ ist die Übergangsfunktion: Q × (∑ ∑ {ε}) × S × Q × S *
q0ist der Ausgangszustand (q 0 ∈ Q)
I ist das anfängliche Stapelsymbol (I ∈ S)
F ist eine Menge von Akzeptanzzuständen (F ∈ Q)
Das folgende Diagramm zeigt einen Übergang in einem PDA von einem Zustand q 1 zu einem Zustand q 2 , bezeichnet als a, b → c -
Dies bedeutet bei Zustand q1, wenn wir auf eine Eingabezeichenfolge stoßen ‘a’ und oberes Symbol des Stapels ist ‘b’, dann knallen wir ‘b’, drücken ‘c’ auf den Stapel legen und in den Status wechseln q2.
Terminologien im Zusammenhang mit PDA
Sofortige Beschreibung
Die momentane Beschreibung (ID) eines PDA wird durch ein Triplett (q, w, s) dargestellt, wobei
q ist der Staat
w ist nicht verbrauchte Eingabe
s ist der Stapelinhalt
Drehkreuznotation
Die "Drehkreuz" -Notation wird zum Verbinden von ID-Paaren verwendet, die eine oder mehrere Bewegungen eines PDA darstellen. Der Übergangsprozess ist mit dem Drehkreuzsymbol "⊢" gekennzeichnet.
Betrachten Sie einen PDA (Q, ∑, S, δ, q 0 , I, F). Ein Übergang kann mathematisch durch die folgende Drehkreuznotation dargestellt werden:
(p, aw, Tβ) ⊢ (q, w, αb)Dies impliziert, dass beim Übergang vom Staat p zu erklären q, das Eingabesymbol ‘a’ verbraucht wird, und die Oberseite des Stapels ‘T’ wird durch eine neue Zeichenfolge ersetzt ‘α’.
Note - Wenn wir null oder mehr Bewegungen eines PDAs wollen, müssen wir das Symbol (⊢ *) dafür verwenden.