Forma normale di Chomsky

Nella teoria dei linguaggi formali, una grammatica libera dal contesto si dice essere nella forma normale di Chomsky (CNF,^[1] o FNC, dall'inglese Chomsky normal form) (scoperta da Noam Chomsky)^[2] se tutte le sue regole di produzione sono nella forma seguente:^[1][3]

${\displaystyle A\rightarrow BC}$ o

${\displaystyle A\rightarrow a}$ o

${\displaystyle S\rightarrow \varepsilon }$,

dove ${\displaystyle A}$, ${\displaystyle B}$ e ${\displaystyle C}$ sono simboli non terminali, ${\displaystyle a}$ è un simbolo terminale (un simbolo che rappresenta un valore costante), ${\displaystyle S}$ è l'assioma di partenza, ${\displaystyle \varepsilon }$ è la stringa vuota, e ${\displaystyle B\neq S\land C\neq S}$.

Tutte le grammatiche nella forma normale di Chomsky sono non contestuali e, viceversa, tutte le grammatiche non contestuali possono essere trasformate in grammatiche equivalenti in FNC. Per eseguire tale trasformazione sono stati ideati più algoritmi. Tuttavia, come fatto notare da Lange e Leiß,^[4] lo svantaggio di queste trasformazioni sta nel grande aumento della dimensione della grammatica, dove tale dimensione equivale alla somma delle dimensioni delle regole di produzione, le quali, a loro volta, equivalgono a 1 più la lunghezza della parte destra. Denotando con ${\displaystyle |G|}$ la dimensione della grammatica originale ${\displaystyle G}$, la crescita di tale dimensione nel peggiore dei casi è compresa fra ${\displaystyle |G|^{2}}$ a ${\displaystyle 2^{2|G|}}$ (dipende dall'algoritmo di trasformazione utilizzato).