Grammatiktransformationen: Chomsky-Normalform & Bereinigung

Beseitigung unzugänglicher Symbole

Algorithmus zur Entfernung unzugänglicher Symbole

Um unzugängliche Symbole aus einer Grammatik G = (N, T, P, S) zu entfernen und eine neue Grammatik G' = (N', T', P', S) zu erstellen, gehen Sie wie folgt vor:

1. Initialisierung

   Initialisieren Sie die Menge der erreichbaren Nichtterminale N' (z.B. mit dem Startsymbol S) und die Menge der erreichbaren Produktionen P' als leer.

2. Iteration zur Ermittlung erreichbarer Symbole

   Wiederholen Sie die folgenden Schritte, bis sich N' nicht mehr ändert:

   • Für jedes Nichtterminal A ∈ N', wenn A → w eine Produktion in P ist, dann:
     1. Fügen Sie A → w zu P' hinzu.
     2. Für jedes Nichtterminal B, das in w vorkommt, fügen Sie B zu N' hinzu.
     3. Für jedes Terminal a, das in w vorkommt, werden keine weiteren Regeln zu P' hinzugefügt, da Terminals nicht expandieren.

Beseitigung von Epsilon-Regeln (ε-Regeln)

Algorithmus zur Entfernung von ε-Regeln

Gegeben sei eine Grammatik G = (N, T, P, S). Wenn ε ∈ L(G) (d.h., das leere Wort wird von S erzeugt), darf die Produktion S → ε nicht gelöscht werden. Alle anderen ε-Regeln können beseitigt werden.

Definition: Nullable Symbole

Ein Nichtterminal A ∈ N ist nullable (oder anfechtbar), wenn A ⇒* ε (d.h., A kann das leere Wort erzeugen).

1. Berechnung aller nullable Symbole

   Bestimmen Sie die Menge N_ε aller nullable Nichtterminale:

   1. Initialisieren Sie N_ε mit allen Nichtterminalen A, für die eine Produktion A → ε ∈ P existiert.
   2. Wiederholen Sie: Fügen Sie zu N_ε alle Nichtterminale B hinzu, für die eine Produktion B → w ∈ P existiert, wobei alle Symbole in w bereits in N_ε enthalten sind (d.h., w ⇒* ε). Fahren Sie fort, bis sich N_ε nicht mehr ändert.

2. Modifikation der Produktionen

   Wir modifizieren die Regeln in P wie folgt, um P' zu erstellen:

   Für jede Produktion B → x₁x₂...x_n ∈ P (wobei B ≠ S, falls S → ε beibehalten werden soll), fügen wir zu P' alle Produktionen B → y₁y₂...y_n hinzu. Dabei gilt: y_i = x_i, wenn x_i nicht nullable ist. Wenn x_i nullable ist, kann y_i entweder x_i oder ε sein. Dies gilt für alle möglichen Kombinationen der nullable Symbole, die durch ε ersetzt werden können, solange die resultierende rechte Seite nicht leer ist.

   Hinweis: Wenn ε ∈ L(G), fügen Sie am Ende die Regel S → ε zu P' hinzu, falls sie nicht bereits durch die Modifikation entstanden ist und S selbst nullable ist.

Beseitigung von Einheitsregeln

Algorithmus zur Entfernung von Einheitsregeln

Definition: Eine Einheitsregel ist eine Produktion der Form A → B, wobei A, B ∈ N (Nichtterminale). Für jedes Nichtterminal A ∈ N definieren wir Unit(A) = {B ∈ N | A ⇒* B nur mit Einheitsregeln}.

1. Initialisierung

   Initialisieren Sie die neue Menge von Produktionen P' mit allen Produktionen aus P: P' = P.

2. Berechnung von Unit(A)

   Für jedes Nichtterminal A ∈ N, berechnen Sie die Menge Unit(A).

3. Hinzufügen neuer Produktionen

   Für jedes Nichtterminal A ∈ N:

   • Für jedes B ∈ Unit(A):
     • Für jede Produktion B → w ∈ P, bei der w kein einzelnes Nichtterminal ist (d.h., w ist keine Einheitsregel):
       1. Fügen Sie die Produktion A → w zu P' hinzu.

4. Entfernen von Einheitsregeln

   Entfernen Sie alle Einheitsregeln (Produktionen der Form X → Y, wobei X, Y ∈ N) aus P'.

Reihenfolge der Grammatiktransformationen

Um eine Grammatik in die Chomsky-Normalform zu überführen, ist es wichtig, die Transformationen in einer bestimmten Reihenfolge anzuwenden:

1. Beseitigung von Epsilon-Regeln (siehe oben)
2. Beseitigung von Einheitsregeln (siehe oben)
3. Beseitigung unzugänglicher Symbole (siehe oben)
4. (Optional, aber empfohlen: Beseitigung nutzloser Symbole)

Chomsky-Normalform (CNF)

Definition der Chomsky-Normalform

Eine Grammatik befindet sich in Chomsky-Normalform (CNF), wenn alle Produktionen eine der folgenden Formen haben:

• A → a (wobei A ein Nichtterminal und a ein Terminal ist)
• A → BC (wobei A, B, C Nichtterminale sind)

Transformation in die Chomsky-Normalform

Wie transformiert man eine beliebige Grammatik G (die bereits von ε-Regeln, Einheitsregeln, nutzlosen Symbolen und unzugänglichen Symbolen bereinigt wurde) in eine Grammatik G' in CNF?

Für jede Produktion A → w in G (wenn ε ∈ L(G), wird S → ε separat behandelt und am Ende wieder hinzugefügt):

1. Behandlung von Terminalen in rechten Seiten mit Länge > 1

   Wenn |w| = 1:

   • Wenn w ein Terminal ist (z.B. A → a), ist die Regel bereits in CNF.

   Wenn |w| > 1 und w = x₁x₂...x_n:

   • Wenn x_i ein Nichtterminal ist, bleibt es unverändert.
   • Wenn x_i ein Terminal ist, ersetzen Sie es durch ein neues Nichtterminal X_a und fügen Sie die Regel X_a → x_i zu P' hinzu.

2. Binarisierung der Regeln

   Wenn die rechte Seite einer Produktion mehr als zwei Symbole enthält (z.B. A → B₁B₂...B_n mit n > 2), führen Sie neue Nichtterminale ein, um die Regel zu binarisieren. Zum Beispiel wird A → B₁B₂B₃ zu den Regeln A → B₁D₁ und D₁ → B₂B₃.

   Allgemein: A → B₁B₂...B_n wird zu A → B₁D₁, D₁ → B₂D₂, ..., D_n-2 → B_n-1B_n.

3. Behandlung des leeren Wortes

   Am Ende, wenn ε ∈ L(G), fügen Sie die Regel S → ε zu P' hinzu.