CNF reprezintă forma normală Chomsky. O CFG (gramatică fără context) este în CNF (forma normală Chomsky) dacă toate regulile de producție îndeplinesc una dintre următoarele condiții:

• Simbolul de pornire generează ε De exemplu, A → ε.
• Un non-terminal care generează două non-terminale. De exemplu, S → AB.
• Un non-terminal care generează un terminal. De exemplu, S → a.

De exemplu:

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

Regulile de producție ale Gramaticii G1 îndeplinesc regulile specificate pentru CNF, deci gramatica G1 este în CNF. Cu toate acestea, regula de producție a gramaticii G2 nu îndeplinește regulile specificate pentru CNF, deoarece S → aZ conține terminal urmat de non-terminal. Deci gramatica G2 nu este în CNF.

lista de latex

Pași pentru conversia CFG în CNF

Pasul 1: Eliminați simbolul de pornire din RHS. Dacă simbolul de început T este în partea dreaptă a oricărei producții, creați o nouă producție ca:

 S1 → S 

Unde S1 este noul simbol de pornire.

Pasul 2: În gramatică, eliminați producțiile nule, unitare și inutile. Puteți consulta Simplificarea CFG.

Pasul 3: Eliminați terminalele din RHS ale producției dacă acestea există cu alte non-terminale sau terminale. De exemplu, producția S → aA poate fi descompusă ca:

 S → RA R → a 

Pasul 4: Eliminați RHS cu mai mult de două non-terminale. De exemplu, S → ASB poate fi descompus ca:

obține conexiunea

 S → RS R → AS 

Exemplu:

Convertiți CFG-ul dat în CNF. Luați în considerare gramatica dată G1:

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

Soluţie:

Pasul 1: Vom crea o nouă producție S1 → S, deoarece simbolul de start S apare pe RHS. Gramatica va fi:

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

Pasul 2: Deoarece gramatica G1 conține A → ε producție nulă, eliminarea ei din gramatică are ca rezultat:

int la char java

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

Acum, deoarece gramatica G1 conține producția unitară S → B, randamentul său de eliminare:

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

Îndepărtați și producția unitară S1 → S, eliminarea acesteia din gramatică dă:

rdbms

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

Pasul 3: În regula de producție S0 → aA | Aa, S → aA | Aa, A → aBB și B → Aa, terminalul a există pe RHS cu non-terminale. Deci vom înlocui terminalul a cu X:

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

Pasul 4: În regula de producție A → XBB, RHS are mai mult de două simboluri, eliminându-l din randamentul gramatical:

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

Prin urmare, pentru gramatica dată, acesta este CNF-ul necesar.