CNF reiškia Chomsky normalią formą. CFG (nekontekstinė gramatika) yra CNF (Chomsky normalios formos), jei visos gamybos taisyklės atitinka vieną iš šių sąlygų:

• Pradėti generuoti simbolį ε Pavyzdžiui, A → ε.
• Ne terminalas, generuojantis du ne terminalus. Pavyzdžiui, S → AB.
• Ne terminalas, generuojantis terminalą. Pavyzdžiui, S → a.

Pavyzdžiui:

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

Gramatikos G1 gamybos taisyklės atitinka CNF nurodytas taisykles, todėl gramatika G1 yra CNF. Tačiau Gramatikos G2 gamybos taisyklė neatitinka CNF nurodytų taisyklių, nes S → aZ yra terminalas, po kurio eina ne terminalas. Taigi gramatikos G2 nėra CNF.

nuo 1 iki 100 romėnų Nr

CFG konvertavimo į CNF žingsniai

1 žingsnis: Pašalinkite pradžios simbolį iš RHS. Jei pradžios simbolis T yra dešinėje kūrinio pusėje, sukurkite naują produkciją taip:

 S1 → S 

Kur S1 yra naujos pradžios simbolis.

2 žingsnis: Iš gramatikos pašalinkite nulį, vienetą ir nenaudingus gaminius. Galite kreiptis į CFG supaprastinimą.

3 veiksmas: Pašalinkite terminalus iš gamybos RHS, jei jie yra su kitais ne terminalais arba terminalais. Pavyzdžiui, produkcija S → aA gali būti išskaidyta taip:

pabėgimo simbolis java

 S → RA R → a 

4 veiksmas: Pašalinkite RHS su daugiau nei dviem ne terminalais. Pavyzdžiui, S → ASB gali būti suskaidytas taip:

 S → RS R → AS 

Pavyzdys:

Konvertuokite nurodytą CFG į CNF. Apsvarstykite pateiktą gramatiką G1:

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

Sprendimas:

1 žingsnis: Sukursime naują produkciją S1 → S, nes dešinėje pusėje atsiras starto simbolis S. Gramatika bus tokia:

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

2 žingsnis: Kadangi gramatikoje G1 yra A → ε nulinė produkcija, jos pašalinimas iš gramatikos duoda:

java pabėgimo simboliai

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

Kadangi gramatikoje G1 yra vienetų gamyba S → B, jo pašalinimo išeiga:

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

Taip pat pašalinkite vieneto produkciją S1 → S, išėmus ją iš gramatikos, gaunama:

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

3 veiksmas: Gamybos taisyklėje S0 → aA | Aa, S → aA | Aa, A → aBB ir B → Aa, terminalas a egzistuoja RHS su ne terminalais. Taigi terminalą a pakeisime X:

kiek uncijų yra 10 mililitrų

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

4 veiksmas: Gamybos taisyklėje A → XBB RHS turi daugiau nei du simbolius, pašalinančius jį iš gramatikos:

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

Vadinasi, nurodytai gramatikai tai yra būtinas CNF.