CNF steht für Chomsky-Normalform. Eine CFG (kontextfreie Grammatik) liegt in CNF (Chomsky-Normalform) vor, wenn alle Produktionsregeln eine der folgenden Bedingungen erfüllen:
- Starten Sie die Symbolgenerierung von ε. Zum Beispiel A → ε.
- Ein Nicht-Terminal, das zwei Nicht-Terminals erzeugt. Zum Beispiel S → AB.
- Ein Nicht-Terminal, das ein Terminal generiert. Zum Beispiel S → a.
Zum Beispiel:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} Die Produktionsregeln der Grammatik G1 erfüllen die für CNF angegebenen Regeln, sodass die Grammatik G1 in CNF enthalten ist. Die Produktionsregel der Grammatik G2 erfüllt jedoch nicht die für CNF angegebenen Regeln, da S → aZ Terminal gefolgt von Nicht-Terminal enthält. Die Grammatik G2 ist also nicht in CNF enthalten.
Kapselung Java
Schritte zur Konvertierung von CFG in CNF
Schritt 1: Entfernen Sie das Startsymbol aus der rechten Seite. Wenn sich das Startsymbol T auf der rechten Seite einer Produktion befindet, erstellen Sie eine neue Produktion wie folgt:
S1 → S
Wobei S1 das neue Startsymbol ist.
Schritt 2: Entfernen Sie in der Grammatik die Null-, Einheits- und nutzlosen Produktionen. Sie können sich auf die Vereinfachung von CFG beziehen.
Linux-Befehle
Schritt 3: Eliminieren Sie Terminals aus der RHS der Produktion, wenn sie zusammen mit anderen Nicht-Terminals oder Terminals vorhanden sind. Beispielsweise kann die Produktion S → aA wie folgt zerlegt werden:
S → RA R → a
Schritt 4: Beseitigen Sie RHS mit mehr als zwei Nicht-Terminals. S → ASB kann beispielsweise wie folgt zerlegt werden:
S → RS R → AS
Beispiel:
Konvertieren Sie das angegebene CFG in CNF. Betrachten Sie die gegebene Grammatik G1:
S → a | aA | B A → aBB | ε B → Aa | b
Lösung:
Schritt 1: Wir werden eine neue Produktion S1 → S erstellen, da das Startsymbol S auf der rechten Seite erscheint. Die Grammatik wird sein:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
Schritt 2: Da die Grammatik G1 die Nullproduktion A → ε enthält, ergibt ihre Entfernung aus der Grammatik:
string.format in Java
S1 → S S → a | aA | B A → aBB B → Aa | b | a
Da nun die Grammatik G1 die Einheitsproduktion S → B enthält, ergibt sich aus ihrer Entfernung:
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
Entfernen Sie auch die Einheitsproduktion S1 → S, ihre Entfernung aus der Grammatik ergibt:
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
Schritt 3: In der Produktionsregel S0 → aA | Aa, S → aA | Aa, A → aBB und B → Aa, Terminal a existiert auf RHS mit Nicht-Terminals. Also ersetzen wir Terminal a durch X:
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
Schritt 4: In der Produktionsregel A → XBB hat RHS mehr als zwei Symbole, wodurch es aus der Grammatikausbeute entfernt wird:
Bilderspiele für Android
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
Daher ist dies für die gegebene Grammatik die erforderliche CNF.