Zum Inhalt springen

Kellerautomat

Aus FLBK-Wiki
Version vom 8. November 2026, 09:07 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „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>M = (Q, \Sigma, \Gamma, \delta, q0, \#, F)</math>. Wie beim endlichen Automaten ist <math>Q</math> die endliche, nicht leere Zustandsmenge, <math>\Sigma</math> das Eingabealphabet, <math>\delta</math> die Übergangsfunktion (siehe #…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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, q0, \#, 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{ q0 \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,
  • das Kellerbodensymbol [math]\displaystyle{ \# \in \Gamma }[/math], das den Boden des Kellers markiert und zu Beginn als einziges Zeichen im Keller liegt.

Der Keller 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.

Arbeitsweise

Jeder Schritt berücksichtigt den Zustand, das nächste Eingabezeichen oder [math]\displaystyle{ \varepsilon }[/math] (dann liest der Automat kein Zeichen) und das oberste Kellerzeichen. Diese drei Angaben bilden die Lage des Automaten. Der Automat wechselt den Zustand und ersetzt das oberste Kellerzeichen durch ein Wort aus Kellerzeichen. Je nach Ersatzwort wirkt der Schritt so auf den Keller:

  • Ablegen: Das Ersatzwort ist länger als ein Zeichen. Der Keller wird höher.
  • Entfernen: Das Ersatzwort ist leer. Das oberste Zeichen verschwindet.
  • Unverändert lassen: Das Ersatzwort besteht nur aus dem bisherigen obersten Zeichen.

Akzeptanz

Der Kellerautomat akzeptiert ein Wort, wenn die Eingabe vollständig gelesen ist und ein Endzustand erreicht wurde. Gibt es in einer Lage keinen passenden Übergang, bricht der Automat ab und lehnt das Wort ab.

Andere Quellen akzeptieren stattdessen bei leerem Keller. Deterministische Kellerautomaten erkennen nicht alle kontextfreien Sprachen.

Formale Darstellung

Die Übergangsfunktion 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.

In der Tabelle steht jede Zeile für einen Übergang mit den Spalten Zustand, Eingabe, oberstes Kellerzeichen, Folgezustand und Ersatzwort. Ein Ersatzwort wird von links nach rechts geschrieben, sein letztes Zeichen liegt danach oben. Beim deterministischen Automaten passt in jeder Lage höchstens eine Zeile.

Beispiele

Klammerausdruck mit einem Keller prüfen

Der Kellerautomat prüft, ob jede öffnende Klammer eine passende schließende hat. Er hat die Zustände q0 (Startzustand und Endzustand) und q1, das Eingabealphabet [math]\displaystyle{ \Sigma = \{(, )\} }[/math] und das Kelleralphabet [math]\displaystyle{ \Gamma = \{\#, K\} }[/math]. Jedes ( legt ein K ab, jedes ) entfernt ein K.

Zustand Eingabe oben im Keller Folgezustand ersetzt durch
q0 ( # q1 #K
q1 ( K q1 KK
q1 ) K q1 ε
q1 ε # q0 #

Der Keller wird von links nach rechts geschrieben, oben steht rechts. Das Protokoll zeigt den Lauf für (()). Zu Beginn liegt nur # im Keller.

Schritt Zustand Resteingabe Keller (oben rechts)
0 q0 (()) #
1 q1 ()) #K
2 q1 )) #KK
3 q1 ) #K
4 q1 ε #
5 q0 ε #
Kellerbelegung beim Lesen von (())

In Schritt 4 liegt nur noch # im Keller. Schritt 5 ist der ε-Übergang: Er führt ohne Eingabezeichen nach q0. Am Ende ist alles gelesen, und q0 ist ein Endzustand. Der Automat akzeptiert (()).

Abgelehntes Wort protokollieren

Das Protokoll für (() zeigt, warum der Automat dieses Wort ablehnt.

Schritt Zustand Resteingabe Keller (oben rechts)
0 q0 (() #
1 q1 () #K
2 q1 ) #KK
3 q1 ε #K

Alles ist gelesen, aber ein K liegt noch im Keller. Der Automat steht in q1, und q1 ist kein Endzustand. Für q1 mit K oben gibt es keinen Übergang ohne Eingabezeichen, der Automat bricht ab. Er lehnt (() ab.