Lenguaje libre de contexto

Diferentes gramáticas libres de contexto pueden generar el mismo lenguaje libre de contexto. Las propiedades intrínsecas del lenguaje pueden distinguirse de las propiedades extrínsecas de una gramática particular al comparar múltiples gramáticas que describen el lenguaje.

El conjunto de todos los lenguajes libres de contexto es idéntico al conjunto de lenguajes aceptados por autómata con pila, lo que hace que estos lenguajes sean susceptibles de análisis sintáctico. Además, para una GLC dada, existe una manera directa de producir un autómata de pila para la gramática (y, por ende, el lenguaje correspondiente), aunque el proceso inverso (producir una gramática dado un autómata) no es tan directo.

Summarize Timeline Top Qs Fact Check

Un ejemplo de lenguaje libre de contexto es ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$, el lenguaje de todas las cadenas no vacías de longitud par, cuya primera mitad está formada por a y la segunda mitad por b. L es generado por la gramática ${\displaystyle S\to aSb~|~ab}$. Este lenguaje no es regular.

Es aceptado por el autómata con pila ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}$ donde ${\displaystyle \delta }$ se define como sigue:^{[Nota 1]}

${\displaystyle {\begin{aligned}\delta (q_{0},a,z)&=(q_{0},az)\\\delta (q_{0},a,a)&=(q_{0},aa)\\\delta (q_{0},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},\varepsilon ,z)&=(q_{f},\varepsilon )\end{aligned}}}$

Los LLC no ambiguos son un subconjunto propio de todos los LLC: existen LLC inherentemente ambiguos. Un ejemplo de un LLC inherentemente ambiguo es la unión de ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}$ con ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}$. Este conjunto es libre de contexto, ya que la unión de dos lenguajes libres de contexto siempre es libre de contexto. Pero no hay forma de analizar sin ambigüedad las cadenas en el subconjunto (no libre de contexto) ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$, que es la intersección de estos dos lenguajes.^[1]

El lenguaje de todos los paréntesis correctamente emparejados es generado por la gramática ${\displaystyle S\to SS~|~(S)~|~\varepsilon }$.

Summarize Timeline Top Qs Fact Check

La naturaleza libre de contexto del lenguaje facilita su análisis con un autómata de pila.

Determinar una instancia del problema de pertenencia; es decir, dada una cadena ${\displaystyle w}$, determinar si ${\displaystyle w\in L(G)}$, donde ${\displaystyle L}$ es el lenguaje generado por una gramática dada ${\displaystyle G}$; también se conoce como «reconocimiento». El reconocimiento libre de contexto para gramáticas en forma normal de Chomsky fue demostrado por Leslie G. Valiant como reducible a la multiplicación de matrices booleanas, heredando así su límite superior de complejidad de O(n^2.3728596).^{[2][Nota 2]}

Por el contrario, Lillian Lee ha demostrado que la multiplicación de matrices booleanas O(n^3−ε) es reducible a un análisis sintáctico de GLC O(n^3−3ε), estableciendo así un límite inferior para este último.^[3]

El uso práctico de los lenguajes libres de contexto también requiere producir un árbol de derivación que muestre la estructura que la gramática asocia con la cadena dada. El proceso de producir este árbol se llama «análisis sintáctico». Los analizadores conocidos tienen una complejidad temporal cúbica en el tamaño de la cadena que se analiza.

Formalmente, el conjunto de todos los lenguajes libres de contexto es idéntico al conjunto de lenguajes aceptados por autómatas de pila (PDA). Los algoritmos de análisis para lenguajes libres de contexto incluyen el algoritmo CYK y el algoritmo de Earley.

Una subclase especial de lenguajes libres de contexto son los lenguajes libres de contexto deterministas, que se definen como el conjunto de lenguajes aceptados por un autómata de pila determinista y pueden ser analizados por un analizador LR(k).^[4]

Véase también gramática de expresiones de análisis como un enfoque alternativo para gramáticas y analizadores.

La clase de lenguajes libres de contexto es cerrada bajo las siguientes operaciones. Es decir, si «L» y «P» son lenguajes libres de contexto, los siguientes lenguajes también son libres de contexto:

