CNF apzīmē Chomsky parasto formu. CFG (bezkonteksta gramatika) ir CNF (Chomsky normālā formā), ja visi ražošanas noteikumi atbilst vienam no šiem nosacījumiem:

• Sākt ģenerēt simbolu ε, piemēram, A → ε.
• Netermināls, kas ģenerē divus neterminālus. Piemēram, S → AB.
• Neterminālis, kas ģenerē termināli. Piemēram, S → a.

Piemēram:

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

Gramatikas G1 ražošanas noteikumi atbilst CNF noteiktajiem noteikumiem, tāpēc gramatika G1 ir CNF. Tomēr Grammar G2 ražošanas noteikums neatbilst noteikumiem, kas norādīti CNF, jo S → aZ satur termināli, kam seko netermināls. Tātad gramatika G2 nav CNF.

attēla centrēšana css

Soļi CFG pārvēršanai par CNF

1. darbība: Izņemiet starta simbolu no RHS. Ja sākuma simbols T atrodas jebkura iestudējuma labajā pusē, izveidojiet jaunu iestudējumu šādi:

 S1 → S 

Kur S1 ir jaunais sākuma simbols.

2. darbība: Gramatikā noņemiet nulles, vienības un bezjēdzīgos ražojumus. Varat atsaukties uz CFG vienkāršošanu.

3. darbība: Izslēdziet termināļus no ražošanas RHS, ja tie pastāv ar citiem termināļiem vai termināļiem. Piemēram, produkciju S → aA var sadalīt šādi:

 S → RA R → a 

4. darbība: Likvidējiet RHS ar vairāk nekā diviem netermināļiem. Piemēram, S → ASB var sadalīt šādi:

sapludināt kārtot java

 S → RS R → AS 

Piemērs:

Konvertējiet doto CFG uz CNF. Apsveriet doto gramatiku G1:

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

Risinājums:

1. darbība: Izveidosim jaunu iestudējumu S1 → S, jo uz RHS parādās sākuma simbols S. Gramatika būs šāda:

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

2. darbība: Tā kā gramatika G1 satur A → ε nulles produkciju, tās noņemšana no gramatikas dod:

java virknes savienošana

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

Tagad, tā kā gramatika G1 satur vienību ražošanu S → B, tās noņemšanas raža:

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

Noņemiet arī vienības produkciju S1 → S, tās noņemšana no gramatikas iegūst:

pothineni auns

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

3. darbība: Ražošanas noteikumā S0 → aA | Aa, S → aA | Aa, A → aBB un B → Aa, terminālis a pastāv RHS ar netermināļiem. Tātad termināli a aizstāsim ar X:

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

4. darbība: Ražošanas noteikumā A → XBB RHS ir vairāk nekā divi simboli, kas to noņem no gramatikas iznākuma:

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

Tādējādi dotajai gramatikai tas ir nepieciešamais CNF.