Lenguaje libre de contexto

Lenguaje formal generado por gramática libre de contexto.

En la teoría del lenguaje formal , 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 se generan mediante gramáticas libres de contexto.

Fondo

Gramática libre de contexto

Diferentes gramáticas libres de contexto pueden generar el mismo lenguaje libre de contexto. Las propiedades intrínsecas de la lengua se pueden distinguir de las propiedades extrínsecas de una gramática particular comparando varias gramáticas que describen la lengua.

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 sean susceptibles de análisis. Además, para un CFG determinado, existe una manera directa de producir un autómata pushdown para la gramática (y por lo tanto el lenguaje correspondiente), aunque ir en sentido contrario (producir una gramática dado un autómata) no es tan directo.

Ejemplos

Un ejemplo de lenguaje libre de contexto es , el lenguaje de todas las cadenas no vacías de longitud par, cuyas primeras mitades son a y las segundas mitades son b . L es generado por la gramática . Este lenguaje no es regular . Es aceptado por el autómata pushdown donde se define de la siguiente manera: ^{[nota 1]} ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$ ${\displaystyle S\to aSb~|~ab}$ ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}$ ${\displaystyle \delta }$

${\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}}}$

Las LFC inequívocas son un subconjunto adecuado de todas las LFC: existen LFC intrínsecamente ambiguas . Un ejemplo de CFL inherentemente ambigua es la unión de con . Este conjunto está libre de contexto, ya que la unión de dos lenguajes libres de contexto siempre está libre de contexto. Pero no hay manera de analizar cadenas sin ambigüedades en el subconjunto (no libre de contexto) que es la intersección de estos dos lenguajes. ^[1] ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}$ ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}$ ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$

idioma Dyck

La gramática genera el lenguaje de todos los paréntesis que coinciden correctamente . ${\displaystyle S\to SS~|~(S)~|~\varepsilon }$

Propiedades

Análisis sin contexto

La naturaleza libre de contexto del lenguaje hace que sea sencillo de analizar con un autómata pushdown.

Determinar un caso del problema de membresía; es decir, dada una cadena , determina si dónde está el lenguaje generado por una gramática determinada ; También se le conoce como reconocimiento . Leslie G. Valiant demostró que el reconocimiento libre de contexto de las gramáticas de forma normal de Chomsky es 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 al análisis CFG de O ( n ^3−3ε ), estableciendo así algún tipo de límite inferior para este último. ^[3] ${\displaystyle w}$ ${\displaystyle w\in L(G)}$ ${\displaystyle L}$ ${\displaystyle G}$

Los usos prácticos de los lenguajes libres de contexto requieren también 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 . 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 los autómatas pushdown (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 deterministas libres de contexto que se definen como el conjunto de lenguajes aceptados por un autómata pushdown determinista y pueden ser analizados por un analizador LR(k) . ^[4]

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 con las siguientes operaciones. Es decir, si L y P son lenguajes libres de contexto, los siguientes lenguajes también lo son:

• la unión de L y P ^[5] ${\displaystyle L\cup P}$
• la inversión de L ^[6]
• la concatenación de L y P ^[5] ${\displaystyle L\cdot P}$
• la estrella Kleene de L ^[5] ${\displaystyle L^{*}}$
• la imagen de L bajo un homomorfismo ^[7] ${\displaystyle \varphi (L)}$ ${\displaystyle \varphi }$
• la imagen de L bajo un homomorfismo inverso ^[8] ${\displaystyle \varphi ^{-1}(L)}$ ${\displaystyle \varphi ^{-1}}$
• el desplazamiento circular de L (el lenguaje ) ^[9] ${\displaystyle \{vu:uv\in L\}}$
• el cierre de prefijo 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]

No cierre bajo intersección, complemento y diferencia.

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

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

Decidibilidad

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

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

• Equivalencia: es ? ^[14] ${\displaystyle L(A)=L(B)}$
• Desarticulación: es  ? ^[15] Sin embargo, la intersección de un lenguaje libre de contexto y un lenguaje regular es libre de contexto, ^{[16] [17]} de ahí que la variante del problema donde B es una gramática regular es decidible (ver "Vacío" a continuación). ${\displaystyle L(A)\cap L(B)=\emptyset }$
• Contención: ¿es  ? ^[18] Nuevamente, la variante del problema donde B es una gramática regular es decidible, ^{[ cita necesaria ]} mientras que aquella donde A es regular generalmente no lo es. ^[19] ${\displaystyle L(A)\subseteq L(B)}$
• Universalidad: ¿es ? ^[20] ${\displaystyle L(A)=\Sigma ^{*}}$
• Regularidad: ¿es un lenguaje regular? ^[21] ${\displaystyle L(A)}$
• Ambigüedad: ¿toda gramática es ambigua? ^[22] ${\displaystyle L(A)}$

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

