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 ), también llamado lenguaje Chomsky tipo 2 , 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.

Fondo

Gramática libre de contexto

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

Autómatas

El conjunto de todos los lenguajes libres de contexto es idéntico al conjunto de lenguajes aceptados por los autómatas de inserción , lo que hace que estos lenguajes sean susceptibles de análisis. Además, para un CFG dado, existe una forma directa de producir un autómata de inserción para la gramática (y, por lo tanto, el lenguaje correspondiente), aunque ir en la dirección opuesta (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 de longitud par no vacías, cuyas primeras mitades son a y cuyas segundas mitades son b . L es generado por la gramática . Este lenguaje no es regular . Lo acepta el autómata de inserción 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 propio de todas las CFL: hay CFL inherentemente ambiguas . Un ejemplo de una CFL inherentemente ambigua es la unión de con . Este conjunto es independiente del contexto, ya que la unión de dos lenguajes independientes del contexto siempre es independiente del contexto. Pero no hay forma de analizar sin ambigüedades las cadenas en el subconjunto (no independiente del 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\}}$

Lenguaje Dyck

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

Propiedades

Análisis sintáctico independiente del contexto

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

La determinación de una instancia del problema de pertenencia; es decir, dada una cadena , determinar si donde 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,3728596 ). ^{[2] [nota 2]} Por el contrario, Lillian Lee ha demostrado que la multiplicación de matrices booleanas O ( n ^3−ε ) se puede reducir al análisis CFG 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 también requieren la producción de 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 denomina análisis sintáctico . Los analizadores sintácticos conocidos tienen una complejidad temporal que es cúbica en relación con 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 de inserción (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 determinista y que pueden ser analizados por un analizador LR(k) . ^[4]

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

Propiedades del 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 lenguajes y , que son ambos libres de contexto. ^{[nota 3]} Su intersección es , 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 pueden cerrarse bajo complementación, ya que para cualquier lenguaje A y B , su intersección puede expresarse por unión y complemento: . En particular, el lenguaje libre de contexto no puede cerrarse bajo diferencia, ya que el complemento puede expresarse por 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 de los lenguajes formales, las cuestiones sobre lenguajes regulares suelen ser decidibles, pero las cuestiones sobre lenguajes independientes del contexto no suelen serlo. Es decidible si un lenguaje de este tipo es finito, pero no si contiene todas las cadenas posibles, si es regular, si es inequívoco o si es equivalente a un lenguaje con una gramática diferente.

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

• Equivalencia: es ? ^[14] ${\displaystyle L(A)=L(B)}$
• Disyunción: ¿es  ? ^[15] Sin embargo, la intersección de un lenguaje libre de contexto y un lenguaje regular es libre de contexto, ^{[16] [17]} por lo tanto, 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 requerida ]} 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 libre de contexto A , es  ? ^[23] ${\displaystyle L(A)=\emptyset }$
• Finitud: Dada una gramática libre de contexto A , ¿es finita? ^[24] ${\displaystyle L(A)}$
• Pertenencia: Dada una gramática G independiente del contexto y una palabra , ¿cumple  ? Los algoritmos de tiempo polinomial eficientes 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), ^[25] muchas de las propiedades fundamentales de cierre y (in)decidibilidad de los lenguajes libres de contexto se demostraron en el artículo de 1961 de Bar-Hillel , Perles y Shamir ^[26].

Idiomas que no son libres de contexto

El conjunto es un lenguaje sensible al contexto , pero no existe una gramática libre del contexto que genere este lenguaje. ^[27] Por lo tanto, existen lenguajes sensibles al contexto que no son libres del contexto. Para demostrar que un lenguaje dado no es libre del contexto, se puede emplear el lema de bombeo para lenguajes libres del 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. Véase Multiplicación de matrices#Complejidad computacional para conocer las mejoras en los límites desde entonces.
3. Una gramática libre de contexto para el lenguaje A está dada por las siguientes reglas de producción, tomando S como símbolo de inicio: 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 sin contexto en un tiempo menor que el cúbico" (PDF) . Journal of Computer and System Sciences . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
3. Lee, Lillian (enero de 2002). "El análisis gramatical rápido sin 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 lenguas de izquierda a derecha". Información y control . 8 (6): 607–639. doi :10.1016/S0019-9958(65)90426-2.
5. Hopcroft & 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. 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 es 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 de autómatas, lenguajes y computación . 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 lenguaje no es libre de contexto?".

Obras citadas

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

Lectura adicional

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Lenguajes libres de contexto y autómatas de inserción". En G. Rozenberg; A. Salomaa (eds.). Handbook of Formal Languages ​​(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, EE. UU.: McGraw-Hill.
• Sipser, Michael (1997). "2: Lenguajes libres de contexto". Introducción a la teoría de la computación . PWS Publishing. pp. 91–122. ISBN 0-534-94728-X.