forma normale di Chomsky

Una grammatica acontestuale (CFG) è in forma normale se oni sua regola è nella forma $A\to BC$ oppure $A\to a$. Dove $A,B,C\in V,a\in \Sigma ,B,C\notin S$. È ammessa anche la regola $S\to \epsilon$.

Teorema: ogni CFG ammette una CFG equivalente in forma normale.

1. Dobbiamo trasformare le regola della CFG. Per prima cosa aggiungo $S_0$, la nuova variabile iniziale e le regole $S_0\to S$.
2. Passiamo poi alle $\epsilon$-regole: $A\to \epsilon$. Per ogni occorrenza di $A$ sul lato destro di una regola, aggiungo nuove regole con occorrenza cancellata. (praticamente per poter togliere $A\to \epsilon$ si applica $A\to \epsilon$ a tutte le regole vecchie). Esempio: $A\to \epsilon$ $B\to uAv$, con $u,v$ stringhe di variabili/terminali. $⟹B\to uv$ Altro esempio: $B\to uAvAw$ $⟹B\to uvw\mid uAvw\mid uvAw\mid uAvAw$ Altro esempio: $B\to CC\to A\mid c$ diventano $B\to A\mid c$ e $C\to A\mid c$
3. Togliamo le regole unitarie: $A\to B$. Per ogni occorrenza di regole $B\to u$, aggiungo $A\to u$. ($u$ sempre sequenza di variabili/terminali) (piccola gif a scopo di intrattenimento)
4. Infine tolgo tutte le $A\to u_1,u_2,\dots ,u_{k}k\ge 3$, quindi per compensare introduco nelle regole nuove $A\to w_1{A}_1,A_1\to w_2{A}_2,A_2\to w_3{A}_3\dots A_{k-2}\to w_{k-2}{w}_k$ Esempio: $A\to aBC$ $A\to a{A}_1$ $A_1\to BC$ dopodiché $A\to a{A}_1$ (che non è ancora in CFG) diventa $A\to U{A}_1$ e $U\to a$, dove $U$ è una variabile d’appoggio introdotta adesso.

Esercizio

ŧodo

Regole originali

• $S\to ASA\mid aB$
• $A\to B\mid S$
• $B\to b\mid \epsilon$

Primo passaggio: aggiunta di $S_0$.

• $S_0\to S$
• $A\to ASA\mid aB$
• $A\to B\mid S$
• $B\to b\mid \epsilon$

Secondo passaggio: togliamo le $\epsilon$ regole.

• $S_0\to S$
• $S\to ASA\mid aB\mid a$
• $a\to B\mid S\mid \epsilon$
• $B\to b$

Terzo passaggio: togliamo le regole unitarie.

• togliamo $S_0\to S$ e per compensare aggiungiamo $S_0\to ASA\mid aB\mid a\mid SA\mid AS\mid S$