Forma normal de Chomsky
De Wikipedia, la enciclopedia encyclopedia
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.