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:

A {\displaystyle A} → {\displaystyle \rightarrow \,} B C {\displaystyle BC} o

A {\displaystyle A} → {\displaystyle \rightarrow \,} α

donde A {\displaystyle A} , B {\displaystyle B} y C {\displaystyle C} 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.

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:

A {\displaystyle A} → {\displaystyle \rightarrow \,} B C {\displaystyle BC} o

A {\displaystyle A} → {\displaystyle \rightarrow \,} α o

S {\displaystyle S} → {\displaystyle \rightarrow \,} ε

donde S {\displaystyle S} es el símbolo distinguido (o inicial) de la gramática, A {\displaystyle A} es un símbolo no terminal (o variable), B {\displaystyle B} y C {\displaystyle C} también son símbolos no terminales pero distintos de S {\displaystyle S} , α es un símbolo terminal, y ε es la cadena nula (o vacía).

• Gramática (autómata)
• Forma normal de Greibach