| Typ | Konzept |
|---|---|
| Quellen | Quelle - Automatentheorie Zusammenfassung |
| Erstellt | 2026-09-24 |
| Aktualisiert | 2026-09-26 |
| Tags | theoretische-informatik, automatentheorie, compilerbau |
Ein endlicher Automat mit einem zusätzlichen, unbeschränkten Stapelspeicher (Keller, Stack). Er erkennt genau die kontextfreien Sprachen und ist das Maschinenmodell hinter jedem Parser.
Aufbau
K = (Σ, S, Γ, δ, s₀, ⊥, F) mit Eingabealphabet Σ, Zuständen S, Kelleralphabet Γ, Überführung δ, Startzustand s₀, Kellerbodensymbol ⊥ und Endzuständen F (Quelle - Automatentheorie Zusammenfassung).
- Nur das oberste Kellersymbol ist lesbar. Es wird bei jedem Übergang durch ein Wort ersetzt (auch durch ε, dann ist es gelöscht).
- ε-Übergänge lesen kein Eingabesymbol und verändern nur den Keller.
- Akzeptanz per Endzustand und per leerem Keller ist gleichwertig.
Mächtigkeit
- PDA = kontextfreie Sprachen: Zu jeder kontextfreien Grammatik gibt es einen Kellerautomaten und umgekehrt → Kontextfreie Sprache. Ein Parser-Generator konstruiert ihn automatisch und kann dabei den Ableitungsbaum mitliefern.
- Der Keller erlaubt Zählen, was dem endlichen Automaten fehlt. Beispiel aⁿbⁿ: Für jedes a wird ein Symbol gekellert, für jedes b eines entnommen. Ist der Keller am Ende leer, wird akzeptiert.
- Mit zwei Kellern kann ein Kellerautomat jede Turingmaschine simulieren.
- Ein einziger Keller reicht nicht für aⁿbⁿcⁿ: Nach dem Abgleich der b's ist die Anzahl der a's „verbraucht“. Diese Sprache ist kontextsensitiv → Chomsky-Hierarchie.
Deterministische Kellerautomaten (DPDA)
- DPDA ⊊ PDA: Anders als bei endlichen Automaten lässt sich Nichtdeterminismus hier nicht eliminieren (Quelle - Automatentheorie Zusammenfassung).
- Dafür prüfen DPDA die Syntax in linearer Zeit. Deshalb nutzt der Compilerbau deterministisch kontextfreie Grammatiken (LR(k)).
- Jede reguläre Sprache ist deterministisch kontextfrei.
- DPDA-Sprachen sind abgeschlossen unter Komplement und unter Durchschnitt mit einer regulären Sprache, nicht aber unter Vereinigung, Durchschnitt, Konkatenation und Kleene-Stern.
- Beispiel K₂ (S. 31) für L₂ = {w ∈ {a,b}* | Anzahl a = Anzahl b}: Der Keller merkt sich den „Überschuss“ an a's oder b's. Jedes Gegensymbol baut ein Symbol ab. Ist der Keller wieder leer (⊥), beginnt es von vorn. Über ε und ⊥ geht K₂ in den Endzustand s_f. Die Konfigurationsfolge für abbaba endet in (s_f, ε, ε).
Einordnung (Claude)
Die Quelle führt die Äquivalenz zweier DPDA als offene Frage („?“). Sie ist seit Sénizergues (1997) als entscheidbar bewiesen, für allgemeine PDA bleibt sie unentscheidbar (siehe Chomsky-Hierarchie). Praktisch steckt der Kellerautomat in jedem Parser, auch in denen, die Markdown-Dateien wie die dieses Wikis einlesen.
Anwendungen
- Syntaxanalyse im Compilerbau (Parser)
- Syntaxanalyse in der Bildanalyse: Top-down- und Bottom-up-Parsing von Bildgrammatiken mit Backtracking → Wissensbasierte Bildanalyse
Verwandt
- Kontextfreie Sprache – die Sprachklasse, die er erkennt
- Endlicher Automat – Kellerautomat ohne Keller
- Turingmaschine – statt Keller ein frei beschreibbares Band
- Chomsky-Hierarchie – Einordnung als Typ-2-Automat; Determinismus-Vergleich
- Wissensbasierte Bildanalyse – Parsing von Bildgrammatiken
- HP 48G – Taschenrechner mit umgekehrter polnischer Notation, rechnet auf einem Stapel