Chomsky Normalform

Ein CFG liegt in Chomsky-Normalform vor, wenn die Produktionen in den folgenden Formen vorliegen:

  • A → a
  • A → BC
  • S → ε

wobei A, B und C keine Terminals sind und a ist Terminal.

Algorithmus zur Umwandlung in Chomsky-Normalform -

Step 1 - Wenn das Startsymbol S tritt auf einer rechten Seite auf, erstellen Sie ein neues Startsymbol S’ und eine neue Produktion S’→ S.

Step 2- Entfernen Sie Nullproduktionen. (Verwenden des zuvor beschriebenen Algorithmus zum Entfernen der Nullproduktion)

Step 3- Geräteproduktionen entfernen. (Verwenden des zuvor beschriebenen Algorithmus zum Entfernen der Einheitenproduktion)

Step 4 - Ersetzen Sie jede Produktion A → B1…Bn wo n > 2 mit A → B1C wo C → B2 …Bn. Wiederholen Sie diesen Schritt für alle Produktionen mit zwei oder mehr Symbolen auf der rechten Seite.

Step 5 - Wenn die rechte Seite einer Produktion in der Form ist A → aB wo a ein Terminal ist und A, B Sind nicht-terminal, dann wird die Produktion durch ersetzt A → XB und X → a. Wiederholen Sie diesen Schritt für jede Produktion in der FormA → aB.

Problem

Konvertieren Sie das folgende CFG in CNF

S → ASA | aB, A → B | S, B → b | ε

Lösung

(1) Schon seit S erscheint in RHS, fügen wir einen neuen Status hinzu S0 und S0→S wird dem Produktionsset hinzugefügt und es wird -

S 0 → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Jetzt werden wir die Nullproduktionen entfernen -

B → ∈ und A → ∈

Nach dem Entfernen von B → ε wird der Produktionssatz zu -

S 0 → S, S → ASA | aB | a, A → B | S | ∈, B → b

Nach dem Entfernen von A → ∈ wird der Produktionssatz zu -

S 0 → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Jetzt werden wir die Einheitsproduktionen entfernen.

Nach dem Entfernen von S → S wird der Produktionssatz zu -

S 0 → S, S → ASA | aB | a | AS | SA, A → B | S, B → b

Nach dem Entfernen von S 0 → S wird der Produktionssatz zu -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

Nach dem Entfernen von A → B wird der Produktionssatz zu -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | b

B → b

Nach dem Entfernen von A → S wird der Produktionssatz zu -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → b | ASA | aB | a | AS | SA, B → b

(4) Jetzt werden wir mehr als zwei Variablen in der RHS herausfinden

Hier verletzt S 0 → ASA, S → ASA, A → ASA zwei Nicht-Terminals in RHS

Daher werden wir Schritt 4 und Schritt 5 anwenden, um den folgenden endgültigen Produktionssatz zu erhalten, der in CNF vorliegt -

S 0 → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Wir müssen die Produktionen S 0 → aB, S → aB, A → aB ändern

Und das endgültige Produktionsset wird -

S 0 → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a