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:

ou
ou

onde , e são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), é a variável inicial, e ε é a cadeia vazia. Além disso, nem nem 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 para denotar o tamanho da gramática original , o tamanho do inchaço no pior dos casos pode variar de a , dependendo do algoritmo de transformação utilizado (Lange and Leiß, 2009).

Definição alternativa

Outra forma de definir a forma normal de Chomsky (Hopcroft e Ullman 1979, e Hopcroft et al. 2006) é:

Uma gramática formal está na forma reduzida de Chomsky se todas as suas regras de produção são da seguinte forma:

ou

onde , e são variáveis (símbolos não-terminais), e α é um símbolo terminal. Ao usar esta definição, ou pode ser a variável inicial.

En otros idiomas