Pesquisa · Mapa mental
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
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: onde A {\displaystyle A} , B {\displaystyle B} e C {\displaystyle C} são variáveis (símbolos não-terminais), e α é um símbolo terminal. Ao usar esta definição, B {\displaystyle B} ou C {\displaystyle C} pode ser a variável inicial.
