CNF znamená Chomského normální formu. CFG (bezkontextová gramatika) je v CNF (Chomského normální forma), pokud všechna produkční pravidla splňují jednu z následujících podmínek:

• Začněte generovat symbol ε. Například A → ε.
• Neterminál generující dva neterminály. Například S → AB.
• Neterminál generující terminál. Například S → a.

Například:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

Produkční pravidla gramatiky G1 splňují pravidla specifikovaná pro CNF, takže gramatika G1 je v CNF. Produkční pravidlo gramatiky G2 však nesplňuje pravidla specifikovaná pro CNF, protože S → aZ obsahuje terminál následovaný neterminálem. Takže gramatika G2 není v CNF.

textový wrapper css

Kroky pro konverzi CFG na CNF

Krok 1: Odstraňte startovací symbol z RHS. Pokud je počáteční symbol T na pravé straně jakékoli produkce, vytvořte novou produkci jako:

 S1 → S 

Kde S1 je nový startovací symbol.

Krok 2: V gramatice odstraňte null, unit a neužitečné produkce. Můžete se podívat na Zjednodušení CFG .

Krok 3: Odstraňte terminály z RHS výroby, pokud existují s jinými neterminály nebo terminály. Například produkci S → aA lze rozložit jako:

 S → RA R → a 

Krok 4: Odstraňte RHS pomocí více než dvou neterminálů. Například S → ASB lze rozložit jako:

zkuste chytit v Javě

 S → RS R → AS 

Příklad:

Převeďte daný CFG na CNF. Zvažte danou gramatiku G1:

 S → a | aA | B A → aBB | ε B → Aa | b 

Řešení:

Krok 1: Vytvoříme novou produkci S1 → S, protože na pravé straně se objeví startovací symbol S. Gramatika bude:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Krok 2: Protože gramatika G1 obsahuje A → ε nulovou produkci, její odstranění z gramatiky vede:

stáhnout videa z youtube vlc

 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Nyní, protože gramatika G1 obsahuje produkci jednotek S → B, její výtěžek odstranění:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

Odstraňte také produkci jednotek S1 → S, její odstranění z gramatiky vede:

cast sql

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Krok 3: Ve výrobním pravidle S0 → aA | Aa, S → aA | Aa, A → aBB a B → Aa, svorka a existuje na RHS s nekoncovkami. Terminál a tedy nahradíme X:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Krok 4: V produkčním pravidle A → XBB má RHS více než dva symboly, čímž se z výtěžku gramatiky odstraní:

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Pro danou gramatiku je to tedy požadovaný CNF.