Forma normal de Greibach

Forma normal de Greibach

Forma normal de Greibach

Se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG), si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:

  • A − > aw

Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesisión de auxiliares y terminales entremezclados, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":

  • A − > a

Existe un teorema que prueba que cualquier GIC, cuyo lenguaje no contiene a la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG. Para su demostración, normalmente, se procede por contrucción, es decir, se plantea directamente un algoritmo capaz de obtener la FNG a partir de una GIC dada.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Forma normal de Chomsky — Saltar a navegación, búsqueda Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción tienen de una de las siguientes formas: A BC o A α o S λ donde S es el símbolo distingu …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”