6. Chomsky Normalform

Thema 7: Chomsky-Normalform (CNF)

📌 Definition:

Eine Grammatik ist in Chomsky-Normalform (CNF), wenn jede Produktionsregel eine der folgenden Formen hat:

1. Binarregel:

   A→BCA \rightarrow BCA→BC - A, B, C: Nichtterminalsymbole (B, C ≠ Startsymbol) - Keine Terminals auf der rechten Seite. 2. Terminalregel:

   A→aA \rightarrow aA→a - a: Terminalsymbol (z.B. a, b, c) 3. Leere Produktion (optional):

   S→εS \rightarrow \varepsilonS→ε - Nur erlaubt, wenn S das Startsymbol ist.

---

📝 Schritte zur Umwandlung in CNF:

1. Eliminiere ε-Produktionen:

   • Entferne Regeln der Form A → ε, außer wenn A das Startsymbol ist.

   • Eliminiere unit-Productions:

   • Regeln der Form A → B werden aufgelöst, indem A die Regeln von B übernimmt.

   • Eliminiere unnötige Symbole:

   • Entferne Nichtterminale, die nicht zur Erzeugung von Terminals führen.

   • Reduziere längere Produktionen:

   • Z.B. A → BCD wird umgewandelt in:

     css

     KopierenBearbeiten

     A → BX X → CD

2. Ersetze Terminals in Kombinationen:

   • Z.B. A → aB wird:

     css

     KopierenBearbeiten

     A → XB X → a

---

📊 2. CYK-Algorithmus (Cocke-Younger-Kasami)

📌 Zweck:

Prüft, ob ein Wort von einer Grammatik in CNF erzeugt werden kann.

📝 Voraussetzungen:

• Die Grammatik muss in CNF vorliegen.
• Das Wort ω wird von unten nach oben in einer Tabelle überprüft.

---

⚙️ Ablauf des CYK-Algorithmus:

1. Initialisierung (Basis):

   • Erstelle eine Dreiecksmatrix.
   • Fülle die unterste Zeile mit den Nichtterminals, die das jeweilige Terminal ableiten.

   • Rekursive Berechnung:

   • Für jedes Teilwort (länger als 1) prüfe, welche Kombination von Nichtterminals möglich ist.

   • Nutze die Produktionsregeln der Grammatik.

   • Akzeptanzprüfung:

   • Das Wort wird akzeptiert, wenn das Startsymbol (S) in der oberen Zelle der Matrix steht.

---

🔍 3. Typische Prüfungsaufgaben

✅ Aufgabe 1: Grammatik in CNF umwandeln

• Beispiel:

  S → FF | FG F → aHa G → bb H → bHb | ε

• Vorgehen:

  1. Ersetze Terminals: aHa → XHY mit X → a, Y → a
  2. Reduziere lange Produktionen: S → FX mit X → FG
  3. Eliminiere ε-Produktionen: H → bHb | ε wird angepasst.

---

✅ Aufgabe 2: CYK für cccabb

• Erstelle eine Tabelle für das Wort cccabb.
• Prüfe jede Kombination mit den Produktionsregeln.
• Akzeptanz: Falls S in der oberen Zelle → Wort gehört zur Sprache.

---

✅ Aufgabe 3: CYK für ababacc

• Gleiche Vorgehensweise wie bei Aufgabe 2.
• Grammatik ist bereits in CNF → direkt anwenden.

---

🎯 4. Zusammenfassung

• Chomsky-Normalform: Grammatik in einfache Binärform umwandeln.
• CYK-Algorithmus: Matrixverfahren, um die Ableitbarkeit eines Wortes zu prüfen.
• Prüfung: Immer kontrollieren, ob das Startsymbol S in der letzten Matrixzelle steht.