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