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

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 .${\displaystyle \{a^{i}b^{i}\;|\;i\geq 0\}}$

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 todas las reglas son de la forma A → αw donde α es vacío o un solo no terminal yw es una cadena de terminales;
• las gramáticas lineales a la derecha o regulares a la derecha, en las que todas las reglas son de la forma A → wα donde w es una cadena de terminales y α es vacío o un solo no terminal.

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.

Observe que insertando nuevos no terminales, cualquier gramática lineal puede ser reemplazada por una equivalente donde algunas de las reglas son lineales a la izquierda y otras son lineales a la derecha. Por ejemplo, las reglas de G anteriores se pueden reemplazar con

S → aA

A → Sb

S → ε

Sin embargo, el requisito de que todas las reglas sean lineales a la izquierda (o que 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; a la inversa, un ejemplo de lenguaje lineal no regular es { a ⁿ b ⁿ }. 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ón es nuevamente 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.${\displaystyle L\cap M}$

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). doi : 10.1145 / 321356.321365 .
3. 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