Forma normal de Greibach

En la teoría del lenguaje formal, una gramática libre de contexto está en forma normal de Greibach (GNF) si los lados derechos de todas las reglas de producción comienzan con un símbolo terminal, seguido opcionalmente por algunas variables. Una forma no estricta permite una excepción a esta restricción de formato para permitir que la palabra vacía (epsilon, ε) sea miembro del lenguaje descrito. La forma normal fue establecida por Sheila Greibach y lleva su nombre.

Más precisamente, una gramática libre de contexto está en la forma normal de Greibach, si todas las reglas de producción son de la forma:

A→ → aA1A2⋯ ⋯ An{displaystyle Ato aA_{1}A_{2}cdots A_{n}

Donde A{displaystyle A} es un símbolo no final, a{displaystyle a} es un símbolo terminal, A1A2...... An{displaystyle A_{1}A_{2}ldots A_{n} es una secuencia (posiblemente vacía) de símbolos no terminales no incluyendo el símbolo de inicio y S{displaystyle S. es el símbolo de inicio.

Observe que la gramática no tiene recursiones por la izquierda.

Toda gramática independiente del contexto se puede transformar en una gramática equivalente en la forma normal de Greibach. Existen varias construcciones. Algunos no permiten la segunda forma de regla y no pueden transformar gramáticas independientes del contexto que puedan generar la palabra vacía. Para una de estas construcciones, el tamaño de la gramática construida es O(n⁴) en el caso general y O(n³) si ninguna derivación de la gramática original consiste en un único símbolo no terminal, donde n es el tamaño de la gramática original. Esta conversión se puede usar para probar que cada lenguaje libre de contexto puede ser aceptado por un autómata pushdown en tiempo real (no determinista), es decir, el autómata lee una letra de su entrada en cada paso.

Dada una gramática en GNF y una cadena derivable en la gramática con una longitud n, cualquier analizador de arriba hacia abajo se detendrá en la profundidad n.