CNF står för Chomsky normal form. En CFG (kontextfri grammatik) är i CNF (Chomsky normal form) om alla produktionsregler uppfyller något av följande villkor:
- Börja generera ε till exempel A → ε.
- En icke-terminal som genererar två icke-terminaler. Till exempel S → AB.
- En icke-terminal som genererar en terminal. Till exempel, S → a.
Till exempel:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} Produktionsreglerna för Grammatik G1 uppfyller reglerna som specificeras för CNF, så grammatiken G1 är i CNF. Produktionsregeln för Grammar G2 uppfyller dock inte reglerna som specificeras för CNF eftersom S → aZ innehåller terminal följt av icke-terminal. Så grammatiken G2 finns inte i CNF.
byta namn på katalogen i linux
Steg för att konvertera CFG till CNF
Steg 1: Eliminera startsymbolen från RHS. Om startsymbolen T finns till höger om någon produktion, skapa en ny produktion som:
S1 → S
Där S1 är nystartssymbolen.
Steg 2: Ta bort null, enhet och värdelösa produktioner i grammatiken. Du kan hänvisa till förenklingen av CFG.
Steg 3: Eliminera terminaler från produktionens RHS om de finns med andra icke-terminaler eller terminaler. Till exempel kan produktion S → aA delas upp som:
S → RA R → a
Steg 4: Eliminera RHS med fler än två icke-terminaler. Till exempel kan S → ASB delas upp som:
S → RS R → AS
Exempel:
Konvertera den givna CFG till CNF. Betrakta den givna grammatiken G1:
funktioner i en pandaserie
S → a | aA | B A → aBB | ε B → Aa | b
Lösning:
Steg 1: Vi kommer att skapa en ny produktion S1 → S, eftersom startsymbolen S visas på RHS. Grammatiken blir:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
Steg 2: Eftersom grammatik G1 innehåller A → ε nollproduktion, ger dess borttagning från grammatiken:
sorteringsmatris i java
S1 → S S → a | aA | B A → aBB B → Aa | b | a
Nu, eftersom grammatik G1 innehåller enhetsproduktion S → B, ger dess borttagning:
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
Ta också bort enhetsproduktionen S1 → S, dess borttagning från grammatiken ger:
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
Steg 3: I produktionsregeln S0 → aA | Aa, S → aA | Aa, A → aBB och B → Aa, terminal a finns på RHS med icke-terminaler. Så vi kommer att ersätta terminal a med X:
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
Steg 4: I produktionsregeln A → XBB har RHS fler än två symboler, vilket tar bort det från grammatikutbytet:
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
Därför, för den givna grammatiken, är detta den nödvändiga CNF.
spara youtube video vlc