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:
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 sucesión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":
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 construcción, es decir, se plantea directamente un algoritmo capaz de obtener la FNG a partir de una GIC dada.
forma, normal, greibach, gramática, independiente, contexto, está, todas, cada, reglas, producción, tienen, consecuente, empieza, carácter, alfabeto, también, llamado, símbolo, terminal, formalmente, cualquiera, reglas, tendrá, estructura, displaystyle, donde,. Una gramatica independiente del contexto GIC esta en Forma normal de Greibach FNG si todas y cada una de sus reglas de produccion tienen un consecuente que empieza por un caracter del alfabeto tambien llamado simbolo terminal Formalmente cualquiera de las reglas tendra la estructura A gt a w displaystyle A gt aw Donde A es el antecedente de la regla que en el caso de las GIC debe ser necesariamente un solo simbolo auxiliar Por su parte a es el mencionado comienzo del consecuente y por tanto un simbolo terminal Finalmente w representa una concatenacion generica de elementos gramaticales esto es una sucesion exclusivamente de auxiliares inclusive pudiera ser la palabra vacia en este caso particular se tendria una regla llamada terminal A gt a displaystyle A gt a Existe un teorema que prueba que cualquier GIC cuyo lenguaje no contiene a la palabra vacia si no lo esta ya se puede transformar en otra equivalente que si este en FNG Para su demostracion normalmente se procede por construccion es decir se plantea directamente un algoritmo capaz de obtener la FNG a partir de una GIC dada Vease tambien EditarGramatica automata Forma normal de Chomsky Datos Q1499325 Obtenido de https es wikipedia org w index php title Forma normal de Greibach amp oldid 117365891, wikipedia, wiki, leyendo, leer, libro, biblioteca,
