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.