Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Ein endlicher Automat kann nicht erkennen, weil er nicht beliebig weit zählen kann. Gib ihm einen Stapel Papier zum Mitzählen, und plötzlich geht es. Genau das ist der Kellerautomat: ein endlicher Automat mit einem zusätzlichen, unbegrenzten Keller (Stack). Er ist das Maschinenmodell der kontextfreien Sprachen und damit die Grundlage jedes Parsers.
Was du in der Klausur können musst:
Klausur-Tipp: Bei ""-artigen Sprachen ist der Keller dein Zähler. Probiere (ein zu viel) und (falsche Form), um zu sehen, wie der Automat stecken bleibt oder mit nicht-leerem Keller endet.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Ein endlicher Automat kann aⁿ bⁿ nicht erkennen, weil er nicht beliebig weit zählen kann. Gib ihm einen Stapel Papier zum Mitzählen, und plötzlich geht es. Genau das ist der Kellerautomat: ein endlicher Automat mit einem zusätzlichen, unbegrenzten Keller (Stack). Er ist das Maschinenmodell der kontextfreien Sprachen und damit die Grundlage jedes Parsers.
Was du in der Klausur können musst:
aⁿ bⁿ Schritt für Schritt auf dem Keller verarbeitensubsetneq NPDA (anders als beim DFA/NFA)Ein Kellerautomat (PDA, Pushdown-Automat) ist ein endlicher Automat mit einem zusätzlichen unbegrenzten Keller (Stack als Gedächtnis). Er erkennt genau die kontextfreien Sprachen (Chomsky-Typ 2).
Der Keller ist ein LIFO-Speicher (last in, first out): nur das oberste Symbol ist zugänglich.
Der unbegrenzte Keller ist das Gedächtnis, das einem endlichen Automaten fehlt. Damit kann der PDA zählen und vergleichen, was Automaten ohne Keller nicht können.
Ein Kellerautomat ist ein M = (Q, Σ, Γ, δ, q₀, Z₀, F) mit:
| Symbol | Bedeutung |
|---|---|
Q | endliche Zustandsmenge |
Σ | Eingabealphabet |
Γ | Kelleralphabet |
δ | Überführungsfunktion Q × (Σ ∪ \ε\) × Γ → P(Q × Γ^*) |
q₀ | Startzustand |
Z₀ | Kellerbodensymbol |
F | Endzustände |
Ein Schritt liest ein Eingabesymbol oder ε, nimmt das oberste Kellersymbol herunter und legt eine (evtl. leere) Zeichenkette darauf. ε-Übergänge sind erlaubt, das unterscheidet PDAs von DFAs.
Ein PDA akzeptiert ein Wort entweder
F, oderBeide Modi erkennen dieselbe Sprachklasse (die kontextfreien Sprachen).
aⁿ bⁿ auf dem KellerDie Strategie ist Zählen per Keller: jedes a legt ein Symbol A ab, jedes b nimmt eines herunter.
q₀, liest a: lege A auf den Keller (zähle hoch)q₀, liest erstes b mit A oben: nimm A herunter, wechsle nach q₁q₁, liest b mit A oben: nimm A herunter (zähle ab)a wie b)Verfolge es Schritt für Schritt:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Bei endlichen Automaten sind DFA und NFA gleich mächtig. Bei Kellerautomaten ist das anders:
DPDA
subsetneqNPDA. Deterministische Kellerautomaten erkennen nur die deterministisch kontextfreien Sprachen (DCFL), eine echte Teilmenge der kontextfreien Sprachen. Nichtdeterministische PDAs sind echt mächtiger.
Beispiel: die Palindrome \{w w^R mid w ∈ \a,b\^*\} sind kontextfrei, aber kein DPDA erkennt sie, weil er die Mitte des Wortes nicht deterministisch findet. Man braucht Nichtdeterminismus, um zu "raten", wo die Mitte ist.
Kellerautomaten und kontextfreie Grammatiken sind äquivalent: zu jeder kontextfreien Grammatik gibt es einen PDA, der dieselbe Sprache erkennt, und umgekehrt. Deshalb sind PDAs die theoretische Grundlage der Syntaxanalyse (Parser) im Compilerbau.
1. PDA = endlicher Automat + unbegrenzter Keller. Er erkennt genau die kontextfreien Sprachen (Typ 2).
2. 7-Tupel (Q, Σ, Γ, δ, q₀, Z₀, F). δ liest Eingabe oder ε, popt oben, pusht eine Zeichenkette.
3. Nur die Kellerspitze ist zugänglich (LIFO). Push und pop, kein Hineinschauen.
4. Zwei äquivalente Akzeptanz-Modi: Endzustand oder leerer Keller.
5. aⁿ bⁿ per Keller: a legt ab, b nimmt herunter. So zählt der PDA.
6. PDA ≡ kontextfreie Grammatik. Anwendung: Parser, Syntaxanalyse, BNF/EBNF.
1. DPDA und NPDA gleichsetzen. Anders als beim DFA/NFA ist der nichtdeterministische Kellerautomat echt mächtiger. DPDA subsetneq NPDA.
2. Mehrere Keller annehmen. Ein PDA hat genau einen Keller. Zwei Keller hätten bereits die Mächtigkeit einer Turing-Maschine.
3. In den Keller hineinschauen. Nur das oberste Symbol ist lesbar. Tiefer liegende Symbole erreicht man erst, wenn die oberen abgebaut sind.
4. aⁿ bⁿ cⁿ für kontextfrei halten. Diese Sprache ist nicht kontextfrei (ein Keller reicht für eine Zählung, nicht für zwei unabhängige Vergleiche). Das zeigt das Pumping-Lemma für kontextfreie Sprachen.
5. Akzeptanz-Modus vermischen. Sage klar "durch Endzustand" oder "durch leeren Keller", nicht beides gleichzeitig im selben Argument.
6. ε-Übergänge übersehen. Ein PDA darf Schritte ohne Lesen eines Eingabesymbols machen (Eingabe ε), z.B. um am Ende den Keller zu leeren.
Wähle ein Wort und gehe Schritt für Schritt. Achte darauf, wie der Keller bei den a wächst und bei den b wieder abgebaut wird. Akzeptiert wird nur, wenn am Ende Eingabe und Keller gleichzeitig leer sind.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "aⁿ bⁿ"-artigen Sprachen ist der Keller dein Zähler. Probiere aabbb (ein b zu viel) und abab (falsche Form), um zu sehen, wie der Automat stecken bleibt oder mit nicht-leerem Keller endet.
Klausurfragen mit Lösungen (6)
Antwort: Er hat einen zusätzlichen, unbegrenzten Keller (Stack) als Gedächtnis
Erklärung: Der Kellerautomat ist ein endlicher Automat mit einem unbegrenzten Keller. Dieses Zusatzgedächtnis erlaubt das Zählen und Vergleichen, das einem endlichen Automaten fehlt.
Antwort: die kontextfreien Sprachen (Typ 2)
Erklärung: Kellerautomaten erkennen genau die kontextfreien Sprachen (Chomsky-Typ 2). Reguläre Sprachen schaffen endliche Automaten, Typ 0 die Turing-Maschine.
Zuordnungen:
Erklärung: Die Chomsky-Hierarchie: Typ 3 = endlicher Automat, Typ 2 = Kellerautomat, Typ 1 = linear beschränkte TM, Typ 0 = allgemeine Turing-Maschine. Je höher die Modellstärke, desto mehr Gedächtnis.
Typ: Zuordnung
Antwort: ein Symbol wird auf den Keller gelegt (push)
Erklärung: Jedes `a` legt ein Symbol auf den Keller (push), so wird die Anzahl der `a` gezählt. Beim späteren Lesen der `b` wird für jedes `b` ein Symbol heruntergenommen (pop).
Antwort: Falsch
Erklärung: Falsch. Anders als bei DFA und NFA gilt hier DPDA `subsetneq` NPDA: nichtdeterministische Kellerautomaten sind echt mächtiger. Z.B. die Palindrome `\w w^R\` erkennt kein deterministischer PDA.
Typ: Wahr/Falsch
Antwort: weil ein einzelner Keller nur eine Zählung verwalten kann, nicht zwei unabhängige Vergleiche
Erklärung: Mit einem Keller kann man `a` gegen `b` zählen, danach ist der Keller leer und die Information über `n` verloren, um auch noch die `c` zu prüfen. Zwei unabhängige Zählungen schafft ein PDA nicht. Das beweist das Pumping-Lemma für kontextfreie Sprachen.
Klausurfragen mit Lösungen (6)
Antwort: `(Q, Σ, Γ, δ, q₀, Z₀, F)`
Erklärung: Der PDA ist ein 7-Tupel `(Q, Σ, Γ, δ, q₀, Z₀, F)` mit Zuständen, Eingabe- und Kelleralphabet, Überführungsfunktion, Start, Kellerboden und Endzuständen. Das 5-Tupel ist ein DFA, das 4-Tupel eine Grammatik.
Antwort: nur am obersten Element: lesen, herunternehmen (pop) und drauflegen (push)
Erklärung: Der Keller ist ein LIFO-Speicher: nur die Spitze ist zugänglich. Man liest das oberste Symbol, nimmt es herunter (pop) und legt eine Zeichenkette darauf (push). Tiefere Symbole sind nicht direkt erreichbar.
Antwort: durch Endzustand oder durch leeren Keller (beide äquivalent)
Erklärung: Ein PDA akzeptiert durch Erreichen eines Endzustands ODER durch vollständiges Leeren des Kellers. Beide Modi erkennen exakt dieselbe Sprachklasse (die kontextfreien Sprachen).
Lösungen pro Lücke:
Erklärung: PDA = kontextfreie Sprachen. NPDA ist echt mächtiger als DPDA. Zwei Keller ergeben bereits ein turingmächtiges Modell (zwei Stacks simulieren ein Band).
Typ: Lückentext
Antwort: `Z A A` (zwei `A` über dem Boden)
Erklärung: Jedes `a` legt ein `A` auf den Keller. Nach `aa` liegen zwei `A` über dem Bodensymbol `Z`: also `Z A A`. Die beiden folgenden `b` nehmen die `A` wieder herunter.
Antwort: `\{w w^R mid w ∈ \a,b\^*\}` (Palindrome gerader Länge)
Erklärung: Palindrome `w w^R` sind kontextfrei, aber kein DPDA erkennt sie, weil er die Mitte des Wortes nicht deterministisch bestimmen kann. Er muss nichtdeterministisch 'raten', wo die zweite Hälfte beginnt. `aⁿ bⁿ` dagegen ist sogar deterministisch kontextfrei.