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:

${\displaystyle 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. ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle 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

• Forma Backus-Naur
• Forma normal de Chomsky
• Forma normal de Kuroda

Referencias

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. 

• 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.