CNF je kratica za Chomsky normal form. CFG (gramatika bez konteksta) je u CNF (Chomsky normalan oblik) ako sva pravila proizvodnje zadovoljavaju jedan od sljedećih uvjeta:

• Započnite generiranje ε. Na primjer, A → ε.
• Ne-terminal koji generira dva ne-terminala. Na primjer, S → AB.
• Neterminal koji generira terminal. Na primjer, S → a.

Na primjer:

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

Pravila proizvodnje Gramatike G1 zadovoljavaju pravila navedena za CNF, tako da je gramatika G1 u CNF-u. Međutim, proizvodno pravilo Gramatike G2 ne zadovoljava pravila navedena za CNF jer S → aZ sadrži terminal iza kojeg slijedi ne-terminal. Dakle, gramatika G2 nije u CNF.

lista od lateksa

Koraci za pretvaranje CFG u CNF

Korak 1: Uklonite simbol starta s RHS-a. Ako je simbol početka T na desnoj strani bilo koje proizvodnje, stvorite novu proizvodnju kao:

 S1 → S 

Gdje je S1 novi startni simbol.

Korak 2: U gramatici uklonite nulte, jedinice i beskorisne produkcije. Možete se pozvati na Pojednostavljenje CFG-a.

instanceof u Javi

Korak 3: Uklonite terminale iz RHS-a proizvodnje ako postoje s drugim ne-terminalima ili terminalima. Na primjer, proizvodnja S → aA može se rastaviti kao:

 S → RA R → a 

Korak 4: Uklonite RHS s više od dva ne-terminala. Na primjer, S → ASB se može rastaviti kao:

 S → RS R → AS 

Primjer:

Pretvorite dani CFG u CNF. Razmotrite datu gramatiku G1:

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

Riješenje:

Korak 1: Stvorit ćemo novu proizvodnju S1 → S, budući da se simbol početka S pojavljuje na desnoj strani. Gramatika će biti:

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

Korak 2: Kako gramatika G1 sadrži A → ε nultu proizvodnju, njezino uklanjanje iz gramatike daje:

usporedba java niza

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

Sada, kako gramatika G1 sadrži jediničnu proizvodnju S → B, njezino uklanjanje daje:

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

Također uklonite jediničnu proizvodnju S1 → S, njezino uklanjanje iz gramatike daje:

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

Korak 3: U proizvodnom pravilu S0 → aA | Aa, S → aA | Aa, A → aBB i B → Aa, terminal a postoji na RHS s ne-terminalima. Dakle, zamijenit ćemo terminal a s X:

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

Korak 4: U proizvodnom pravilu A → XBB, RHS ima više od dva simbola, što ga uklanja iz gramatičkog prinosa:

pretvaranje int u dvostruku Javu

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

Dakle, za datu gramatiku, ovo je tražena CNF.