Lenguaje libre de contexto

En la teoría formal del lenguaje, un lenguaje libre de contexto (CFL) es un lenguaje generado por una gramática libre de contexto (CFG).

Los lenguajes libres de contexto tienen muchas aplicaciones en los lenguajes de programación, en particular, la mayoría de las expresiones aritméticas son generadas por gramáticas libres de contexto.

Antecedentes

Gramática independiente del contexto

Diferentes gramáticas independientes del contexto pueden generar el mismo lenguaje independiente del contexto. Las propiedades intrínsecas del idioma se pueden distinguir de las propiedades extrínsecas de una gramática particular comparando múltiples gramáticas que describen el idioma.

Autómatas

El conjunto de todos los lenguajes libres de contexto es idéntico al conjunto de lenguajes aceptados por los autómatas pushdown, lo que hace que estos lenguajes se puedan analizar. Además, para un CFG dado, hay una forma directa de producir un autómata pushdown para la gramática (y, por lo tanto, el idioma correspondiente), aunque ir en sentido contrario (producir una gramática dado un autómata) no es tan directo.

Ejemplos

Un ejemplo de lenguaje sin contexto es ${displaystyle L={a^{n}b^{n}:ngeq #$, el lenguaje de todas las cadenas de longitud no vacías, las primeras mitades de las cuales son a's, y las segundas mitades de las cuales son bEs. L se genera por la gramática ${displaystyle Sto aSb~$. Este idioma no es regular. Es aceptado por el automatizado de empuje ${displaystyle M=({q_{0},q_{1},{a,b},{a,z},deltaq_{0},z,{q_{f}}) }$ Donde ${displaystyle delta }$ se define como sigue:

${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft Sans Serif} {cH0} {cH0} {cH0}cH00}cH0}cH00}cH0cH00}cH0cH0cH00}$

