Kellerautomat
Du möchtest das Thema „Kellerautomat“ endlich verstehen? Hier in unserem Beitrag und im dazugehörigem Video findest du die wichtigsten Eigenschaften von einem Kellerautomat einfach erklärt. Zusätzlich zeigen wir dir, was Kellerautomaten mit formalen Sprachen zu tun haben. Zum Schluss findest du ein ausführliches Kellerautomat Beispiel.
Inhaltsübersicht
Kellerautomaten
Ein Kellerautomat, kurz KA, auch bekannt als pushdown automata – kurz PDA, ist ein endlicher Automat , der zusätzlich zu den Grundkomponenten eines Automaten einen Kellerspeicher benutzt. Der Kellerspeicher ist hierbei ein „Last In First Out“ – Speicher. Es werden also die Elemente, die zuletzt abgelegt wurden, als erstes wieder entfernt. Diese Datenstruktur wird auch Stapel oder englisch: Stack genannt. Allgemein erkennen Kellerautomaten, ob eine Eingabe zu einer formalen Sprache gehört, oder nicht.
Formale Definition
Ein nichtdeterministischer Kellerautomat wird als 7-Tupel definiert – entsprechend benötigen wir die folgenden 7 Elemente:
- Die Menge der Zustände Z
- Zstart als Startzustand
- Zend als Endzustand
- das Eingabealphabet E stellt die Zeichen dar, die das Eingabewort enthalten darf
- das Kelleralphabet Γ die Zeichen, die in den Keller geschrieben werden dürfen
- die Zustandsübergangsfunktion δ
- als neues Element kommt noch das Anfangssymbol hinzu, das vor Eingabe des Wortes im Keller steht. Dieses wird mit einem Rautezeichen (#) dargestellt
Kellerautomat – einfach erklärt
Du möchtest den Kellerautomat einfach erklärt bekommen? Kein Problem! Der Automat schreibt zu Beginn das Anfangssymbol in den Speicher, dieses wird später noch wichtig. Jetzt wird ein Wort, Zeichen für Zeichen, eingelesen. Endlich kann eine Operation mit dem Kellerspeicher ausgeführt werden, wie zum Beispiel das eben eingelesene Zeichen auf dem Speicher abzulegen oder mit dem aktuellen Zeichen an oberster Stelle des Kellers verwerten. Für diese Verwertung gibt es klare Regeln, die, je nachdem, welches Zeichen das oberste im Keller ist, anders aussehen.
Stelle dir einen Automaten vor, der erkennt, ob ein Eingabewort mit n-mal „0“ beginnt und auf n-mal „1“ endet, zum Beispiel so: „000111“. Liest der Automat eine 0 ein, und das erste Zeichen im Keller ist ebenfalls eine 0, so wird das erste Zeichen im Keller verdoppelt, also zu „00“. Hierbei stellst du dir den Keller einfach wie eine Zeichenfolge vor:
Das erste Zeichen im Keller ist jetzt trotzdem nur eine „0“ und nicht „00“, da nur das erste Zeichen der Zeichenfolge betrachtet wird. Wird hingegen eine 1 eingelesen, während das erste Zeichen im Keller eine 0 ist, wird die 0 aus dem Keller gelöscht, also durch ein leeres Wort ersetzt. Alle darauffolgenden Zeichen rücken jetzt nach, also haben wir ein neues erstes Zeichen im Keller. So können wir nach und nach die Anzahl der Nullen mit der Anzahl der Einsen abgleichen.
Verarbeitungsregeln
Die Regeln für die Verarbeitung werden hierbei von der Überführungsfunktion beschrieben. Die Funktion hat als Eingabewert hierbei Tripel, also Tupel mit drei Elementen. Diese bestehen aus dem aktuellen Zustand, dem eingelesenen sowie dem obersten Zeichen des Kellers. Jedes dieser Tripel hat als Funktionswert ein Tupel aus zwei Elementen. Diese enthalten zum einen den Folgezustand und zum anderen das neue oberste Zeichen im Keller. Gibt es von jedem Zustand immer höchstens einen Übergang bei gleicher Eingabe und gleichem obersten Kellerzeichen, dann ist es ein deterministischer Kellerautomat, sonst natürlich nichtdeterministisch.
Zudem kann der Automat selbstverständlich verschiedene Zustände einnehmen. Ist nach der kompletten Verarbeitung eines Wortes nur noch das Anfangszeichen im Keller, dann wechselt der Automat in den Endzustand und akzeptiert die Eingabe. Es gibt auch Automaten, die ein Wort dann akzeptieren, wenn sich der Automat, nach Abarbeiten eines Wortes in einem Endzustand befindet ohne, dass der Keller leer ist.
Kellerautomaten und formale Sprachen
Nichtdeterministische Kellerautomaten können hierbei genau die kontextfreien Sprachen, Typ 2 der Chomsky-Hierarchie , erkennen, während deterministische Kellerautomaten nur genau die deterministisch-kontextfreie Sprachen, also einen Teil der kontextfreien Sprachen erkennen können. Es gibt also kontextfreie Sprachen, die deterministische Kellerautomaten nicht lesen können. Du weißt nicht, was die Chomsky-Hierarchie oder kontextfreie Sprachen sind? Dann schau dir am besten unser Video dazu an!
Alles klar! Nun verstehst du, wie du Kellerautomaten konstruieren und nachvollziehen kannst. Außerdem weißt du jetzt auch, wie du Kellerautomaten nutzen kannst. Aber wie sich das Ganze theoretisch umsetzen lässt, sehen wir uns nun an dem folgenden Kellerautomat Beispiel an.
Kellerautomat Beispiel
Ein deterministischer Kellerautomat hat für jede Konfiguration höchsten eine Folgekonfiguration und hat dabei wie endliche Automaten eine lineare Spracherkennung. Dabei ist wichtig zu wissen, dass ein deterministischer Kellerautomat nicht jede kontextfreie Sprache erkennt.
Versuchen wir unser neues Wissen an einem Beispiel anzuwenden. Die Aufgabe ist es, den vorher bereits angesprochenen Automaten zu erstellen. Kurze Erinnerung: der Automat soll Wörter erkennen, die mit n-mal „0“ beginnen und mit n-mal „1“ enden, also zum Beispiel diese Wörter:
„01“, „0011“, „0000000011111111“
Kellerautomat konstruieren
Um unseren Kellerautomat konstruieren zu können, benötigt man drei Zustände:
- einen Startzustand z0 für das Einlesen und für das Schreiben der Nullen in den Keller,
- einen Zustand z1 für das Löschen der Nullen im Keller beim Einlesen einer „1“ und
- einen Endzustand z2, der das Wort akzeptiert.
Nun können wir beginnen unsere Übergangsfunktion zu konstruieren. Hierfür benutzen wir unsere vorher genannten Tupel aus unserer Kellerautomat Aufgabe:
Welche Zustandsübergänge brauchen wir jetzt? Zu Beginn befinden wir uns im Startzustand z0 und im Keller steht nur das Anfangssymbol, hierfür nehmen wir jetzt das „Z“. Wird nun eine „0“ eingelesen, ist der Folgezustand ebenfalls z0, und das oberste Kellerzeichen wird von „Z“ zu „0Z“ – das am weitesten linksstehende Zeichen ist hierbei immer das oberste. Diesen Übergang tragen wir in unsere Tabelle ein. Werden jetzt weitere Nullen eingelesen, bleiben wir ebenfalls im Zustand z0, das oberste Zeichen im Keller wird lediglich von „0“ zu „00“ geändert.
Stellen wir uns jetzt vor im Eingabewort folgt eine „1“. Was muss jetzt passieren? Da wir gleich viele Einsen wie Nullen benötigen, kann für jede Eins eine Null aus dem Keller gestrichen werden. Klar, oder? Außerdem haben wir definiert, dass der Zustand z1 für diesen Schritt verantwortlich sein soll, also wechseln wir in diesen Zustand. Wie du in der Tabelle sehen kannst, haben wir das oberste Zeichen im Keller mit einem ε ersetzt. Das ist das sogenannte leere Wort. Da dieses aus keinen Zeichen besteht, und das erste Zeichen im Keller ersetzt, hat es denselben Effekt wie eine Löschung des aktuellen obersten Zeichens. Alle folgenden Einsen werden ebenfalls eine Null aus dem Keller löschen, hierfür bleiben wir im Zustand z1.
Übergang Endzustand
Zu guter Letzt benötigen wir einen Übergang in den Endzustand. Wann soll dieser passieren? Ein Wort soll dann akzeptiert werden, wenn nach der Abarbeitung einer Eingabe nur noch das Anfangszeichen im Keller steht. Wir schauen also nach, ob ohne Eingabe, also unter Eingabe des leeren Wortes, im Keller ein „Z“ steht. Wenn ja, gehen wir in den Endzustand z2 über und leeren den Keller vollständig. Fertig!