Forma Normal de Chomsky

Em ciência da computação, uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras de produção são da forma: A → B C {\displaystyle A\rightarrow BC} ou A → α {\displaystyle A\rightarrow \alpha } ou S → ε {\displaystyle S\rightarrow \varepsilon } onde A {\displaystyle A} , B {\displaystyle B} e C {\displaystyle C} são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), S {\displaystyle S} é a variável inicial, e ε é a cadeia vazia. Além disso, nem B {\displaystyle B} nem C {\displaystyle C} podem ser a variável inicial. Toda gramática na forma normal de Chomsky é uma livre de contexto, e inversamente, toda gramática livre de contexto pode ser transformada em uma equivalente que está na forma normal de Chomsky. Vários algoritmos para realizar tal transformação são conhecidos. Transformações são descritas na maioria dos livros sobre teoria dos autômatos, tais como (Hopcroft and Ullman, 1979). Como apontado por Lange and Leiß, a desvantagem destas transformações é que elas podem levar a um inchaço indesejável no tamanho da gramática. Usando | G | {\displaystyle |G|} para denotar o tamanho da gramática original G {\displaystyle G} , o tamanho do inchaço no pior dos casos pode variar de | G | 2 {\displaystyle |G|^{2}} a 2 2 | G | {\displaystyle 2^{2|G|}} , dependendo do algoritmo de transformação utilizado (Lange and Leiß, 2009).