CNF står for Chomsky normal form. En CFG (kontekstfri grammatikk) er i CNF (Chomsky normal form) hvis alle produksjonsregler tilfredsstiller en av følgende betingelser:

• Start symbolgenerering ε For eksempel A → ε.
• En ikke-terminal som genererer to ikke-terminaler. For eksempel S → AB.
• En ikke-terminal som genererer en terminal. For eksempel, S → a.

For eksempel:

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

Produksjonsreglene til Grammatikk G1 tilfredsstiller reglene spesifisert for CNF, så grammatikken G1 er i CNF. Produksjonsregelen til Grammar G2 tilfredsstiller imidlertid ikke reglene spesifisert for CNF da S → aZ inneholder terminal etterfulgt av ikke-terminal. Så grammatikken G2 er ikke i CNF.

romertall diagram 1 100

Trinn for å konvertere CFG til CNF

Trinn 1: Fjern startsymbolet fra RHS. Hvis startsymbolet T er på høyre side av en produksjon, oppretter du en ny produksjon som:

 S1 → S 

Hvor S1 er det nye startsymbolet.

Steg 2: Fjern null-, enhets- og ubrukelige produksjoner i grammatikken. Du kan se forenklingen av CFG.

Trinn 3: Eliminer terminaler fra produksjonens RHS hvis de eksisterer med andre ikke-terminaler eller terminaler. For eksempel kan produksjon S → aA dekomponeres som:

 S → RA R → a 

Trinn 4: Eliminer RHS med mer enn to ikke-terminaler. For eksempel kan S → ASB dekomponeres som:

 S → RS R → AS 

Eksempel:

Konverter den gitte CFG til CNF. Tenk på den gitte grammatikken G1:

java erstatte alt

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

Løsning:

Trinn 1: Vi vil lage en ny produksjon S1 → S, ettersom startsymbolet S vises på RHS. Grammatikken vil være:

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

Steg 2: Ettersom grammatikk G1 inneholder A → ε nullproduksjon, gir fjerning fra grammatikken:

ascii tabell java

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

Nå, ettersom grammatikk G1 inneholder enhetsproduksjon S → B, gir dens fjerning:

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

Fjern også enhetsproduksjonen S1 → S, fjerning av den fra grammatikken gir:

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

Trinn 3: I produksjonsregelen S0 → aA | Aa, S → aA | Aa, A → aBB og B → Aa, terminal a eksisterer på RHS med ikke-terminaler. Så vi vil erstatte terminal a med X:

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

Trinn 4: I produksjonsregelen A → XBB har RHS mer enn to symboler, og fjerner det fra grammatikkutbyttet:

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

Derfor, for den gitte grammatikken, er dette den nødvendige CNF.

hvilken samling i java