1.6 Kellerautomaten
Wie wir im letzten Abschnitt gesehen haben, haben endliche Automaten ihre Grenzen. Beispielsweise können sie nicht zählen, da sie nur endlich viele Zustände und keinen Speicher haben. Ein Kellerautomat ist ein Automat mit einem speziellem Speicher. Dieser Speicher ist unbegrenzt und heisst Keller oder auch Stack (zu Deutsch “Stapel”) und funktioniert nach dem LIFO- (last in, first out) Prinzip. Analogie Stack Merkhilfe
Erinnern wir uns an das Beispiel, für welches wir keinen EA konstruieren konnten.
Beispiel \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\) als KA
Wir möchten einen Kellerautomaten (KA) konstruieren, der nur für die Eingabefolge \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\) (also bestehend aus einer beliebigen Anzahl Nullen, gefolgt von derselben Anzahl Einsen) in einem akzeptierenden Zustand landet. Das \(n\) ist aber nicht fest. D.h. er soll beispielsweise \(0011 \) aber auch \(00001111 \) akzeptieren. Dieser KA hat nun einen unbegrenzten Kellerspeicher. Die Idee liegt darin, dass wir für jede \(0\) ein Zeichen in den Keller schreiben und für jede \(1\) ein Zeichen aus dem Keller löschen. Wenn der Keller am Schluss leer ist, hatte das Wort gleichviele Nullen wie Einsen.
Die folgende Grafik beschreibt diesen KA.
- Eine grafische Veranschaulichung was Schritt für Schritt im Keller für das Wort \(0011\) passiert, finden Sie via dem folgenden Knopf Veranschaulichung für 0011 .
- Im folgenden Video wird der Kellerautomat erklärt und dieses Beispiel erläutert. (Anstatt der Ziffer \(0\) wird der Buchstabe \(a\), anstelle der \(1\) der Buchstabe \(b\) und anstelle des \(X\) der Buchstabe \(A\) verwendet. Ausserdem wird eine Notation für \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\) bzw. \(\underbrace{aa..a}_{n}\underbrace{bb..b}_{n}\) verwendet, welche wir noch nicht kennen. Es entspricht aber genau dieses Beispiel.)
Definition: Kellerautomat (NKA)
Ein nichtdeterministischer Kellerautomat (NKA) ist ein 7-Tupel \(M = (Q, Σ, Γ, \delta, q_0, \#, F)\), wobei
- \(Q\) ist eine endliche Menge von Zuständen.
- \( Σ\) ist das Eingabealphabet.
- \(Γ\) ist das Kelleralphabet (= Menge von Symbolen, die in den Keller geschrieben werden können).
- \(\delta : Q×(Σ\cup ε) ×Γ→ P((Q×Γ^* ))\) ist die Übergangsfunktion.
- \(q_0 \in Q\) ist der Startzustand.
- \(\# \in Γ\) ist das Kellersymbol, ein ausgewähltes Symbol des Kelleralphabets, das das Ende des Kellers anzeigt. Anfangs enthält der Keller das Symbol \(\#\).
- \( F \subseteq Q \) ist die Menge der akzeptierenden Zustände.
Bemerkungen
- \(Γ^* \) ist die Menge aller Kombinationen von Elementen von \(Γ\) . Beispiele Γ*
- Die Übergangsfunktion \(\delta \) bildet Elemente (wie der NEA) auf eine Potenzmenge ab. D.h. dass die Übergänge nicht eindeutig sind. Deshalb heisst der oben definierte Kellerautomat nichtdeterministisch.
- Es gibt auch deterministische Kellerautomaten. Diese unterscheiden sich nur in der Übergangsfunktion und sind von weniger grossen Bedeutung. Wenn wir von KA sprechen, sind NKA gemeint.
- Für uns wird später wieder entscheidend sein, ob ein NKA für ein Wort in einem akzeptierenden Zustand landen kann. Ob der Keller am Schluss leer ist oder nicht, ist für uns nicht relevant. Es gibt verschiedene äquivalente Definitionen, bei welchen der Keller am Schluss leer sein müsste.
- Wir verwenden die Kellerautomaten so, dass sie leer sein müssen, um in einem akzeptierenden Zustand zu landen. Es gibt äquivalente Definitionen, welche dies nicht verlangen.
Beispiel geschlossene Klammern
Rechtsstehend ist die vollständige Definition eines KA zu finden, welcher als Eingabe Klammern nimmt und nur dann in einem akzeptierenden Zustand landet, wenn im Eingabewort ein Klammerausdruck der Gestalt (((….))) also geschachtelter Klammern war, wobei alle offenen Klammern der Reihe nach wieder geschlossen wurden. “(())” und “((()))” werden im akzeptierenden Zustand landen, während beispielsweise “()()”, “(()”, (()))” und “()(” nicht in einem akzeptierenden Zustand landen werden.
Vielleicht haben Sie bemerkt, dass dieser KA analog funktioniert, wie der letzte KA. Dies liegt daran, dass letztendlich beide ein bestimmtes Zeichen mit Hilfe des Kellerspeichers zählen und mit der Anzahl des anderen Zeichen vergleichen, wobei eine gewisse Reihenfolge eingehalten werden muss.
Grenzen von Kellerautomaten
Auch Kellerautomaten (deterministische sowie nichtdeterministische) haben ihre Grenzen. Mit dem Keller kann nur einmal eine Anzahl verglichen werden, danach sind die Symbole nicht mehr auf dem Keller. Möchten wir unser erstes Beispiel vom KA zu einem KA erweitern, so dass er nur für die Eingabefolgen die aus gleichvielen 0, 1 und 2 bestehen ( \(\underbrace{00..0}_{n}\underbrace{11..1}_{n}\underbrace{22..2}_{n}\) ) in einem akzeptierenden Zustand landet, scheitern wir. Denn nach dem “Einkellern” mit den Nullen und dem “Auskellern” mit den Einsen sind keine Informationen über die Anzahl der Zeichen mehr vorhanden.
Zwei Kellerspeicher würden dieses Problem lösen. Und für das übernächste Problem brauchen wir vielleicht drei, vier oder viel mehr Kellerstapel. Um nicht eine ganze Familie von Automaten mit zwei, drei usw. Stapel zu betrachten, hat sich der Mathematiker Alan Turing (1912 – 1954) eine universellere Maschine überlegt, die sogenannte Turingmaschine .
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 1_6_KA_Notizen.