Forma normale di Chomsky

Una CFG $G$ è detta in forma normale di Chomsky se ogni sua regola è in una delle seguenti forme:

• $A\to BC$, con $B,C\ne S$: lo start symbol sta solo a sinistra e i non-terminali a destra stanno in coppia
• $A\to a$: ogni opzione di $A$ ha un solo terminale
• $S_0\to ϵ$, se $ϵ\in L(G)$: lo start symbol $S_0$ è l'unico che può avere questa regola

Si può dimostrare che ogni linguaggio context-free è generato da una CFG in forma normale di Chomsky, infatti è possibile convertire una qualsiasi CFG in forma normale attraverso delle trasformazioni:

1. Introdurre un nuovo simbolo iniziale $S_0\to S$
2. Eliminare le $ϵ$-regole $A\to ϵ$ aggiungendo alle regole padre i casi in cui $A$ è presente oppure no
3. Eliminare le regole unitarie $A\to B$ rimpiazzando il non-terminale a destra con il suo contenuto
4. Dividi le regole $A\to u_1{u}_2\cdots u_n$ per $n>2$ e $u_i\in (V\cup \Sigma )$ in $A\to u_1{A}_1,...,A_{n-2}\to u_{n-1}{u}_n$
5. Rimpiazza ogni terminale non solitario $a\in \Sigma$ con una regola $A\to a$

L'ordine del quarto e quinto punto non causa problemi perchè la divisione include anche i terminali.

Per esempio¹, $$\begin{array}{rlrlr}& \begin{array}{rl}& S\to ASA\mid aB\\ & A\to B\mid S\\ & B\to b\mid ϵ\end{array}\underset{1}{\Rightarrow }\begin{array}{rl}& S_0\to S\\ & S\to ASA\mid aB\\ & A\to B\mid S\\ & B\to b\mid ϵ\end{array}& & \underset{2}{\Rightarrow }\begin{array}{rl}& S_0\to S\\ & S\to ASA\mid aB\mid a\\ & A\to B\mid S\mid ϵ\\ & B\to b\end{array}& \Rightarrow \\ & \underset{2}{\Rightarrow }\begin{array}{rl}& S_0\to S\\ & S\to ASA\mid aB\mid a\mid SA\mid AS\mid S\\ & A\to B\mid S\\ & B\to b\end{array}& & \underset{3}{\Rightarrow }\begin{array}{rl}& S_0\to ASA\mid aB\mid a\mid SA\mid AS\\ & S\to ASA\mid aB\mid a\mid SA\mid AS\\ & A\to b\mid ASA\mid aB\mid a\mid SA\mid AS\\ & B\to b\end{array}& \Rightarrow \\ & \underset{4}{\Rightarrow }\begin{array}{rl}& S_0\to A{A}_1\mid aB\mid a\mid SA\mid AS\\ & S\to A{A}_1\mid aB\mid a\mid SA\mid AS\\ & A\to b\mid A{A}_1\mid aB\mid a\mid SA\mid AS\\ & B\to b\\ & A_1\to SA\end{array}& & \underset{5}{\Rightarrow }\begin{array}{rl}& S_0\to A{A}_1\mid UB\mid a\mid SA\mid AS\\ & S\to A{A}_1\mid UB\mid a\mid SA\mid AS\\ & A\to b\mid A{A}_1\mid UB\mid a\mid SA\mid AS\\ & B\to b\\ & A_1\to SA\\ & U\to a\end{array}& \end{array}$$