• la unión ${\displaystyle L\cup P}$ de «L» y «P»^[5]
• la inversión de «L»^[6]
• la concatenación ${\displaystyle L\cdot P}$ de «L» y «P»^[5]
• la estrella de Kleene ${\displaystyle L^{*}}$ de «L»^[5]
• la imagen ${\displaystyle \varphi (L)}$ de «L» bajo un homomorfismo ${\displaystyle \varphi }$^[7]
• la imagen ${\displaystyle \varphi ^{-1}(L)}$ de «L» bajo un homomorfismo inverso ${\displaystyle \varphi ^{-1}}$^[8]
• el desplazamiento circular de «L» (el lenguaje ${\displaystyle \{vu:uv\in L\}}$)^[9]
• la cerradura de prefijos de «L» (el conjunto de todos los prefijos de cadenas de «L»)^[10]
• el cociente «L»/«R» de «L» por un lenguaje regular «R»^[11]

Los lenguajes libres de contexto no son cerrados bajo intersección. Esto se puede ver al tomar los lenguajes ${\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}$ y ${\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}$, ambos libres de contexto.^{[Nota 3]} Su intersección es ${\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$, que se puede demostrar que no es libre de contexto mediante el lema de bombeo para lenguajes libres de contexto. Como consecuencia, los lenguajes libres de contexto no son cerrados bajo complementación, ya que para cualesquiera lenguajes «A» y «B», su intersección puede expresarse mediante unión y complemento: ${\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}}$. En particular, los lenguajes libres de contexto no son cerrados bajo diferencia, ya que el complemento puede expresarse mediante diferencia: ${\displaystyle {\overline {L}}=\Sigma ^{*}\setminus L}$.^[12]

Sin embargo, si «L» es un lenguaje libre de contexto y «D» es un lenguaje regular, entonces tanto su intersección ${\displaystyle L\cap D}$ como su diferencia ${\displaystyle L\setminus D}$ son lenguajes libres de contexto.^[13]

En la teoría de lenguajes formales, las preguntas sobre lenguajes regulares suelen ser decidibles, pero las de lenguajes libres de contexto a menudo no lo son. Es decidible si un lenguaje de este tipo es finito, pero no si contiene todas las cadenas posibles, si es regular, si es no ambiguo, o si es equivalente a un lenguaje con una gramática diferente.

Los siguientes problemas son indecidibles para gramáticas libres de contexto arbitrariamente dadas A y B:

• Equivalencia: ¿es ${\displaystyle L(A)=L(B)}$?^[14]
• Disyunción: ¿es ${\displaystyle L(A)\cap L(B)=\emptyset }$?^[15] Sin embargo, la intersección de un lenguaje libre de contexto y un lenguaje «regular» es libre de contexto,^[16][17] por lo que la variante del problema donde «B» es una gramática regular es decidible (véase «Vaciedad» más abajo).
• Contención: ¿es ${\displaystyle L(A)\subseteq L(B)}$?^[18] Nuevamente, la variante del problema donde «B» es una gramática regular es decidible,^{[aclaración requerida]} mientras que aquella donde «A» es regular generalmente no lo es.^[19]
• Universalidad: ¿es ${\displaystyle L(A)=\Sigma ^{*}}$?^[20]
• Regularidad: ¿es ${\displaystyle L(A)}$ un lenguaje regular?^[21]
• Ambigüedad: ¿es toda gramática para ${\displaystyle L(A)}$ ambigua?^[22]

Los siguientes problemas son «decidibles» para lenguajes libres de contexto arbitrarios:

• Vaciedad: Dada una gramática libre de contexto «A», ¿es ${\displaystyle L(A)=\emptyset }$?^[23]
• Finidad: Dada una gramática libre de contexto «A», ¿es ${\displaystyle L(A)}$ finito?^[24]
• Pertenencia: Dada una gramática libre de contexto «G» y una palabra ${\displaystyle w}$, ¿es ${\displaystyle w\in L(G)}$? Los algoritmos eficientes en tiempo polinómico para el problema de pertenencia son el algoritmo CYK y el algoritmo de Earley.

Según Hopcroft, Motwani, Ullman (2003),^[25] muchas de las propiedades fundamentales de cierre y (in)decidibilidad de los lenguajes libres de contexto fueron demostradas en el artículo de 1961 de Bar-Hillel, Perles y Shamir.^[26]

El conjunto ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$ es un lenguaje sensible al contexto, pero no existe una gramática libre de contexto que genere este lenguaje.^[27] Por lo tanto, existen lenguajes sensibles al contexto que no son libres de contexto. Para probar que un lenguaje dado no es libre de contexto, se puede emplear el lema del bombeo para lenguajes libres de contexto^[26] o varios otros métodos, como el lema de Ogden o el teorema de Parikh.^[28]