En informática , una gramática lineal es una gramática libre de contexto que tiene como máximo un no terminal en el lado derecho de cada una de sus producciones.
Un lenguaje lineal es un lenguaje generado por alguna gramática lineal.
Ejemplo
Una gramática lineal simple es G con N = {S}, Σ = {a, b}, P con el símbolo de inicio S y reglas
- S → aSb
- S → ε
Genera el lenguaje .
Relación con las gramáticas regulares
Dos tipos especiales de gramáticas lineales son los siguientes:
- las gramáticas lineales a la izquierda o regulares a la izquierda, en las que todos los no terminales de los lados derechos están en los extremos izquierdos ;
- las gramáticas lineales a la derecha o regulares a la derecha, en las que todos los no terminales en los lados derechos están en los extremos derechos .
Cada uno de estos puede describir exactamente los idiomas regulares . Una gramática regular es una gramática lineal a la izquierda o lineal a la derecha.
Otro tipo especial de gramática lineal es el siguiente:
- gramáticas lineales en las que todos los no terminales en el lado derecho están en los extremos izquierdo o derecho, pero no necesariamente todos en el mismo extremo.
Al insertar nuevos no terminales, cada gramática lineal puede incorporarse a esta forma sin afectar el lenguaje generado. Por ejemplo, las reglas de G anteriores se pueden reemplazar con
- S → aA
- A → Sb
- S → ε
Por tanto, las gramáticas lineales de esta forma especial pueden generar todos los lenguajes lineales.
Poder expresivo
Todos los lenguajes regulares son lineales; a la inversa, un ejemplo de lenguaje lineal no regular es { a n b n }. como se explicó anteriormente. Todos los lenguajes lineales están libres de contexto ; a la inversa, un ejemplo de un lenguaje no lineal y sin contexto es el lenguaje Dyck de pares de paréntesis bien equilibrados. Por lo tanto, los lenguajes regulares son un subconjunto adecuado de los lenguajes lineales, que a su vez son un subconjunto adecuado de los lenguajes libres de contexto.
Mientras que los lenguajes lineales que son lenguajes regulares son deterministas , existen lenguajes lineales que son no deterministas. Por ejemplo, el lenguaje de palíndromos pares en el alfabeto de 0 y 1 tiene la gramática lineal S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no se puede analizar sin leer primero todas sus letras, lo que significa que un autómata pushdown tiene que probar transiciones de estado alternativas para adaptarse a las diferentes longitudes posibles de una cadena semi-analizada. [1] Este lenguaje no es determinista. Dado que los lenguajes no deterministas libres de contexto no pueden aceptarse en tiempo lineal, los lenguajes lineales no pueden aceptarse en tiempo lineal en el caso general. Además, es indecidible si un lenguaje libre de contexto dado es un lenguaje lineal libre de contexto. [2]
Propiedades de cierre
Si L es un lenguaje lineal y M es un lenguaje regular, entonces la intersecciónes de nuevo un lenguaje lineal; en otras palabras, los lenguajes lineales se cierran bajo intersección con conjuntos regulares. Además, los lenguajes lineales están cerrados bajo homomorfismo y homomorfismo inverso . [3] Estas tres propiedades de cierre muestran que los lenguajes lineales forman un trío completo . Los tríos completos en general son familias de lenguas que disfrutan de un par de otras propiedades matemáticas deseables.
Referencias
- ^ Hopcroft, John ; Rajeev Motwani ; Jeffrey Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación 2ª edición . Addison-Wesley. págs. 249-253.
- ^ Greibach, Sheila (octubre de 1966). "La insolubilidad del reconocimiento de lenguajes lineales libres de contexto". Revista de la ACM . 13 (4). doi : 10.1145 / 321356.321365 .
- ^ John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X ., Ej. 11.1, págs.282 y siguientes