Gramática lineal

Una gramática lineal es una gramática libre de contexto tal que el lado derecho de cualquiera de sus reglas de inferencia contiene como máximo un no terminal.

Un lenguaje lineal es un lenguaje generado por alguna gramática lineal.

Ejemplo

Un ejemplo simple de una gramática lineal es una con un conjunto de no terminales , un alfabeto , un no terminal inicial y reglas de inferencia. $GRAMO$ ${\ estilo de visualización N = \ {S \}}$ ${\ estilo de visualización \ Sigma = \ {a, b \}}$ $S$

{\ estilo de visualización S \ a aSb}

S\to\varepsilon

Esta gramática genera un lenguaje irregular . $\{a^{i}b^{i}\;|\;i\geq 0\}$

Cumplimiento de los lenguajes regulares

Hay tipos especiales de gramáticas lineales:

Gramática lineal a la izquierda , en la que los no terminales siempre están al principio de las partes derechas de las reglas de inferencia;
Una gramática lineal derecha en la que los no terminales siempre están al final de las partes correctas de las reglas de inferencia.

Cada uno de estos tipos describe individualmente exactamente la clase de lenguajes regulares . Una gramática regular es una gramática que es lineal a la izquierda o lineal a la derecha.

Otro tipo especial de gramática lineal es:

Una gramática lineal en la que los no terminales siempre se encuentran al principio o al final del lado derecho de las reglas de inferencia.

Al agregar nuevos no terminales, cualquier gramática lineal se puede reducir a la forma descrita anteriormente sin cambiar el lenguaje generado por la gramática. Por ejemplo, se puede llevar a la forma $GRAMO$

{\ estilo de visualización S \ a aA}

{\ estilo de visualización A \ a Sb}

S\to\varepsilon

Así, las gramáticas lineales de este tipo generan la misma clase de lenguajes que las gramáticas lineales arbitrarias.

Expresividad

Todos los lenguajes regulares son lineales. El ejemplo clásico de un lenguaje lineal pero no regular es el lenguaje descrito anteriormente . Todos los lenguajes lineales son libres de contexto . Un ejemplo de un lenguaje libre de contexto pero no lineal es el lenguaje Dyck , que consta de secuencias de paréntesis regulares. Así, los lenguajes regulares son su propio subconjunto de lenguajes lineales, que a su vez son su propio subconjunto de lenguajes libres de contexto. ${\displaystyle \{a^{i}b^{i}:i\geq 0\))$

Si bien todos los lenguajes lineales regulares son deterministas , existen lenguajes lineales no deterministas. Un ejemplo de tal lenguaje es el lenguaje de los palíndromos de longitud uniforme sobre el alfabeto , que viene dado por una gramática lineal . Una palabra arbitraria de un idioma dado no puede ser analizada por un autómata pushdown sin leer todos sus símbolos, por lo que el idioma no es determinista [1] . El problema de verificar si un lenguaje libre de contexto dado es lineal no tiene solución [2] . ${\ estilo de visualización \ Sigma = \ {0,1 \}}$ $S\to 0S0|1S1|\varepsilon$

Notas

↑ Hopcroft JE , Motwani R. , Ullman JD Introducción a la teoría de autómatas, lenguajes y computación . — 2 ed. - Addison-Wesley , 2001. - P. 249-253.
↑ Greibach, Sheila. La imposibilidad de resolver el reconocimiento de lenguajes lineales libres de contexto (inglés) // Revista de la ACM : revista. - 1966. - Octubre ( vol. 13 , no. 4 ). -doi : 10.1145/ 321356.321365 .