Im vorletzten Post wurden Endliche Automaten erläutert. Dieser Automatentyp ist zwar sehr einfach, aber auch beschränkt in seiner Anwendung. In diesem Post wird der Kellerautomat erläutert - ein Automat, der einen Speicher besitzt und so zum Beispiel auch Palindrome erkennen kann.

Keller

Der Keller

Gegenüber einem Endlichen Automaten unterscheidet sich ein Keller-Automat durch den Keller. Der Keller ist ein Stack, mithilfe dessen sich der Automat Dinge merken kann. Wichtig: Man kann bei einem Stack neue Werte nur oben anfügen sowie den obersten Wert auslesen. Liest man den obersten Wert aus, wird dieser auch sofort entfernt1.

Die Definition eines Kellerautomat wächst im Vergleich zum Endlichen Automaten um zwei Parameter:

Das Keller-Alphabet Γ\Gamma, welches alle für den Keller zulässigen Symbole enthält, sowie das Initial-Symbol des Kellers, bezeichnet als ZZ.

A=(Q,Σ,Γ,δ,q0,Z,F)\displaystyle A = (Q, \Sigma, \Gamma, \delta, q_0, Z, F)

δ\delta, die Übergangsfunktion, verändert sich leicht, um nun zusätzlich die Veränderung des Kellers abzubilden.

Ein Beispiel

Ein einfacher Kellerautomat wäre dieser, der die Sprache L={w∈Σ∗∣w=anbn,n>0}L=\{ w \in \Sigma^* | w=a^nb^n, n > 0 \} (nn mal “a”, dann nn mal “b”) erkennt.

graphviz-ff9397a8889cb99640cfd942bd93e919 digraph anbn { rankdir=LR; size="8,5"; node [shape = doublecircle];q2; node [shape = point]; qi; node [shape = circle]; qi -> q0; q0 -> q0 [ label = "a,#;#A" ]; q0 -> q0 [ label = "a,A;AA" ]; q0 -> q1 [ label = "b,A;ε" ]; q1 -> q1 [ label = "b,A;ε" ]; q1 -> q2 [ label = "ε,#;#" ]; } anbn q2 q2 qi q0 q0 qi->q0 q0->q0 a,#;#A q0->q0 a,A;AA q1 q1 q0->q1 b,A;ε q1->q2 ε,#;# q1->q1 b,A;ε

Wie liest man so einen Übergangsgraphen?
Der Pfeil a,#;#A von q0q_0 nach q0q_0 bedeutet: Wenn du in q0q_0 bist, ein “a” eingelesen hast und der oberste Wert des Kellers ein “#”2 ist, dann gehe nach q0q_0 und lege ein “#” sowie ein “A” auf den Keller drauf.

Der obige Automat funktioniert so:

Zu Beginn werden alle “a”s des Wortes eingelesen, für jedes eingelesene “a” wird ein “A” auf den Keller gelegt.
Die Anzahl der “A” im Keller repräsentiert also die Anzahl der “a”, mit denen die Eingabe beginnt.

Sobald das erste “b” kommt, wird zu q1q_1 gewechselt. Nun wird für jedes folgende “b” ein “A” aus dem Keller genommen.

