Gramática lineal

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

Un ejemplo de gramática lineal es G con N = {S}, Σ = {a, b}, P con símbolo de inicio S y reglas

S → aSb

S → ε

Genera el lenguaje . ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$

Relación con las gramáticas regulares

Dos tipos especiales de gramáticas lineales son los siguientes:

• las gramáticas lineales por la izquierda o regulares por la izquierda, en las que todas las reglas tienen la forma A → αw, donde α está vacío o es un único no terminal y w es una cadena de terminales;
• las gramáticas lineales derechas o regulares derechas, en las que todas las reglas tienen la forma A → wα, donde w es una cadena de terminales y α está vacía o es un único no terminal.

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

S → aA

A → Sb

S → ε

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.

Poder expresivo

Todos los lenguajes regulares son lineales; por el contrario, un ejemplo de lenguaje lineal no regular es { a ⁿ b ⁿ }, 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 no deterministas libres de contexto 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 lineal libre de contexto. ^[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 ruido, nunca vuelve a empujar.

Propiedades del cierre

Casos positivos

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 . ${\displaystyle L_{1},L_{2}}$ ${\displaystyle L_{1}\cup L_{2}}$ ${\displaystyle S\to S_{1}|S_{2}}$ ${\displaystyle S_{1},S_{2}}$ ${\displaystyle L_{1},L_{2}}$

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. ${\displaystyle L\cap M}$

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.

Casos negativos

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 . ${\displaystyle L_{1}=\{a^{n}b^{n}c^{m}\mid n,m\geq 0\},L_{2}=\{a^{n}b^{m}c^{m}\mid n,m\geq 0\}}$

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

Referencias

1. 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.
2. Greibach, Sheila (octubre de 1966). "La insolubilidad del reconocimiento de lenguajes lineales libres de contexto". Revista de la ACM . 13 (4): 582–587. doi : 10.1145/321356.321365 . S2CID  37003419.
3. John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación , Addison-Wesley Publishing, Reading, Massachusetts, 1979. ISBN 0-201-02988-X , ej. 11.1, págs. 282 y siguientes.