Edición de «Forma normal de Chomsky»

Una [[gramática formal]] está en '''Forma normal de [[Noam Chomsky|Chomsky]]''' si todas sus reglas de producción son de alguna de las siguientes formas: 

: <math>A</math><math>\rightarrow\, </math><math>BC</math> o
: <math>A</math><math>\rightarrow\, </math>α

donde <math>A</math>, <math>B</math> y <math>C</math> son símbolos no terminales (o variables) y α es un símbolo terminal.

Todo [[Lenguaje libre de contexto|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 libre de contexto|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:

: <math>A</math><math>\rightarrow\, </math><math>BC</math> o
: <math>A</math><math>\rightarrow\, </math>α o
: <math>S</math><math>\rightarrow\, </math>ε

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

== Véase también ==

* [[Gramática (autómata)]]
* [[Forma normal de Greibach]]

{{Control de autoridades}}
[[Categoría:Gramática generativa]]
[[Categoría:Noam Chomsky]]