Deterministischer Kellerautomat

Kellerautomaten erweitern den Deterministischer Endlicher Automat (DEA) um einen Kellerspeicher (Stapel). Dienen zur Erkennung, ob eine Zeichenfolge (ein “Wort”) zu einer Sprache (z.B. Programmiersprache) gehört oder nicht.

Kellerspeicher

• Stapel / Stack
  • theoretisch unendlich groß
  • besitzt “Kellerboden”: # (unterstes Kellerelement, das nicht entfernt wird)
  • kann nur mit Elementen des Kelleralphabets beschrieben werden
• beim Einlesen, des Eingabezeichens wird zusätzlich das jeweils oberste Zeichen des Kellerspeichers gelesen (und dabei vom Stapel entfernt)
• der Übergang zwischen Zuständen ab
  • aktuellen Eingabezeichen
  • jeweils obersten Zeichen des Kellerspeichers

Formale Definition

Menge der Zustände: $Z$ Startzustand $Z_{start}$ Eingabealphabet $E$ Kelleralphabet $\Gamma$ Zustandsübergangsfunktion $\delta$

Definition	Beispiel
endliche (nicht leere) Menge von Zuständen	$Z=\{Z_1;Z_2;\dots ,Z_n\}$
Eingabealphabet: endliche (nicht leere) Menge	$\Sigma =\{a_1;a_2,\dots ;a_n\}$
Kelleralphabet: endliche (nicht leere) Menge	$\Gamma =\{k_1;k_2;\dots ;k_n\}$
**Zustandsübergangsfunktion **$\delta$	$Z_m\to a_i,k_j,k_p,k_q\to Z_n$
genau ein Startzustand	$Z_0\in Z$
mindestens einen Endzustand (“Finalzustand”)	$F=\{F_1;F_2;\dots ;F_n\}\subseteq Z$
Kellerboden (Anfangssymbol im Keller, Keller ist leer)	$\#\in \Gamma$

Ein Wort gehört nicht zur Sprache, wenn:

• nach vollständiger Abarbeitung des Eigabewortes der Keller nicht leer ist
• ein Übergang in die konkrete Kombination aus Eingabe- und Kellerzeichen nicht existiert

Tipp

Beispiele: Klammererkenner, Palindromerkenner