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