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.