logo

Forma normal de Greibach (GNF)

GNF significa forma normal de Greibach. Una CFG (gramática libre de contexto) está en GNF (forma normal de Greibach) si todas las reglas de producción satisfacen una de las siguientes condiciones:

Java ¡vaya conceptos!
  • Un símbolo inicial que genera ε. Por ejemplo, S → ε.
  • Un no terminal que genera un terminal. Por ejemplo, A → a.
  • Un no terminal que genera un terminal seguido por cualquier número de no terminales. Por ejemplo, S → aASB.

Por ejemplo:

 G1 = aB, A → aA G2 = S → aAB 

Las reglas de producción de la Gramática G1 satisfacen las reglas especificadas para GNF, por lo que la gramática G1 está en GNF. Sin embargo, la regla de producción de Gramática G2 no satisface las reglas especificadas para GNF ya que A → ε y B → ε contienen ε (solo el símbolo inicial puede generar ε). Entonces la gramática G2 no está en GNF.

Pasos para convertir CFG en GNF

Paso 1: Convierte la gramática a CNF.

Si la gramática dada no está en CNF, conviértala a CNF. Puede consultar el siguiente tema para convertir el CFG en CNF: Forma normal de Chomsky

Paso 2: Si la gramática existe recursión izquierda, elimínela.

identificadores válidos de java

Si la gramática libre de contexto contiene recursividad hacia la izquierda, elimínela. Puede consultar el siguiente tema para eliminar la recursividad hacia la izquierda: Recursión hacia la izquierda

Paso 3: En la gramática, convierta la regla de producción dada a la forma GNF.

Si alguna regla de producción en la gramática no está en forma GNF, conviértala.

Ejemplo:

 S → XB | AA A → a | SA B → b X → a 

Solución:

Como la gramática G dada ya está en CNF y no hay recursividad a la izquierda, podemos omitir los pasos 1 y 2 e ir directamente al paso 3.

negación matemática discreta

La regla de producción A → SA no está en GNF, por lo que sustituimos S → XB | AA en la regla de producción A → SA como:

 S → XB | AA A → a | XBA | AAA B → b X → a 

La regla de producción S → XB y B → XBA no está en GNF, por lo que sustituimos X → a en la regla de producción S → XB y B → XBA como:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Ahora eliminaremos la recursividad hacia la izquierda (A → AAA), obtenemos:

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Ahora eliminaremos la producción nula C → ε, obtenemos:

numerar el alfabeto
 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

La regla de producción S → AA no está en GNF, por lo que sustituimos A → aC | aBAC | un | aBA en la regla de producción S → AA como:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

La regla de producción C → AAC no está en GNF, por lo que sustituimos A → aC | aBAC | un | aBA en la regla de producción C → AAC como:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Por tanto, ésta es la forma GNF de la gramática G.