Las CFL inequívocas son un subconjunto adecuado de todas las CFL: existen CFLs inherentemente ambiguas. Un ejemplo de una CFL ambigua inherentemente es la unión de ${displaystyle {a^{n}b^{m}c^{m}d^{n} animadon,m título0}$ con ${displaystyle {a^{n}b^{n}c^{m}d^{m} animadon,m título0}$. Este conjunto es libre de contexto, ya que la unión de dos idiomas libres de contexto es siempre libre de contexto. Pero no hay manera de analizar sin ambigüedades las cuerdas en el subconjunto (sin texto) ${displaystyle {a^{n}b^{n}c^{n}d^{n} {n} {fn}}}$ que es la intersección de estos dos idiomas.

Lenguaje Dyck

El lenguaje de todos los paréntesis correctamente emparejados es generado por la gramática ${displaystyle Sto SS~ sobre la vida...$.

Propiedades

Análisis sin contexto

La naturaleza independiente del contexto del lenguaje hace que sea fácil de analizar con un autómata pushdown.

Determinar una instancia del problema de la membresía; es decir, dada una cadena ${displaystyle w}$, determinar si ${displaystyle win L(G)}$ Donde ${displaystyle L.$ es el idioma generado por una gramática dada ${displaystyle G.$; también se conoce como reconocimiento. El reconocimiento sin texto para las gramáticas normales de forma Chomsky fue demostrado por Leslie G. Valiant para ser reducible a la multiplicación de matriz booleana, herediendo así su complejidad superior límite de O(n^2.3728596). Por el contrario, Lillian Lee ha demostrado O()n^3−ε) multiplicación de matriz booleana para ser reducible a O()n^{3 a 3 años}) CFG parsing, estableciendo así algún tipo de límite inferior para este último.

Los usos prácticos de lenguajes libres de contexto también requieren producir un árbol de derivación que muestre la estructura que la gramática asocia con la cadena dada. El proceso de producción de este árbol se llama análisis. Los analizadores conocidos tienen una complejidad de tiempo que es 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 los autómatas pushdown (PDA). Los algoritmos de analizador 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 pushdown determinista y pueden ser analizados por un analizador LR(k).

Véase también análisis de la gramática de expresiones como un enfoque alternativo a la gramática y el analizador.

Propiedades de cierre

La clase de lenguajes libres de contexto se cierra bajo las siguientes operaciones. Es decir, si L y P son lenguajes independientes del contexto, los siguientes lenguajes también lo son:

• el sindicato ${displaystyle Lcup P}$ de L y P
• la inversión de L
• la concatenación ${displaystyle Lcdot P}$ de L y P
• la estrella Kleene ${displaystyle L^{*}$ de L
• la imagen ${displaystyle varphi (L)}$ de L bajo un homomorfismo ${displaystyle varphi }$
• la imagen ${displaystyle varphi ^{-1}(L)}$ de L bajo un homomorfismo inverso ${displaystyle varphi ^{-1}$
• el cambio circular L (el idioma ${displaystyle {vu:uvin L.$)
• el cierre prefijo de L (el conjunto de todos los prefijos de cadenas de L)
• el cociente L/R de L por idioma regular R

No cierre bajo intersección, complemento y diferencia

Los idiomas sin contexto no están cerrados por intersección. Esto se puede ver tomando los idiomas ${displaystyle A={a^{n}b^ {n}c^{m}mid m,ngeq 0}$ y ${displaystyle B={a^{m}b^{n}mid m,ngeq 0}$, que son ambos libres de contexto. Su intersección es ${displaystyle Acap B={a^{n}c^{n}mid ngeq 0}$, que se puede demostrar que no está libre de texto por el lema de bombeo para idiomas sin contexto. Como consecuencia de ello, los idiomas libres de contexto no pueden cerrarse en forma de complemento, en cuanto a los idiomas A y B, su intersección se puede expresar por unión y complemento: ${displaystyle Acap B={overline {fnK}cup {fnK}} {fnK}}} {fn}} {fn} {fn} {fn}}} {fn}}} {fn}}}} {fn}}}} {f}}}} {f} {fn}}}}}}}}} {}}}}}}} {}}}}}}}}}}}} {}}}}}}}}}}}} {}}}}}}}}}}}}}}} {f}}}} {}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}} {f}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$. En particular, el lenguaje libre de contexto no puede cerrarse bajo diferencia, ya que el complemento puede expresarse por diferencia: ${displaystyle {overline {}=Sigma ^{*}setminus L.$.

Sin embargo, si L es un lenguaje sin contexto y D es un idioma regular entonces ambos su intersección ${displaystyle Lcap D}$ y su diferencia ${displaystyle Lsetminus D}$ son idiomas sin contexto.

Decidibilidad

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

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

• Equivalencia: es ${displaystyle L(A)=L(B)}$?
• La alegría: es ${displaystyle L(A)cap L(B)=emptyset$? Sin embargo, la intersección de un lenguaje sin contexto y una ordinario el lenguaje es libre de contexto, por lo tanto la variante del problema donde B es una gramática regular es decidable (ver "Empezadidad" abajo).
• Contención: es ${displaystyle L(A)subseteq L(B)}$? Una vez más, la variante del problema donde B es una gramática regular es decidable, mientras que allí A es regular no es generalmente.
• Universalidad: es ${displaystyle L(A)= Sigma ^{*}$?
• Regularidad: es ${displaystyle L(A)}$ ¿un idioma regular?
• Ambigüedad: es cada gramática para ${displaystyle L(A)}$ ¿ambiguo?

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

• Vacío: Dada una gramática sin contexto A, es ${displaystyle L(A)=emptyset }$?
• Finitness: Dada una gramática sin contexto A, es ${displaystyle L(A)}$ finito?
• Composición: Dada una gramática sin contexto G, y una palabra ${displaystyle w}$, sí ${displaystyle win L(G)}$? Los algoritmos de tiempo polinomio eficiente para el problema de la membresía son el algoritmo CYK y el algoritmo de Earley.

Según Hopcroft, Motwani, Ullman (2003), muchas de las propiedades fundamentales de cierre y (in)decidibilidad de los lenguajes libres de contexto se mostraron en el artículo de 1961 de Bar-Hillel, Perles y Shamir

Idiomas que no están libres de contexto

El set ${displaystyle {a^{n}b^{n}c^{n}d^{n} {n} {fn}}}$ es un lenguaje sensible al contexto, pero no existe una gramática sin contexto que genere este idioma. Así que existen lenguajes sensibles al contexto que no son libres de contexto. Para demostrar que un idioma dado no es sin contexto, se puede emplear el lema de bombeo para idiomas sin contexto o varios otros métodos, como el lema de Ogden o el teorema de Parikh.