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