• Vacío: Dada una gramática A libre de contexto , ¿es  ? ^[23] ${\displaystyle L(A)=\emptyset }$
• Finitud: Dada una gramática A libre de contexto , ¿es finita? ^[24] ${\displaystyle L(A)}$
• Membresía: Dada una gramática libre de contexto G y una palabra , ¿lo hace  ? Los algoritmos de tiempo polinomial eficientes para el problema de membresía son el algoritmo CYK y el algoritmo de Earley . ${\displaystyle w}$ ${\displaystyle w\in L(G)}$

Según Hopcroft, Motwani, Ullman (2003), ^[25] 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 ^[26].

Idiomas que no están libres de contexto

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

Notas

1. significado de los argumentos y resultados de: ${\displaystyle \delta }$ ${\displaystyle \delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )}$
2. En el artículo de Valiant, O ( n ^2.81 ) era el límite superior más conocido en ese momento. Consulte Multiplicación de matrices # Complejidad computacional para conocer las mejoras vinculadas desde entonces.
3. Una gramática libre de contexto para el idioma A viene dada por las siguientes reglas de producción, tomando S como símbolo inicial: S → Sc | aTB | ε ; T → aTb | ε . La gramática para B es análoga.

Referencias

1. Hopcroft y Ullman 1979, pág. 100, Teorema 4.7.
2. Valiant, Leslie G. (abril de 1975). "Reconocimiento general libre de contexto en menos de tiempo cúbico" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
3. Lee, Lillian (enero de 2002). "El análisis gramatical rápido y libre de contexto requiere una multiplicación rápida de matrices booleanas" (PDF) . J.ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491. Archivado (PDF) desde el original el 27 de abril de 2003.
4. Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha". Información y Control . 8 (6): 607–639. doi :10.1016/S0019-9958(65)90426-2.
5. Hopcroft y Ullman 1979, pág. 131, Corolario del Teorema 6.1.
6. Hopcroft y Ullman 1979, pág. 142, Ejercicio 6.4d.
7. Hopcroft y Ullman 1979, pág. 131-132, Corolario del Teorema 6.2.
8. Hopcroft y Ullman 1979, pág. 132, Teorema 6.3.
9. Hopcroft y Ullman 1979, pág. 142-144, Ejercicio 6.4c.
10. Hopcroft y Ullman 1979, pág. 142, Ejercicio 6.4b.
11. Hopcroft y Ullman 1979, pág. 142, Ejercicio 6.4a.
12. Stephen Scheinberg (1960). "Nota sobre las propiedades booleanas de los lenguajes libres de contexto" (PDF) . Información y Control . 3 (4): 372–375. doi : 10.1016/s0019-9958(60)90965-7 . Archivado (PDF) desde el original el 26 de noviembre de 2018.
13. Beigel, Richard; Gasarch, William. "Una prueba de que si L = L1 ∩ L2 donde L1 es CFL y L2 es regular, entonces L está libre de contexto y no utiliza PDA" (PDF) . Departamento de Ciencias de la Computación de la Universidad de Maryland . Archivado (PDF) desde el original el 12 de diciembre de 2014 . Consultado el 6 de junio de 2020 .
14. Hopcroft y Ullman 1979, pág. 203, Teorema 8.12(1).
15. Hopcroft y Ullman 1979, pág. 202, Teorema 8.10.
16. Salomaa (1973), pág. 59, Teorema 6.7
17. Hopcroft y Ullman 1979, pág. 135, Teorema 6.5.
18. Hopcroft y Ullman 1979, pág. 203, Teorema 8.12(2).
19. Hopcroft y Ullman 1979, pág. 203, Teorema 8.12(4).
20. Hopcroft y Ullman 1979, pág. 203, Teorema 8.11.
21. Hopcroft y Ullman 1979, pág. 205, Teorema 8.15.
22. Hopcroft y Ullman 1979, pág. 206, teorema 8.16.
23. Hopcroft y Ullman 1979, pág. 137, Teorema 6.6(a).
24. Hopcroft y Ullman 1979, pág. 137, Teorema 6.6(b).
25. John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introducción a la teoría, los lenguajes y la computación de autómatas . Addison Wesley.Aquí: Sec.7.6, p.304, y Sec.9.7, p.411
26. Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). "Sobre las propiedades formales de las gramáticas de estructura de frases simples". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143-172.
27. Hopcroft y Ullman 1979.
28. "¿Cómo demostrar que un idioma no está libre de contexto?".

Trabajos citados

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Addison-Wesley. ISBN 9780201029888.
• Salomaa, Arto (1973). Lenguajes formales . Serie de monografías ACM.

Otras lecturas

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Lucas (1997). "Lenguajes libres de contexto y autómatas push-down". En G. Rozenberg; A. Salomaa (eds.). Manual de lenguajes formales (PDF) . vol. 1. Springer-Verlag. págs. 111-174. Archivado (PDF) desde el original el 16 de mayo de 2011.
• Ginsburg, Seymour (1966). La teoría matemática de los lenguajes libres de contexto . Nueva York, NY, Estados Unidos: McGraw-Hill.
• Sipser, Michael (1997). "2: Idiomas libres de contexto". Introducción a la Teoría de la Computación . Publicación PWS. págs. 91-122. ISBN 0-534-94728-X.