Zum Inhalt springen

Formale Sprache

Aus FLBK-Wiki

Ein Kellerautomat ist ein endlicher Automat mit zusätzlichem Speicher. Damit kann er verschachtelte Strukturen wie Klammern prüfen.

Definition

Ein Kellerautomat ist ein 7-Tupel [math]\displaystyle{ M = (Q; \Sigma; \Gamma; \delta; q_0; \#; F) }[/math]. Wie beim endlichen Automaten ist [math]\displaystyle{ Q }[/math] die endliche, nicht leere Zustandsmenge, [math]\displaystyle{ \Sigma }[/math] das Eingabealphabet, [math]\displaystyle{ \delta }[/math] die Übergangsfunktion (siehe Formale Darstellung), [math]\displaystyle{ q_0 \in Q }[/math] der Startzustand und [math]\displaystyle{ F \subseteq Q }[/math] die Menge der Endzustände. Zusätzlich besitzt der Kellerautomat:

  • das Kelleralphabet [math]\displaystyle{ \Gamma }[/math], die Menge der Zeichen, die im Keller liegen dürfen. Diese Zeichen heißen Kellerzeichen.
  • das Kellerbodensymbol [math]\displaystyle{ \# \in \Gamma }[/math], das zu Beginn als einziges Zeichen im Keller liegt. Es gehört selbst zu den Kellerzeichen.

Der Keller ist ein unbegrenzter Speicher: Er kann beliebig viele Zeichen aufnehmen. Er arbeitet nach dem LIFO-Prinzip (last in, first out) wie ein Stapel. Der Automat sieht nur das oberste Zeichen. Das zuletzt abgelegte Zeichen wird als Erstes wieder entfernt. Das Kellerbodensymbol markiert den Boden: Liegt es oben, weiß der Automat, dass kein anderes Zeichen mehr im Keller ist.

Arbeitsweise

Ein Schritt hängt vom Zustand, vom nächsten Eingabezeichen und vom obersten Kellerzeichen ab. Diese drei Angaben bilden die Lage des Automaten. Der Automat wechselt den Zustand und ersetzt das oberste Kellerzeichen durch ein Wort aus Kellerzeichen, das Ersatzwort. Je nach Ersatzwort wirkt der Schritt so auf den Keller:

  • Ablegen: Das Ersatzwort besteht aus dem bisherigen obersten Zeichen und einem weiteren Zeichen. Der Keller wird höher.
  • Entfernen: Das Ersatzwort ist leer. Das oberste Zeichen verschwindet. Das leere Ersatzwort wird [math]\displaystyle{ \varepsilon }[/math] geschrieben.
  • Unverändert lassen: Das Ersatzwort besteht nur aus dem bisherigen obersten Zeichen.

Eine Ausnahme ist der [math]\displaystyle{ \varepsilon }[/math]-Übergang: Bei ihm liest der Automat kein Eingabezeichen. Die Eingabe bleibt stehen, nur Zustand und Keller ändern sich. Der Automat führt ihn aus, sobald Zustand und oberstes Kellerzeichen passen. Das nächste Eingabezeichen spielt dabei keine Rolle.

Ein Kellerautomat ist deterministisch, wenn in jeder Lage höchstens ein Übergang möglich ist. Für einen Zustand und ein oberstes Kellerzeichen gibt es dann entweder Übergänge mit Eingabezeichen oder einen [math]\displaystyle{ \varepsilon }[/math]-Übergang, nie beides. Nichtdeterministische Kellerautomaten dürfen wie ein NEA mehrere Möglichkeiten offenhalten.

Akzeptanz

Der Kellerautomat akzeptiert ein Wort, wenn die Eingabe vollständig gelesen ist und er in einem Endzustand steht. Mögliche [math]\displaystyle{ \varepsilon }[/math]-Übergänge am Ende der Eingabe werden vorher noch ausgeführt. Gibt es in einer Lage keinen passenden Übergang, obwohl noch Eingabe übrig ist, bricht der Automat ab und lehnt das Wort ab.

Was am Ende noch im Keller liegt, spielt für diese Akzeptanz keine Rolle. Soll der Automat ein Wort nur dann akzeptieren, wenn alle abgelegten Zeichen wieder entfernt sind, muss er das über seine Zustände sicherstellen: Er darf nur dann in einem Endzustand stehen, wenn im Keller nur noch das Kellerbodensymbol [math]\displaystyle{ \# }[/math] liegt. Im ersten Beispiel führt deshalb nur ein [math]\displaystyle{ \varepsilon }[/math]-Übergang in den Endzustand zurück, der [math]\displaystyle{ \# }[/math] oben verlangt und den Keller unverändert lässt.

Andere Quellen akzeptieren stattdessen bei leerem Keller. Anders als bei endlichen Automaten leisten nichtdeterministische Kellerautomaten mehr als deterministische: Sie erkennen alle kontextfreien Sprachen, deterministische Kellerautomaten nur einen Teil davon.

Formale Darstellung

Die Übergangsfunktion eines deterministischen Kellerautomaten hat die Form [math]\displaystyle{ \delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to Q \times \Gamma^* }[/math]. Sie ordnet dem Zustand, dem Eingabezeichen (oder [math]\displaystyle{ \varepsilon }[/math]) und dem obersten Kellerzeichen einen Folgezustand und ein Ersatzwort zu. [math]\displaystyle{ \Gamma^* }[/math] ist die Menge aller Wörter aus Kellerzeichen einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math], siehe Kleenesche Hülle. Die Übergangsfunktion muss nicht für jede Lage einen Wert haben.

In der Tabelle steht jede Zeile für einen Übergang. Die Spalten heißen Zustand, Eingabe, oben im Keller, Folgezustand und ersetzt durch. Die Spalte „oben im Keller“ nennt das oberste Kellerzeichen, die Spalte „ersetzt durch“ das Ersatzwort. Ein Ersatzwort wird von links nach rechts geschrieben, sein letztes Zeichen liegt danach oben. Für Lagen, die in der Tabelle fehlen, gibt es keinen Übergang.

Anwendung und Grenzen

Ein Compiler arbeitet beim Prüfen eines Programms wie ein Kellerautomat: Er legt für jede geöffnete Klammer und jeden begonnenen Block einen Eintrag auf einem Stapel ab und entfernt den obersten Eintrag, sobald die passende schließende Klammer folgt. Passt sie nicht oder bleibt am Ende ein Eintrag übrig, meldet er einen Syntaxfehler.

Mit dem Keller kann ein Automat zwei Anzahlen vergleichen: Er legt für jedes Zeichen des ersten Blocks ein Kellerzeichen ab und entfernt für jedes Zeichen des zweiten Blocks eines. Auch mehrere solche Vergleiche gelingen, wenn sie nacheinander stattfinden oder ineinander verschachtelt sind. Dieselbe Anzahl ein zweites Mal zu vergleichen gelingt nicht: Nach dem ersten Vergleich sind die abgelegten Zeichen entfernt, und die Anzahl ist verloren. Drei gleich lange Blöcke wie in der Sprache [math]\displaystyle{ \{a^n b^n c^n \mid n \geq 1\} }[/math] erkennt deshalb kein Kellerautomat, siehe Sprachen einordnen.

Beispiele

Klammerausdruck mit einem Keller prüfen

Der Kellerautomat prüft, ob jede öffnende Klammer eine passende schließende hat. Als 7-Tupel [math]\displaystyle{ M = (Q; \Sigma; \Gamma; \delta; q_0; \#; F) }[/math] hat er diese Bestandteile:

  • [math]\displaystyle{ Q = \{q_0; q_1\} }[/math]
  • [math]\displaystyle{ \Sigma = \{(; )\} }[/math]
  • [math]\displaystyle{ \Gamma = \{\#; K\} }[/math]
  • Startzustand [math]\displaystyle{ q_0 }[/math] und Kellerbodensymbol [math]\displaystyle{ \# }[/math]
  • [math]\displaystyle{ F = \{q_0\} }[/math]

In [math]\displaystyle{ q_0 }[/math] sind alle bisher geöffneten Klammern wieder geschlossen. In [math]\displaystyle{ q_1 }[/math] liest der Automat einen begonnenen Klammerausdruck. Jede öffnende Klammer legt ein [math]\displaystyle{ K }[/math] ab, jede schließende Klammer entfernt ein [math]\displaystyle{ K }[/math]. Liegt in [math]\displaystyle{ q_1 }[/math] nur noch [math]\displaystyle{ \# }[/math] im Keller, wechselt der Automat ohne Eingabezeichen zurück nach [math]\displaystyle{ q_0 }[/math]. Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] steht in der Tabelle:

Zustand Eingabe oben im Keller Folgezustand ersetzt durch
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ( }[/math] [math]\displaystyle{ \# }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \#K }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ( }[/math] [math]\displaystyle{ K }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ KK }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ K }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math] [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \# }[/math]

Der Keller wird von links nach rechts geschrieben, oben steht rechts. Das Protokoll zeigt den Lauf für [math]\displaystyle{ (()) }[/math]. Zu Beginn liegt nur [math]\displaystyle{ \# }[/math] im Keller.

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ (()) }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ()) }[/math] [math]\displaystyle{ \#K }[/math]
2 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ )) }[/math] [math]\displaystyle{ \#KK }[/math]
3 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \#K }[/math]
4 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]
5 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]
Kellerbelegung beim Lesen von (())

In Schritt 1 liest der Automat die erste öffnende Klammer, legt ein [math]\displaystyle{ K }[/math] auf [math]\displaystyle{ \# }[/math] und wechselt nach [math]\displaystyle{ q_1 }[/math]. In Schritt 2 legt die zweite öffnende Klammer ein weiteres [math]\displaystyle{ K }[/math] ab. In den Schritten 3 und 4 entfernt jede schließende Klammer ein [math]\displaystyle{ K }[/math]. Danach liegt nur noch [math]\displaystyle{ \# }[/math] im Keller. Schritt 5 ist der [math]\displaystyle{ \varepsilon }[/math]-Übergang: Er führt ohne Eingabezeichen nach [math]\displaystyle{ q_0 }[/math]. Am Ende ist alles gelesen, und [math]\displaystyle{ q_0 }[/math] ist ein Endzustand. Der Automat akzeptiert [math]\displaystyle{ (()) }[/math].

Abgelehntes Wort protokollieren

Das Protokoll für [math]\displaystyle{ (() }[/math] zeigt, warum der Automat dieses Wort ablehnt.

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ (() }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ () }[/math] [math]\displaystyle{ \#K }[/math]
2 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \#KK }[/math]
3 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \#K }[/math]

Alles ist gelesen, aber ein [math]\displaystyle{ K }[/math] liegt noch im Keller. Der Automat steht in [math]\displaystyle{ q_1 }[/math], und [math]\displaystyle{ q_1 }[/math] ist kein Endzustand. Für [math]\displaystyle{ q_1 }[/math] mit [math]\displaystyle{ K }[/math] oben gibt es keinen [math]\displaystyle{ \varepsilon }[/math]-Übergang, der Automat bleibt dort stehen. Er lehnt [math]\displaystyle{ (() }[/math] ab.

Über die Akzeptanz entscheidet dabei der Zustand, nicht der Keller: Wäre auch [math]\displaystyle{ q_1 }[/math] ein Endzustand, würde der Automat [math]\displaystyle{ (() }[/math] akzeptieren, obwohl noch ein [math]\displaystyle{ K }[/math] im Keller liegt.

ε-Übergang mitten in der Eingabe verfolgen

Das Wort [math]\displaystyle{ ()() }[/math] besteht aus zwei Klammerpaaren nacheinander. Der Automat aus dem ersten Beispiel führt den [math]\displaystyle{ \varepsilon }[/math]-Übergang hier zweimal aus:

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ()() }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ )() }[/math] [math]\displaystyle{ \#K }[/math]
2 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ () }[/math] [math]\displaystyle{ \# }[/math]
3 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ () }[/math] [math]\displaystyle{ \# }[/math]
4 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \#K }[/math]
5 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]
6 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]

Nach dem ersten Klammerpaar liegt in Schritt 2 nur noch [math]\displaystyle{ \# }[/math] im Keller. In [math]\displaystyle{ q_1 }[/math] mit [math]\displaystyle{ \# }[/math] oben gibt es nur den [math]\displaystyle{ \varepsilon }[/math]-Übergang, also führt der Automat ihn in Schritt 3 aus, obwohl noch Eingabe übrig ist. Zurück in [math]\displaystyle{ q_0 }[/math] kann er die nächste öffnende Klammer lesen. Am Ende ist alles gelesen, und der Automat steht im Endzustand [math]\displaystyle{ q_0 }[/math]: Er akzeptiert [math]\displaystyle{ ()() }[/math].

Schließende Klammer ohne Partner ablehnen

Im Wort [math]\displaystyle{ ()) }[/math] gehört zur letzten schließenden Klammer keine öffnende.

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ()) }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ )) }[/math] [math]\displaystyle{ \#K }[/math]
2 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \# }[/math]
3 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \# }[/math]

Nach dem Klammerpaar wechselt der Automat mit dem [math]\displaystyle{ \varepsilon }[/math]-Übergang nach [math]\displaystyle{ q_0 }[/math]. Dort trifft die übrige schließende Klammer auf das Kellerbodensymbol [math]\displaystyle{ \# }[/math]. Für diese Lage gibt es keinen Übergang, der Automat bricht ab. Die Eingabe ist nicht vollständig gelesen, das Wort wird abgelehnt.

Zwei Klammerarten mit zwei Kellerzeichen prüfen

Kellerbelegung beim Lesen von ([])

In Programmen kommen runde und eckige Klammern gemischt vor. Jede schließende Klammer muss zur zuletzt geöffneten Klammer passen: [math]\displaystyle{ ([]) }[/math] ist korrekt, [math]\displaystyle{ (] }[/math] nicht. Neben dem Kellerbodensymbol reicht ein einziges Kellerzeichen dafür nicht mehr, denn der Automat muss sich die Art jeder offenen Klammer merken. Das Kelleralphabet ist [math]\displaystyle{ \Gamma = \{\#; R; E\} }[/math]: [math]\displaystyle{ R }[/math] steht für eine offene runde, [math]\displaystyle{ E }[/math] für eine offene eckige Klammer. Der Automat hat wie im ersten Beispiel die Zustandsmenge [math]\displaystyle{ Q = \{q_0; q_1\} }[/math], den Startzustand [math]\displaystyle{ q_0 }[/math] und die Endzustandsmenge [math]\displaystyle{ F = \{q_0\} }[/math]. Sein Eingabealphabet ist [math]\displaystyle{ \Sigma = \{(; ); [; ]\} }[/math].

Zustand Eingabe oben im Keller Folgezustand ersetzt durch
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ( }[/math] [math]\displaystyle{ \# }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \#R }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ [ }[/math] [math]\displaystyle{ \# }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \#E }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ( }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ RR }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ( }[/math] [math]\displaystyle{ E }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ER }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ [ }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ RE }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ [ }[/math] [math]\displaystyle{ E }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ EE }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ] }[/math] [math]\displaystyle{ E }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math] [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \# }[/math]

Eine schließende runde Klammer darf nur gelesen werden, wenn [math]\displaystyle{ R }[/math] oben liegt, eine schließende eckige nur, wenn [math]\displaystyle{ E }[/math] oben liegt. Das Protokoll für [math]\displaystyle{ ([]) }[/math]:

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ ([]) }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ []) }[/math] [math]\displaystyle{ \#R }[/math]
2 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ]) }[/math] [math]\displaystyle{ \#RE }[/math]
3 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \#R }[/math]
4 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]
5 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \varepsilon }[/math] [math]\displaystyle{ \# }[/math]

Alles ist gelesen, der Automat steht im Endzustand [math]\displaystyle{ q_0 }[/math] und akzeptiert. Für [math]\displaystyle{ (] }[/math] ergibt sich:

Schritt Zustand Resteingabe Keller (oben rechts)
0 [math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ (] }[/math] [math]\displaystyle{ \# }[/math]
1 [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ ] }[/math] [math]\displaystyle{ \#R }[/math]

Oben liegt [math]\displaystyle{ R }[/math], gelesen werden soll die schließende eckige Klammer. Für diese Lage gibt es keinen Übergang, der Automat bricht ab und lehnt das Wort ab.