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.