Am Ende des Wortes (wenn das leere Wort ε eingelesen wird) steht also im Keller ein “A” für jedes “a” ohne entsprechendes “b”. Ist der Keller leer (“#” ist das oberste Keller-Symbol), ist die Anzahl der “a” gleich der Anzahl der “b” und das Wort wird angenommen.

Was kann ein Kellerautomat?

Ein Kellerautomat kann sich Dinge über seine Eingabe merken, dadurch kann er deutlich mehr Sprachen abbilden als ein Endlicher Automat.

So kann ein Kellerautomat zum Beispiel auch Palindrome erkennen, deren Wortmitte markiert ist:

L={w∈Σ∗∣w=m0mreverse,m∈(Σ∖0)∗}\displaystyle L = \{ w \in \Sigma^* | w = m0m_{reverse}, m \in (\Sigma \setminus{0})^* \}
graphviz-b3ab0aa73229d71ef5f7d00902d469b8 digraph anbn { rankdir=LR; size="8,5"; node [shape = doublecircle];q2; node [shape = point]; qi; node [shape = circle]; qi -> q0; q0 -> q0 [ label = "a,#;#A" ]; q0 -> q0 [ label = "a,A;AA" ]; q0 -> q0 [ label = "a,B;BA" ]; q0 -> q0 [ label = "b,#;#B" ]; q0 -> q0 [ label = "b,A;AB" ]; q0 -> q0 [ label = "b,B;BB" ]; q0 -> q1 [ label = "0,A;A" ]; q0 -> q1 [ label = "0,B;B" ]; q1 -> q1 [ label = "b,B;ε" ]; q1 -> q1 [ label = "a,A;ε" ]; q1 -> q2 [ label = "ε,#;#" ]; } anbn q2 q2 qi q0 q0 qi->q0 q0->q0 a,#;#A q0->q0 a,A;AA q0->q0 a,B;BA q0->q0 b,#;#B q0->q0 b,A;AB q0->q0 b,B;BB q1 q1 q0->q1 0,A;A q0->q1 0,B;B q1->q2 ε,#;# q1->q1 b,B;ε q1->q1 a,A;ε

Der gezeigte Automat ist ein deterministischer Kellerautomat.

Mit einem nichtdeterministischen Kellerautomaten kann man ein Palindrom auch ohne eine Markierung der Wortmitte erkennen:

L={w∈Σ∗∣w=mmreverse,m∈Σ∗}\displaystyle L = \{ w \in \Sigma^* | w = mm_{reverse}, m \in \Sigma^* \}
graphviz-28ca4a7766b1388d5a9362ed41407e68 digraph anbn { rankdir=LR; size="8,5"; node [shape = doublecircle];q2; node [shape = point]; qi; node [shape = circle]; qi -> q0; q0 -> q0 [ label = "a,#;#A" ]; q0 -> q0 [ label = "a,A;AA" ]; q0 -> q0 [ label = "a,B;BA" ]; q0 -> q0 [ label = "b,#;#B" ]; q0 -> q0 [ label = "b,A;AB" ]; q0 -> q0 [ label = "b,B;BB" ]; q0 -> q1 [ label = "a,A;ε" ]; q0 -> q1 [ label = "b,B;ε" ]; q1 -> q1 [ label = "b,B;ε" ]; q1 -> q1 [ label = "a,A;ε" ]; q1 -> q2 [ label = "ε,#;#" ]; } anbn q2 q2 qi q0 q0 qi->q0 q0->q0 a,#;#A q0->q0 a,A;AA q0->q0 a,B;BA q0->q0 b,#;#B q0->q0 b,A;AB q0->q0 b,B;BB q1 q1 q0->q1 a,A;ε q0->q1 b,B;ε q1->q2 ε,#;# q1->q1 b,B;ε q1->q1 a,A;ε

Daraus wird erkenntlich, dass es, anders als beim Endlichen Automaten, keine einfache Übersetzung zwischen deterministischen und nichtdeterministischen Kellerautomaten gibt - der nichtdeterministische kann mehr Sprachen erkennen.

Was kann ein Kellerautomat nicht?

Der Schwachpunkt des Kellerautomaten ist der Keller: Da der Keller nicht beliebig beschrieben werden kann, sind bestimmte Sprachen nicht durch ihn erkennbar.

Ein Beispiel: L={w∈Σ∗∣anbncn}L = \{ w \in \Sigma^* | a^nb^nc^n \}

Diese Sprache kann von einem Kellerautomaten nicht erkannt werden, da er zum validieren der “b”s bereits seinen Keller leeren muss. Um die Menge der “c”s zu validieren fehlen ihm die nötigen Keller-Elemente.

Auch die Sprache L={w∈Σ∗∣mm,m∈Σ∗}L = \{ w \in \Sigma^* | mm, m \in \Sigma^* \} kann vom Kellerautomaten nicht erkannt werden, da der Keller dafür von unten nach oben ausgelesen werden müsste.

Solche Sprachen können von einer Turing-Maschine erkannt werden, die in einem zukünftigen Post erklärt wird.

TL;DR

Der Kellerautomat erweitert den Endlichen Automaten um einen Speicher. Dieser Speicher ist ein Stack, in dem Elemente des Keller-Alphabets Γ\Gamma gespeichert werden.

Ein Kellerautomat, der die Sprache anbna^nb^n erkennt, sieht so aus:

graphviz-ff9397a8889cb99640cfd942bd93e919 digraph anbn { rankdir=LR; size="8,5"; node [shape = doublecircle];q2; node [shape = point]; qi; node [shape = circle]; qi -> q0; q0 -> q0 [ label = "a,#;#A" ]; q0 -> q0 [ label = "a,A;AA" ]; q0 -> q1 [ label = "b,A;ε" ]; q1 -> q1 [ label = "b,A;ε" ]; q1 -> q2 [ label = "ε,#;#" ]; } anbn q2 q2 qi q0 q0 qi->q0 q0->q0 a,#;#A q0->q0 a,A;AA q1 q1 q0->q1 b,A;ε q1->q2 ε,#;# q1->q1 b,A;ε

Die Menge der Sprachen, die ein nichtdeterministischer Kellerautomat erkennt, ist eine Übermenge der Sprachen, die ein deterministischer Kellerautomat erkennt.

Auch ein Kellerautomat erkennt nicht alle Sprachen, er ist durch den Stack beschränkt. Eine Turingmaschine kann zum Beispiel die Sprache anbncna^nb^nc^n erkennnen.

  1. Wie man einen Stack implementiert, kann in meinem Post über Stacks nachgelesen werden. ↩

  2. ”#” ist per Konvention immer das unterste Element des Kellers. ↩