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 al permitir que la palabra vacía (epsilon, ε) sea un 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 forma normal de Greibach, si todas las reglas de producción son de la forma:

A\to aA_{1}A_{2}\cdots A_{n}

donde es un símbolo no terminal , es un símbolo terminal y es una secuencia (posiblemente vacía) de símbolos no terminales. ${\estilo de visualización A}$ ${\estilo de visualización a}$ $A_{1}A_{2}\ldots A_{n}$

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

Toda gramática libre de contexto puede transformarse en una gramática equivalente en forma normal de Greibach. ^[1] Existen varias construcciones. Algunas no permiten la segunda forma de regla y no pueden transformar gramáticas libres de contexto que puedan generar la palabra vacía. Para una de esas 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. ^[2] Esta conversión se puede utilizar para demostrar que todo lenguaje libre de contexto puede ser aceptado por un autómata de inserción 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 longitud n , cualquier analizador de arriba hacia abajo se detendrá en la profundidad n .

Véase también

Referencias

^ Greibach, Sheila (enero de 1965). "Un nuevo teorema de la forma normal para gramáticas de estructura de frase independientes del contexto". Revista de la ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430.
^ Blum, Norbert; Koch, Robert (1999). "Revisitando la transformación de la forma normal de Greibach". Información y computación . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . doi :10.1006/inco.1998.2772. S2CID 10302796.

Alexander Meduna (6 de diciembre de 2012). Autómatas y lenguajes: teoría y aplicaciones. Springer Science & Business Media. ISBN 978-1-4471-0501-5.
György E. Révész (17 de marzo de 2015). Introducción a los lenguajes formales. Corporación de mensajería. ISBN 978-0-486-16937-8.

[1] Greibach, Sheila (enero de 1965). "Un nuevo teorema de la forma normal para gramáticas de estructura de frase independientes del contexto". Revista de la ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430.

[2] Blum, Norbert; Koch, Robert (1999). "Revisitando la transformación de la forma normal de Greibach". Información y computación . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . doi :10.1006/inco.1998.2772. S2CID 10302796.