Kellerautomat
Einführung
Er gehört zur Familie der endlichen Automaten und ist erweitert um eine Datenstruktur, den sogenannten "Keller" (englisch "stack"). Ein Kellerautomat ist ein Automat, der neben seinen Zuständen und Übergängen auch einen Kellerspeicher, also einen LIFO-(last in, first out) Speicher besitzt. Der Kellerautomat kann
jede Transition zusätzlich vom obersten Element des Stack abhängig machen und
bei jeder Transition auch den Stack manipulieren, also einen zusätzlichen Wert darauflegen (PUSH17 ), den obersten Wert entnehmen (POP) oder den Stack unverändert lassen (NOP).
Der entscheidende Unterschied zum DEA ist hier der unbegrenzte Speicherplatz auf dem Stack.
Ein Kellerautomat arbeitet nach bestimmten Regeln, um Zeichen von einer Eingabe zu lesen und diese in den Keller zu legen oder aus dem Keller zu entfernen. Die Zustandsübergänge des Automaten hängen nicht nur von dem gelesenen Zeichen, sondern auch von dem Zeichen auf der Spitze des Kellers ab. Dies macht Kellerautomaten besonders nützlich zur Erkennung kontextfreier Sprachen.
Kellerautomaten werden in der theoretischen Informatik und in der Compilerkonstruktion oft verwendet, um die Syntax von Programmiersprachen zu analysieren und um sicherzustellen, dass sie korrekt verschachtelte Konstrukte haben. Ein Beispiel für einen Kellerautomaten ist der LR(1)-Parser, der in der Syntaxanalyse von Programmiersprachen eingesetzt wird.
Insgesamt sind Kellerautomaten ein wichtiges Konzept in der theoretischen Informatik, um formale Sprachen und Grammatiken zu beschreiben und zu analysieren.
Definition als 6-Tupel
Einen Kellerautomaten kann man in der Regel als 6-Tupel beschreiben, ähnlich wie viele andere Automaten in der theoretischen Informatik. Die sechs Elemente des Tupels definieren die wesentlichen Komponenten eines Kellerautomaten und seine Funktionsweise. Die sechs Elemente sind in der Regel wie folgt definiert:
Q: Die Menge der Zustände des Automaten.
Σ: Das Eingabealphabet, d.h., die Menge der Zeichen, die der Automat von der Eingabe lesen kann.
Γ: Das Kelleralphabet, d.h., die Menge der Zeichen, die auf den Keller gelegt werden können.
δ: Die Übergangsfunktion, die die Zustandsübergänge des Automaten beschreibt. Sie nimmt ein aktuelles Zustand, ein gelesenes Zeichen von der Eingabe und das aktuelle Kellersymbol und gibt den neuen Zustand, das Zeichen, das auf den Keller gelegt wird und die Richtung (oben oder unten) an, in die das Kellersymbol gelegt wird.
q0: Der Startzustand, von dem aus die Berechnung beginnt.
F: Die Menge der akzeptierenden oder Endzustände, die angeben, wann der Automat eine Eingabe akzeptiert.
Abgrenzung zum DEA
Deterministische endliche Automaten (DEAs) sind aufgrund ihrer begrenzten Fähigkeiten nicht in der Lage, Klammersprachen effizient zu erkennen. Dies liegt daran, dass Klammersprachen in der Regel eine geschachtelte Struktur aufweisen, bei der öffnende und schließende Klammern in einer korrekten Weise auftreten müssen. Ein DEA kann jedoch keine derartige geschachtelte Struktur verarbeiten, da er keinen Mechanismus zum Speichern und Wiederabrufen von Informationen über bereits gelesene Klammern besitzt.
Die Sprache soll L = {ab, aabb, aaabbb, ... } = {anbn | n > 0} sein. a entspricht einer sich öffenden Klammer; b ist eine schließende.
Ob steht ein DEA fü n=3. Für jedes weitere n müsste er entsprechend erweitert werden.
DEAs sind für die Verarbeitung von regulären Sprachen geeignet, die eine lineare Struktur haben, bei der die Reihenfolge der Symbole wichtig ist, aber keine Verschachtelung erfordert wird. Klammersprachen hingegen erfordern eine Art von Zählermechanismus, um sicherzustellen, dass jede öffnende Klammer eine zugehörige schließende Klammer hat. Ein DEA hat keinen internen Speicher, um diese Zählung durchzuführen, und kann daher Klammersprachen nicht angemessen behandeln.
Im Gegensatz dazu sind Kellerautomaten (insbesondere nichtdeterministische Kellerautomaten) in der Lage, Klammersprachen zu verarbeiten. Sie verwenden einen Keller, um Informationen über die gelesenen Klammern zu speichern und die zugehörigen schließenden Klammern zu überprüfen. Diese zusätzliche Fähigkeit, Informationen zu speichern und wiederzuerlangen, ermöglicht es Kellerautomaten, kontextfreie Sprachen zu akzeptieren, zu denen Klammersprachen gehören.
Zusammenfassend können DEAs Klammersprachen nicht effizient lösen, weil sie nicht über die erforderlichen Mechanismen zur Verarbeitung der geschachtelten Struktur verfügen, die in Klammersprachen vorkommt. Kellerautomaten, die über einen Speichermechanismus (den Keller) verfügen, sind besser geeignet, um Klammersprachen und andere kontextfreie Sprachen zu verarbeiten.
Beispiel
Der Folgende Klammerautomat erkennt Klammerpaare. Zu jeder öffnenden Klammer wird eine sich schließende Klammer benötigt. a steht für "Klammer auf". z steht für "Klammer zu". # bedeutet, dass der Stack leer ist.
Quelle: https://lehrerfortbildung-bw.de/
Der Automat beginnt mit leerem Stack und legt bei jeder öffnenden Klammer ein Symbol (z.B. „k“ für Klammer) darauf ab. Bei jeder schließenden Klammer entfernt er eines; die Anzahl der „k“ auf dem Stack zählt also die momentane Klammerungstiefe; das Entfernen vom leeren Stack führt zu einem Fehler. Der Automat für diese Aufgabe muss in einem Endzustand stehen (und das Wort damit akzeptieren), falls am Ende der Eingabe auch der Stack leer ist.
Das Schaubild zeigt einen einfachen Kellerautomaten, der Klammerausdrücke erkennt. Vom Input werden hier nur die Klammern selbst betrachtet und ihr „Inhalt“ ignoriert; zugunsten der Lesbarkeit verwenden wir außerdem a und z statt „Klammer-auf“ und „-zu“. Korrekt geklammerte Ausdrücke sind also etwa az, aaazzz, azaz oder aazazz. Wie schon angesprochen gilt auch das leere Wort als korrekt geklammert.
Ablaufprotokoll eines Kellerautomaten
Im Übergangsgraphen bedeutet die Transition (a, k; push k) Folgendes: „FALLS im Zustand q1 das Eingabezeichen a anliegt UND auf dem Stack ein k liegt, DANN wechsle in Zustand q1 und push ein weiteres k“. Die Transaktion (z,k; pop) bedeitet Falls im Zustand q1 z anliegt UND auf dem Steck k iegt, DANN entfern (pop) k nach dem LIFO-Prinzip. Das Zeichen # steht für einen leeren Stack, das λ für „kein Eingabezeichen“ (Merkhilfe: lambda für „leer“, oft auch epsilon für „empty“). Diese Transition verbraucht also keine Eingabe. (λ, #; nop) Falls es keine weitere Eingabe gibt (also das leere Wort anliegt) UND auf dem Stapel # obenaufliegt, dann Wechsel in q0.
6-Tupel
Q: {q0, q1}
q0: Der Startzustand.
Σ: {a, z}
Die Symbole, die der Automat von der Eingabe liest: "a" für öffnende Klammern und "z" für schließende Klammern.
Γ: {a, z, #}
Das Kelleralphabet, das die Symbole enthält, die auf den Keller gelegt werden können: "a" für öffnende Klammern, "z" für schließende Klammern und "#" für einen leeren Keller.
δ: Die Übergangsfunktion, die die Zustandsübergänge und Kelleroperationen beschreibt.
q0: Endzustand
Implementierung
Eine Implementierung des Beispiels als Kellerautomaten könnte wie folgt aussehen:
import java.util.Stack;
public class BracketAutomaton {
public static boolean checkBrackets(String input) {
Stack<Character> stack = new Stack<>();
for (char c : input.toCharArray()) {
if (c == 'a') {
stack.push(c);
} else if (c == 'z') {
if (stack.isEmpty() || stack.pop() != 'a') {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
String input = "aazzaa";
boolean result = checkBrackets(input);
if (result) {
System.out.println("Klammerpaare sind korrekt verschachtelt.");
} else {
System.out.println("Klammerpaare sind nicht korrekt verschachtelt.");
}
}
}