Forma normal de Chomsky

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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\, α o

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[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:

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).

Véase también[editar]