Forma normal de Chomsky
# 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$$\rightarrow \,$$BC$ o
    $A$$\rightarrow \,$α

donde $A$, $B$ y $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.

## Definición Alternativa

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$$\rightarrow \,$$BC$ o
    $A$$\rightarrow \,$α o
    $S$$\rightarrow \,$ε

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

