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.
Un ejemplo de gramática lineal es G con N = {S}, Σ = {a, b}, P con símbolo de inicio S y reglas
Genera el lenguaje .
Dos tipos especiales de gramáticas lineales son los siguientes:
Cada uno de ellos puede describir exactamente los lenguajes regulares . Una gramática regular es una gramática lineal hacia la izquierda o hacia la derecha.
Observe que al insertar nuevos no terminales, cualquier gramática lineal puede reemplazarse por una equivalente donde algunas de las reglas son lineales por la izquierda y otras por la derecha. Por ejemplo, las reglas de G anteriores pueden reemplazarse por
Sin embargo, el requisito de que todas las reglas sean lineales a la izquierda (o todas las reglas sean lineales a la derecha) conduce a una disminución estricta del poder expresivo de las gramáticas lineales.
Todos los lenguajes regulares son lineales; por el contrario, un ejemplo de lenguaje lineal no regular es { a n b n }, como se explicó anteriormente. Todos los lenguajes lineales son independientes del contexto ; por el contrario, un ejemplo de lenguaje independiente del contexto y no lineal es el lenguaje Dyck de pares de corchetes bien equilibrados. Por lo tanto, los lenguajes regulares son un subconjunto propio de los lenguajes lineales, que a su vez son un subconjunto propio de los lenguajes independientes del contexto.
Si bien los lenguajes regulares son deterministas , existen lenguajes lineales que no son deterministas. Por ejemplo, el lenguaje de palíndromos de longitud par 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 todas sus letras primero, lo que significa que un autómata de empuje hacia abajo tiene que intentar transiciones de estado alternativas para adaptarse a las diferentes longitudes posibles de una cadena semianalizada. [1] Este lenguaje es no determinista. Dado que los lenguajes libres de contexto no deterministas no se pueden aceptar en tiempo lineal [ aclaración necesaria ] , los lenguajes lineales no se pueden aceptar en tiempo lineal en el caso general. Además, es indecidible si un lenguaje libre de contexto dado es un lenguaje libre de contexto lineal. [2]
Un lenguaje es lineal si puede ser generado por un autómata de empuje de una vuelta: un autómata de empuje que, una vez que empieza a hacer pops, nunca vuelve a empujar.
Los lenguajes lineales están cerrados bajo la unión . La construcción es la misma que la construcción para la unión de lenguajes libres de contexto. Sean dos lenguajes lineales, entonces se construye mediante una gramática lineal con , y desempeñando el papel de las gramáticas lineales para .
Si L es un lenguaje lineal y M es un lenguaje regular , entonces la intersección es nuevamente un lenguaje lineal; en otras palabras, los lenguajes lineales están cerrados bajo intersección con conjuntos regulares.
Los lenguajes lineales están cerrados bajo homomorfismo y homomorfismo inverso . [3]
Como corolario , los lenguajes lineales forman un trío completo . Los tríos completos en general son familias de lenguajes que disfrutan de un par de propiedades matemáticas deseables adicionales.
Los lenguajes lineales no están cerrados a la intersección. Por ejemplo, sea , entonces su intersección no solo no es lineal, sino que tampoco es libre de contexto. Véase el lema de bombeo para lenguajes libres de contexto .
Como corolario, los lenguajes lineales no están cerrados bajo el complemento (ya que la intersección puede construirse mediante las leyes de De Morgan a partir de la unión y el complemento).
