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.