CNF står for Chomsky normal form. En CFG (kontekstfri grammatik) er i CNF (Chomsky normal form), hvis alle produktionsregler opfylder en af ​​følgende betingelser:

• Start symbolgenerering ε For eksempel A → ε.
• En ikke-terminal, der genererer to ikke-terminaler. For eksempel S → AB.
• En ikke-terminal, der 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} 

Produktionsreglerne for Grammar G1 opfylder reglerne specificeret for CNF, så grammatikken G1 er i CNF. Produktionsreglen for Grammar G2 opfylder dog ikke reglerne specificeret for CNF, da S → aZ indeholder terminal efterfulgt af ikke-terminal. Så grammatikken G2 er ikke i CNF.

java streng længde

Trin til konvertering af CFG til CNF

Trin 1: Fjern startsymbolet fra RHS. Hvis startsymbolet T er i højre side af en produktion, skal du oprette en ny produktion som:

 S1 → S 

Hvor S1 er det nye startsymbol.

Trin 2: Fjern null-, enheds- og ubrugelige produktioner i grammatikken. Du kan henvise til Simplification of CFG.

Trin 3: Fjern terminaler fra produktionens RHS, hvis de findes med andre ikke-terminaler eller terminaler. For eksempel kan produktion S → aA dekomponeres som:

 S → RA R → a 

Trin 4: Eliminer RHS med mere end to ikke-terminaler. For eksempel kan S → ASB dekomponeres som:

 S → RS R → AS 

Eksempel:

Konverter den givne CFG til CNF. Overvej den givne grammatik G1:

linux task manager

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

Løsning:

Trin 1: Vi vil oprette en ny produktion S1 → S, da startsymbolet S vises på RHS. Grammatikken vil være:

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

Trin 2: Da grammatik G1 indeholder A → ε nulproduktion, giver fjernelse fra grammatikken:

navnekonvention java

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

Nu, da grammatik G1 indeholder enhedsproduktion S → B, giver dets fjernelsesudbytte:

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

Fjern også enhedsproduktionen S1 → S, dens fjernelse fra grammatikken giver:

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

Trin 3: I produktionsreglen S0 → aA | Aa, S → aA | Aa, A → aBB og B → Aa, terminal a findes 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 

Trin 4: I produktionsreglen A → XBB har RHS mere end to symboler, hvilket fjerner det fra grammatikudbyttet:

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

Derfor, for den givne grammatik, er dette den nødvendige CNF.

hvordan man derefererer en pointer i c