CNF tarkoittaa Chomskyn normaalimuotoa. CFG (kontekstivapaa kielioppi) on CNF:ssä (Chomskyn normaalimuodossa), jos kaikki tuotantosäännöt täyttävät yhden seuraavista ehdoista:

• Aloita symbolin luominen ε Esimerkiksi A → ε.
• Ei-päätelaite, joka tuottaa kaksi ei-päätelaitetta. Esimerkiksi S → AB.
• Ei-päätelaite, joka tuottaa päätelaitteen. Esimerkiksi S → a.

Esimerkiksi:

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

Kieliopin G1 tuotantosäännöt täyttävät CNF:lle määritellyt säännöt, joten kielioppi G1 on CNF:ssä. Grammar G2:n tuotantosääntö ei kuitenkaan täytä CNF:lle määritettyjä sääntöjä, koska S → aZ sisältää terminaalin, jota seuraa ei-pääte. Joten kielioppi G2 ei ole CNF:ssä.

linkitetty lista javassa

Vaiheet CFG:n muuntamiseksi CNF:ksi

Vaihe 1: Poista aloitussymboli RHS:stä. Jos aloitussymboli T on tuotannon oikealla puolella, luo uusi tuotanto seuraavasti:

 S1 → S 

Missä S1 on uusi aloitussymboli.

Vaihe 2: Poista kielioppista null-, unit- ja hyödyttömät tuotannot. Voit katsoa CFG:n yksinkertaistamista.

Vaihe 3: Poista päätteet tuotannon RHS:stä, jos niitä on muiden ei-päätteiden tai päätteiden kanssa. Esimerkiksi tuotanto S → aA voidaan jakaa seuraavasti:

kuinka poistaa ensimmäinen merkki excelissä

 S → RA R → a 

Vaihe 4: Poista RHS useammalla kuin kahdella ei-päätteellä. Esimerkiksi S → ASB voidaan jakaa seuraavasti:

 S → RS R → AS 

Esimerkki:

Muunna annettu CFG CNF:ksi. Harkitse annettua kielioppia G1:

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

Ratkaisu:

Vaihe 1: Luomme uuden tuotannon S1 → S, koska aloitussymboli S näkyy oikealla puolella. Kielioppi tulee olemaan:

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

Vaihe 2: Koska kielioppi G1 sisältää A → ε nolla -tuotannon, sen poistaminen kielioppista tuottaa:

java null tarkistus

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

Nyt, kun kielioppi G1 sisältää yksikkötuotannon S → B, sen poistotuotto:

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

Poista myös yksikkötuotanto S1 → S, sen poistaminen kielioppista antaa:

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

Vaihe 3: Tuotantosäännössä S0 → aA | Aa, S → aA | Aa, A → aBB ja B → Aa, pääte a on olemassa RHS:ssä ei-päätteillä. Joten korvaamme terminaalin a X:llä:

voiko abstraktilla luokalla olla konstruktori

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

Vaihe 4: Tuotantosäännössä A → XBB RHS:ssä on enemmän kuin kaksi symbolia, mikä poistaa sen kieliopin tuotosta:

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

Siksi annetulle kieliopille tämä on vaadittu CNF.