Kellerautomat

Ein deterministischer endlicher Automat (DEA) kann reguläre Sprachen erkennen, scheitert aber an Sprachen, die Zählen erfordern (z. B. gleich viele öffnende wie schließende Klammern). Der Kellerautomat (Pushdown Automaton, PDA) erweitert den DEA um einen Stack (Kellerspeicher) und kann dadurch kontextfreie Sprachen erkennen.

Ein Kellerautomat besteht aus:

• Endliche Zustandsmenge Q mit Startzustand q₀
• Eingabealphabet Σ
• Kelleralphabet Γ (Zeichen, die auf dem Stack stehen können)
• Anfangs-Kellersymbol Z₀ (initial auf dem Stack)
• Übergangsfunktion δ: Abhängig vom aktüllen Zustand, dem gelesenen Eingabezeichen und dem obersten Kellerzeichen
• Akzeptierende Zustände F (oder Akzeptanz durch leeren Keller)

In jedem Schritt kann der Kellerautomat:

1. Das nächste Eingabezeichen lesen (oder ε-Übergang ohne Lesen).
2. Das oberste Kellerzeichen lesen und entfernen (pop).
3. Neue Zeichen auf den Keller schreiben (push).
4. Den Zustand wechseln.

Ein Wort wird akzeptiert, wenn nach dem Lesen der gesamten Eingabe ein Endzustand erreicht ist (oder der Keller leer ist).

Diese Sprache besteht aus Wörtern mit gleich vielen a's und b's, wobei alle a's vor den b's stehen (z. B. „aabb“, „aaabbb“).

Idee:
- Für jedes gelesene 'a': push 'A' auf den Keller
- Für jedes gelesene 'b': pop 'A' vom Keller
- Akzeptieren, wenn Eingabe fertig UND Keller leer

Zustände: {q0, q1, q_akz}
Übergänge:
  (q0, a, Z0) → (q0, A Z0)    // erstes a: A auf Stack
  (q0, a, A)  → (q0, A A)      // weitere a: A stapeln
  (q0, b, A)  → (q1, ε)       // erstes b: A entfernen
  (q1, b, A)  → (q1, ε)       // weitere b: A entfernen
  (q1, ε, Z0) → (q_akz, ε)  // Keller leer: akzeptieren

Die von Kellerautomaten erkannten Sprachen sind die kontextfreien Sprachen (CFL). Sie werden durch kontextfreie Grammatiken beschrieben. Beispiele:

• aⁿbⁿ (gleich viele a's und b's)
• Korrekt geklammerte Ausdrücke: (()), (()())
• Palindrome über {a, b}
• Die Syntax der meisten Programmiersprachen

• DEA/NEA: Erkennt reguläre Sprachen. Kein zusätzlicher Speicher.
• Kellerautomat: Erkennt kontextfreie Sprachen (Obermenge der regulären). Zusätzlicher Stack.
• Turingmaschine: Erkennt alle berechenbaren Sprachen. Unendliches Band mit wahlfreiem Zugriff.

Hierarchie: Reguläre Sprachen ⊂ Kontextfreie Sprachen ⊂ Entscheidbare Sprachen ⊂ Aufzählbare Sprachen

Abitur-Tipp: Im Abitur wird häufig verlangt, einen Kellerautomaten für eine gegebene Sprache zu konstruieren oder zu zeigen, dass eine Sprache nicht regulär ist (und daher einen PDA braucht). Präge dir das Beispiel aⁿbⁿ ein: a's zählen (push), b's abzählen (pop). Die Automaten-Hierarchie (DEA ⊂ PDA ⊂ TM) ist ein Klassiker.