Hispanopedia Wiki
Articulo de referencia

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

Hispanopedia WikiContenido en espanolLectura gratuita

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 inicial S y reglas

S → aSb
S → ε

Genera el lenguaje{aibi∣i≥0}{\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}.

Relación con las gramáticas regulares

Existen dos tipos especiales de gramáticas lineales:

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

Cada una de ellas puede describir con exactitud los lenguajes regulares . Una gramática regular es una gramática lineal por la izquierda o lineal por la derecha.

Obsérvese que al insertar nuevos no terminales, cualquier gramática lineal puede ser reemplazada por una equivalente donde algunas de las reglas son lineales por la izquierda y otras son lineales por la derecha. Por ejemplo, las reglas de G anteriores pueden ser reemplazadas por

S → aA
A → Sb
S → ε

Sin embargo, la exigencia de que todas las reglas sean lineales por la izquierda (o todas sean lineales por la derecha) conlleva 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 n b n }, como se explicó anteriormente. Todos los lenguajes lineales son libres de contexto ; por el contrario, un ejemplo de lenguaje libre de contexto no lineal es el lenguaje de 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 libres de contexto.

Si bien los lenguajes regulares son deterministas , existen lenguajes lineales que no lo son. 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 puede ser analizada sin leer primero todas sus letras, lo que significa que un autómata de pila debe intentar transiciones de estado alternativas para acomodar las diferentes longitudes posibles de una cadena semi-analizada. [ 1 ] Este lenguaje no es determinista. Dado que los lenguajes libres de contexto no deterministas no pueden ser aceptados en tiempo lineal , los lenguajes lineales no pueden ser aceptados 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 y solo si puede ser generado por un autómata de pila de una sola vuelta, un autómata de pila que, una vez que comienza a extraer, nunca vuelve a insertar.

Propiedades de cierre

Casos positivos

Los lenguajes lineales son cerrados bajo la unión . La construcción es la misma que la construcción para la unión de lenguajes libres de contexto. SeaL1,L2{\displaystyle L_{1},L_{2}}sean dos lenguajes lineales, entoncesL1∪L2{\ Displaystyle L_ {1} \ taza L_ {2}}se construye mediante una gramática lineal conS→S1|S2{\displaystyle S\to S_{1}|S_{2}}, yS1,S2{\displaystyle S_{1},S_{2}}desempeñando el papel de las gramáticas lineales paraL1,L2{\displaystyle L_{1},L_{2}}.

Si L es un lenguaje lineal y M es un lenguaje regular , entonces la intersecciónL∩METRO{\displaystyle L\cap M}es de nuevo un lenguaje lineal; en otras palabras, los lenguajes lineales son cerrados bajo la intersección con conjuntos regulares.

Los lenguajes lineales son 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 poseen otras propiedades matemáticas deseables.

Casos negativos

Los lenguajes lineales no son cerrados bajo la intersección. Por ejemplo,L1={anortebnortedometro∣norte,metro≥0},L2={anortebmetrodometro∣norte,metro≥0}{\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\}}, 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 son 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 irresolubilidad del reconocimiento de lenguajes libres de contexto lineales" . Journal of the 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. 282f