En la teoría del lenguaje formal , una gramática libre de contexto está en la 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 (épsilon, ε) 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:
dónde es un símbolo no terminal , es un símbolo de terminal, es una secuencia (posiblemente vacía) de símbolos no terminales que no incluyen el símbolo de inicio y es el símbolo de inicio.
Observe que la gramática no tiene recursiones a la izquierda .
Cada gramática libre de contexto se puede transformar en una gramática equivalente en la forma normal de Greibach. [1] Existen varias construcciones. Algunos no permiten la segunda forma de regla y no pueden transformar gramáticas libres de contexto que pueden generar la palabra vacía. Para una de estas construcciones, el tamaño de la gramática construida es O ( n 4 ) en el caso general y O ( n 3 ) si ninguna derivación de la gramática original consiste en un solo símbolo no terminal, donde n es el tamaño de la gramática original. [2] Esta conversión puede usarse para demostrar 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 longitud n , cualquier analizador de arriba hacia abajo se detendrá en la profundidad n .
Ver también
Referencias
- ^ Greibach, Sheila (enero de 1965). "Un nuevo teorema de forma normal para gramáticas de estructura de frases libres de contexto". Revista de la ACM . 12 (1): 42–52. doi : 10.1145 / 321250.321254 . S2CID 12991430 .
- ^ Blum, Norbert; Koch, Robert (1999). "Revisión de la transformación de 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 .
- 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.