Wikipedia · einfach zusammengefasst · Stand
Kellerautomat
Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, …
Inhalt6 Abschnitte
Grundidee und Bedeutung
Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton oder Stackmaschine) ist ein Automat der theoretischen Informatik. Er dient dazu, Eigenschaften von Problemen, Algorithmen und formalen Sprachen zu untersuchen und zu beweisen. Im Kern ist er ein endlicher Automat, der zusätzlich einen Kellerspeicher besitzt. Dieser Speicher funktioniert wie ein Stack: Man kann vor allem auf das oberste Element zugreifen, es entfernen und neue Zeichen oben ablegen.
Ein Kellerautomat prüft, ob ein Eingabewort zu einer bestimmten formalen Sprache gehört. Ein Eingabewort besteht aus null, einem oder mehreren Zeichen; eine formale Sprache ist eine Menge solcher Wörter. Der Automat liest die Eingabe normalerweise von links nach rechts, befindet sich dabei immer in einem Zustand und verändert abhängig von Eingabe, Zustand und Kellerinhalt seinen weiteren Ablauf.
Kellerautomaten sind wichtig, weil sie genau die Sprachklasse beschreiben, die zwischen regulären Sprachen und den allgemeineren von Turingmaschinen erkennbaren Sprachen liegt. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.
Arbeitsweise
Zu Beginn befindet sich der Kellerautomat im Startzustand. In einem typischen Verarbeitungsschritt liest er ein Eingabezeichen und entfernt zugleich das oberste Zeichen aus dem Keller. Danach entscheidet er anhand von drei Informationen, wie es weitergeht: aktueller Zustand, gelesenes Eingabezeichen und gelesenes Kellerzeichen. Er wechselt in einen neuen Zustand und legt anstelle des entfernten Kellerzeichens ein neues Wort auf den Keller.
Eine Eingabe kann auf verschiedene Weise als akzeptiert gelten. Häufig gilt: Wenn die gesamte Eingabe gelesen wurde und der Keller leer ist, gehört die Eingabe zur erkannten Sprache. Es gibt aber auch die Variante, dass eine Eingabe akzeptiert wird, sobald nach ihrer Abarbeitung ein Endzustand erreicht ist, unabhängig davon, ob der Keller leer ist.
Nicht jeder Schritt muss ein Eingabezeichen lesen. Wenn kein Zeichen gelesen wird, spricht man vom leeren Wort ε. Außerdem kann ein Kellerautomat nichtdeterministisch sein: Für dieselbe Kombination aus Zustand, Eingabezeichen oder ε und Kellerzeichen kann es mehrere mögliche Übergänge geben. Dann reicht es, wenn es mindestens einen Berechnungspfad gibt, der zur Akzeptanz führt.
Formale Beschreibung
Ein nichtdeterministischer Kellerautomat (NKA) wird als 7-Tupel M=(Z,Σ,Γ,δ,z₀,#,F) definiert. Dabei ist Z eine endliche Menge von Zuständen, Σ das Eingabealphabet, Γ das Kelleralphabet, δ die Zustandsübergangsfunktion, z₀∈Z der Startzustand, #∈Γ das Anfangssymbol im Keller und F⊆Z die Menge der Endzustände.
Die Übergangsfunktion hat die Form δ: Z×(Σ∪{ε})×Γ → P(Z×Γ*) und bildet nur auf endliche Teilmengen von Z×Γ* ab. Dabei bezeichnet ε das leere Wort und Γ* die Menge aller Wörter über dem Kelleralphabet Γ. Die Funktion beschreibt also, welcher Folgezustand möglich ist und welches Wort auf den Keller geschrieben wird.
Manchmal wird ein Kellerautomat auch als 6-Tupel M=(Z,Σ,Γ,δ,z₀,#) angegeben. Dann gibt es keine Endzustände; ein Wort wird akzeptiert, wenn nach der Abarbeitung der Keller leer ist.
Ein Kellerautomat heißt deterministisch, wenn für jede Kombination aus Zustand z∈Z, Eingabezeichen a∈Σ und Kellerzeichen g∈Γ gilt: |δ(z,a,g)| + |δ(z,ε,g)| ≤ 1. Dann gibt es zu einer festen Eingabe höchstens eine mögliche Folge von Zustandsübergängen, also keine Mehrdeutigkeit.
Akzeptanz von Wörtern
Die Konfigurationen eines Kellerautomaten werden als K=Z×Σ*×Γ* beschrieben. Eine Konfiguration (z,α,γ) besteht aus dem aktuellen Zustand z, dem noch zu lesenden Wort α und dem Kellerinhalt γ. Über eine Relation ⇝ wird festgelegt, wie der Automat von einer Konfiguration in die nächste übergeht.
Wenn ein Eingabezeichen a gelesen wird, kann ein Übergang von (z,aα,gγ) nach (z',α,γ'γ) stattfinden, falls (z',γ')∈δ(z,a,g) gilt. Das bedeutet: a wird verbraucht, g wird vom Keller entfernt, und γ' wird auf den Keller gelegt. Bei einem ε-Übergang wird kein Eingabezeichen verbraucht; entsprechend kann (z,α,gγ) nach (z',α,γ'γ) übergehen, falls (z',γ')∈δ(z,ε,g) gilt.
Bei Akzeptanz durch Endzustände wird ein Wort α∈Σ* genau dann akzeptiert, wenn es ein f∈F und ein γ∈Γ* gibt, sodass (z₀,α,#)⇝(f,ε,γ). Das Wort ist also vollständig gelesen, und der Automat befindet sich in einem Endzustand. Bei Akzeptanz durch leeren Keller wird α genau dann akzeptiert, wenn es ein z∈Z gibt, sodass (z₀,α,#)⇝(z,ε,ε) oder (z₀,α,#)⇝(z,ε,#). Dabei ist ⇝ die reflexive und transitive Hülle von ⇝, also die Folge von beliebig vielen Übergangsschritten einschließlich null Schritten.
Beispiele
Ein typisches Beispiel ist die Prüfung korrekt geklammerter Ausdrücke. Bei einer öffnenden Klammer wird ein Zeichen auf den Keller gelegt. Bei einer schließenden Klammer wird ein entsprechendes oberes Kellerzeichen gelöscht. Am Ende ist der Ausdruck korrekt, wenn die Eingabe vollständig gelesen wurde und im Keller nur noch das Anfangszeichen # liegt. Bleibt eine öffnende Klammer im Keller, fehlt eine schließende Klammer. Wird der Keller zu früh erreicht, gibt es zu viele schließende Klammern.
Ein formales Beispiel ist ein deterministischer Kellerautomat M, der die kontextfreie Sprache L={aⁿbⁿ | n>0} erkennt. Er speichert zunächst im Zustand z₀ für jedes gelesene a ein a im Keller. Beim ersten b und einem a oben im Keller wechselt er in den Zustand z₁ und löscht ein a. Weitere b-Zeichen werden nur gelesen, solange passende a-Zeichen im Keller vorhanden sind. Wenn nur noch das Anfangssymbol # im Keller liegt und keine Eingabe erfolgt, wechselt der Automat in den Endzustand z₂ und akzeptiert.
Für die Eingabe aabb verläuft die Berechnung so: (z₀,aabb,#) ⇝ (z₀,abb,a#) ⇝ (z₀,bb,aa#) ⇝ (z₁,b,a#) ⇝ (z₁,ε,#) ⇝ (z₂,ε,ε). Der Automat erkennt also, dass die Zahl der a-Zeichen und b-Zeichen gleich ist und alle a vor den b stehen.
Ein weiteres Beispiel beschreibt eine Sprache über linken und rechten eckigen Klammern. Sie wird durch die Grammatik G=(V,T,P,S) mit T={[,]}, N={S} und den Regeln S→[S], S→SS und S→ε angegeben. Diese Sprache enthält genau die Zeichenketten, die gleich viele linke und rechte Klammern besitzen und kein Präfix haben, in dem mehr rechte als linke Klammern vorkommen.
Sprachen und Anwendungen
Die Menge der Eingaben, die ein Automat akzeptiert, bildet die durch ihn definierte Sprache. Nichtdeterministische Kellerautomaten erkennen genau die kontextfreien Sprachen, also Typ 2 der Chomsky-Hierarchie. Damit sind sie mächtiger als endliche Automaten, die genau die regulären Sprachen vom Typ 3 erkennen, aber weniger mächtig als Turingmaschinen, die genau die rekursiv aufzählbaren Sprachen vom Typ 0 erkennen.
Deterministische Kellerautomaten (DPDA) erkennen die deterministisch-kontextfreien Sprachen. Diese bilden nur eine echte Teilmenge der kontextfreien Sprachen. Darum ist der Unterschied zwischen deterministischen und nichtdeterministischen Kellerautomaten für die Theorie wichtig.
Für nichtdeterministische Kellerautomaten sind Akzeptanz durch Endzustände und Akzeptanz durch leeren Keller hinsichtlich der akzeptierten Sprachen äquivalent. Für deterministische Kellerautomaten gilt das im Allgemeinen nicht; ein deterministischer Kellerautomat, der über Endzustände akzeptiert, ist mächtiger. Außerdem kann man für nichtdeterministische Kellerautomaten unter bestimmten Bedingungen auf Endzustände, Startzustand und Zustandsmenge verzichten oder ε-Übergänge durch äquivalente Automaten ohne solche Übergänge ersetzen.
Praktisch werden Kellerautomaten vor allem bei der Syntaxanalyse verwendet. Compiler oder Interpreter können mit ihrer Hilfe prüfen, ob eine Tokenfolge syntaktisch korrekt ist. Im Artikel wird dazu ein C-Parser für Klammerpaare gezeigt: Der Ausdruck ()((()())) wird akzeptiert, (()())) hingegen nicht, weil eine schließende Klammer zu viel vorhanden ist.
Auch in der Technik gibt es Kellerprinzipien. Die Gleitkommaeinheit (Floating Point Unit, FPU) der Intel-32-Bit-x86-Architektur war ursprünglich als Stack Machine realisiert. Ihr Kellerspeicher hat eine Tiefe von 8 Speicherplätzen, jeweils für einen 80-Bit-Gleitkommawert. Wegen der Einschränkungen des Kellermodells werden jedoch tendenziell Verarbeitungseinheiten mit direkt adressierbaren Registern verwendet, etwa im Zusammenhang mit SIMD-Erweiterungen.
