5. Kellerautomat (PDA) und Kontextfreie Grammatik (CFG)

Thema 5: Kellerautomat (PDA) und Kontextfreie Grammatik (CFG)

---

✅ 1. Kellerautomat (PDA - Pushdown Automaton)

📌 Definition:

• Ein Kellerautomat (PDA) ist ein endlicher Automat mit einem zusätzlichen Stack (Keller).

• Er kann nicht nur den aktuellen Zustand und das Eingabesymbol verwenden, sondern auch das oberste Symbol des Stacks berücksichtigen.

🗂️ Bestandteile:

• Q: Menge der Zustände

• Σ: Eingabealphabet

• Γ: Stackalphabet

• δ: Übergangsfunktion δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × (Γ ∪ {ε}))

• q₀: Startzustand

• Z₀: Startsymbol des Stacks

• F: Menge der Endzustände

⚙️ Arbeitsweise:

1. Lesen eines Eingabesymbols (oder ε-Übergang ohne Lesen).

2. Stackoperationen:

   • Push: Symbol auf den Stack legen.

   • Pop: Symbol vom Stack entfernen.

   • Keine Änderung: Stack bleibt unverändert.

3. Übergang zu einem neuen Zustand.

📊 **Beispiel

---

✅ 2. Kontextfreie Grammatik (CFG)

📌 Definition:

• Eine Kontextfreie Grammatik (CFG) definiert formale Sprachen mithilfe von Produktionsregeln.

• Form einer Produktionsregel: A → α

  • A: Ein Nichtterminalsymbol.

  • α: Eine beliebige Kombination aus Terminal- und Nichtterminalsymbolen.

🗂️ Bestandteile:

• V: Menge der Variablen (Nichtterminalsymbole)

• Σ: Menge der Terminalsymbole

• R: Menge der Produktionsregeln

• S: Startsymbol

🚀 **Beispiel

---

🔗 3. Zusammenhang zwischen PDA und CFG

• Wichtige Erkenntnis:

  • Jede kontextfreie Sprache (CFL) kann von einem Kellerautomaten (PDA) erkannt werden.

  • Jeder PDA kann in eine CFG umgewandelt werden und umgekehrt.

⚡ Umwandlung PDA → CFG:

1. Erstelle Regeln, die die Stack-Operationen des PDA simulieren.

2. Push-Operation = Hinzufügen von Symbolen in der Grammatik.

3. Pop-Operation = Abbau der Rekursion in der Grammatik.

⚡ Umwandlung CFG → PDA:

1. PDA simuliert die Ableitungsregeln der CFG.

2. Der Stack dient dazu, Nichtterminalsymbole zu speichern.

3. PDA „erweitert“ die Grammatikregeln, bis das Eingabewort vollständig verarbeitet ist.

---

📝 4. Typische Prüfungsaufgaben

• Ableitung von Wörtern mit einer CFG:

  • Beispiel: Für S → aSb | ε, leite das Wort aaabbb ab:

    S → aSb
      → aaSbb
      → aaaSbbb
      → aaabbb
    

• Konstruieren eines PDA:

  • Aufgabe: Erstelle einen PDA für L = {ww^R | w ∈ {0,1}*} (palindromische Wörter).

  • Lösung:

    • Push-Phase: Symbole von w auf den Stack legen.

    • Pop-Phase: Symbole mit w^R vergleichen.

• Umwandeln von PDA in CFG:

  • Definiere Regeln, die den Stack-Zustand beschreiben.

---

🎯 5. Anwendungsgebiete

• Compilerbau: Syntaxanalyse von Programmiersprachen.

• Formale Sprachen: Definition von Programmiersprachen und Protokollen.

• Spracherkennung: Verarbeitung natürlicher Sprache.