Lenguaje 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 son generadas por gramáticas libres de contexto.

Antecedentes

Gramática libre de contexto

Diferentes gramáticas libres de contexto pueden generar el mismo lenguaje libre de contexto. Las propiedades intrínsecas del idioma se pueden distinguir de las propiedades extrínsecas de una gramática en 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 dada un autómata) no es tan directo.

Ejemplos

Un ejemplo de lenguaje libre de contexto es el lenguaje de todas las cadenas de longitud uniforme no vacías, cuyas primeras mitades enteras son a , y las segundas mitades completas son b . L es generado por la gramática . Este idioma no es regular . Es aceptado por el autómata de empuje 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 CFL inequívocas son un subconjunto adecuado de todas las CFL: hay CFL intrínsecamente ambiguas . Un ejemplo de una CFL intrínsecamente ambigua es la unión de with . Este conjunto está libre de contexto, ya que la unión de dos lenguajes libres de contexto es siempre libre de contexto. Pero no hay forma de analizar sin ambigüedades cadenas en el subconjunto (sin 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 correctamente emparejados .${\displaystyle S\to SS~|~(S)~|~\varepsilon }$

Propiedades

Análisis sin contexto

Artículo principal: Análisis

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

Determinar una instancia del problema de membresía ; es decir, dada una cadena , determine si dónde está el lenguaje generado por una gramática dada ; también se conoce como reconocimiento . Leslie G. Valiant demostró que el reconocimiento libre de contexto para las gramáticas de forma normal de Chomsky se puede reducir a la multiplicación de matrices booleanas , heredando así su límite superior de complejidad de O ( n ^2,3728639 ). ^{[2] [nota 2]} A la inversa, Lillian Lee ha mostrado O ( n ^{3 − ε}${\displaystyle w}$${\displaystyle w\in L(G)}$${\displaystyle L}$${\displaystyle G}$) multiplicación de matrices booleanas para ser reducible a análisis sintáctico CFG O ( n ^3−3ε ), estableciendo así algún tipo de límite inferior para este último. ^[3]

Los usos prácticos de lenguajes libres de contexto también requieren producir un árbol de derivación que exhiba la estructura que la gramática asocia con la cadena dada. El proceso de producción de este árbol se llama análisis sintáctico . 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 deterministas libres de contexto que se definen como el conjunto de lenguajes aceptados por un autómata pushdown determinista y que pueden ser analizados por un analizador sintáctico LR (k) . ^[4]

Consulte también analizar la gramática de expresiones como un enfoque alternativo a la gramática y el analizador.

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 idioma ) ^[9]${\displaystyle \{vu:uv\in L\}}$
• el prefijo de cierre 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 por intersección, complemento y diferencia

Los lenguajes libres de contexto no se cierran bajo intersección. Esto se puede ver tomando los idiomas y , que son ambos libres de contexto. ^{[nota 3]} Su intersección es , que puede demostrarse que no está libre de contexto por el lema de bombeo para lenguajes libres de contexto . Como consecuencia, lenguajes independientes del contexto no se pueden cerrar en virtud de complementación, como para cualquier lenguaje de A y B , su intersección se puede expresar mediante la unión y el complemento: . En particular, el lenguaje libre de contexto no se puede cerrar en virtud de diferencia, ya que el complemento se puede expresar mediante la 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 los lenguajes regulares suelen ser decidibles, pero las preguntas sobre los lenguajes libres de contexto a menudo no lo son. Se puede decidir si un lenguaje así 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. ^[14]

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

• Equivalencia: ¿ es ? ^[15]${\displaystyle L(A)=L(B)}$
• Desarticulación:  ¿ es ? ^[16] Sin embargo, la intersección de un lenguaje libre de contexto y un lenguaje regular es libre de contexto, ^{[17] [18]} por lo tanto, la variante del problema donde B es una gramática regular es decidible (ver "Vacuidad" más abajo).${\displaystyle L(A)\cap L(B)=\emptyset }$
• Contención:  ¿ es ? ^[19] Nuevamente, la variante del problema donde B es una gramática regular es decidible, ^{[ cita requerida ]} mientras que donde A es regular generalmente no lo es. ^[20]${\displaystyle L(A)\subseteq L(B)}$
• Universalidad:  ¿ es ? ^[21]${\displaystyle L(A)=\Sigma ^{*}}$

Los siguientes problemas son decidibles para lenguajes arbitrarios sin contexto:

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

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

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. ^[26] Por tanto, existen lenguajes sensibles al contexto que no están libres de contexto. Para probar que un lenguaje dado no está libre de contexto, se puede emplear el lema de bombeo para lenguajes libres de contexto ^[25] o varios otros métodos, como el lema de Ogden o el teorema de Parikh . ^[27]${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$

Notas

1. significado delos 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 los algoritmos de multiplicación de matrices # para una multiplicación de matrices eficiente y el algoritmo de Coppersmith-Winograd para obtener mejoras en los límites desde entonces.
3. Una gramática libre de contexto para el lenguaje A viene dada por las siguientes reglas de producción, tomando S como símbolo de inicio: S → Sc | aTb | ε ; T → aTb | ε . La gramática de B es análoga.

Referencias

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

Obras citadas

• 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.
• Salomaa, Arto (1973). Idiomas formales . Serie de monografías ACM.

Lectura adicional

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