Forma normal de Chomsky
Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:
- o
- α
donde , y son símbolos no terminales (o variables) y α es un símbolo terminal.
Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.
Definición Alternativa
[editar]En algunos textos se puede encontrar una definición de una GFNCH de forma que cualquier GFNCH produzca cualquier lenguaje independiente del contexto y de la misma manera, que para cualquier lenguaje independiente del contexto exista una GFNCH que lo defina. Esta definición apenas se diferencia en permitir una regla ε de la siguiente forma:
- o
- α o
- ε
donde es el símbolo distinguido (o inicial) de la gramática, es un símbolo no terminal (o variable), y también son símbolos no terminales pero distintos de , α es un símbolo terminal, y ε es la cadena nula (o vacía).