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.