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.