Hispanopedia Wiki
Articulo de referencia

Lenguaje libre de contexto

En la teoría del lenguaje formal , un lenguaje libre de contexto ( CFL, por sus siglas en inglés), también llamado lenguaje de tipo Chomsky 2 , es un lenguaje generado por una g...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría del lenguaje formal , un lenguaje libre de contexto ( CFL, por sus siglas en inglés), también llamado lenguaje de tipo Chomsky 2 , es un lenguaje generado por una gramática libre de contexto (CFG, por sus siglas en inglés).

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 del lenguaje se pueden distinguir de las propiedades extrínsecas de una gramática particular comparando varias gramáticas que describen dicho 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 pila , lo que hace que estos lenguajes sean susceptibles de análisis sintáctico. Además, para una gramática libre de contexto dada, existe una forma directa de producir un autómata de pila para la gramática (y, por lo tanto, el lenguaje correspondiente), aunque el proceso inverso (producir una gramática a partir de un autómata) no es tan directo.

Ejemplos

Un ejemplo de lenguaje libre de contexto esL={anortebnorte:norte≥1}{\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}, el lenguaje de todas las cadenas no vacías de longitud par, cuyas primeras mitades completas son 'a ', y cuyas segundas mitades completas son 'b '. L es generado por la gramáticaS→aSb | ab{\displaystyle S\to aSb~|~ab}Este lenguaje no es regular. Es aceptado por el autómata de pila.METRO=({q0,q1,qF},{a,b},{a,z},δ,q0,z,{qF}){\textstyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}dóndeδ{\displaystyle \delta }se define de la siguiente manera: [ nota 1 ]

δ(q0,a,z)=(q0,az)δ(q0,a,a)=(q0,aa)δ(q0,b,a)=(q1,ε)δ(q1,b,a)=(q1,ε)δ(q1,ε,z)=(qF,ε){\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 CFL no ambiguos son un subconjunto propio de todos los CFL: existen CFL inherentemente ambiguos. Un ejemplo de un CFL inherentemente ambiguo es la unión de{anortebmetrodometrodnorte|norte,metro>0}{\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}con{anortebnortedometrodmetro|norte,metro>0}{\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 manera de analizar sin ambigüedad las cadenas en el subconjunto (no libre de contexto).{anortebnortedonortednorte|norte>0}{\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}que es la intersección de estos dos lenguajes. [ 1 ]

Lenguaje de Dyck

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

Propiedades

Análisis sintáctico sin contexto

La naturaleza independiente del contexto del lenguaje facilita su análisis sintáctico mediante un autómata de pila.

Determinar una instancia del problema de pertenencia ; es decir, dada una cadenaw{\displaystyle w}determinar siw∈L(GRAMO){\displaystyle w\in L(G)}dóndeL{\displaystyle L}es el lenguaje generado por una gramática dadaGRAMO{\displaystyle G}; también se conoce como reconocimiento . Leslie G. Valiant demostró que el reconocimiento libre de contexto para 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 sintáctico de CFG O ( n 3−3ε ), estableciendo así algún tipo de límite inferior para este último. [ 3 ]

El uso práctico de los lenguajes libres de contexto también requiere la generación de un árbol de derivación que muestre la estructura que la gramática asocia con la cadena dada. El proceso de generación de este árbol se denomina análisis sintáctico . Los analizadores sintácticos conocidos tienen una complejidad temporal cúbica con respecto al tamaño de la cadena analizada.

Formalmente, el conjunto de todos los lenguajes libres de contexto es idéntico al conjunto de lenguajes aceptados por los autómatas de pila (PDA). Los algoritmos de análisis sintáctico 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 que pueden ser analizados por un analizador LR(k) . [ 4 ]

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

Propiedades de cierre

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 lo son:

No cierre bajo intersección, complemento y diferencia

Los lenguajes libres de contexto no son cerrados bajo la intersección. Esto se puede ver tomando los lenguajesA={anortebnortedometro∣metro,norte≥0}{\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}yB={ametrobnortedonorte∣metro,norte≥0}{\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}, que son ambas independientes del contexto. [ nota 3 ] Su intersección esA∩B={anortebnortedonorte∣norte≥0}{\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}, que puede demostrarse 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 ser cerrados bajo complementación, ya que para cualesquiera lenguajes A y B , su intersección puede expresarse mediante unión y complemento: A∩B=A¯∪B¯¯{\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}}. En particular, el lenguaje libre de contexto no puede ser cerrado bajo la diferencia, ya que el complemento puede expresarse mediante la diferencia:L¯=Σ∗∖L{\displaystyle {\overline {L}}=\Sigma ^{*}\setminus L}. [ 12 ]

Sin embargo, si L es un lenguaje libre de contexto y D es un lenguaje regular, entonces su intersecciónL∩D{\displaystyle L\cap D}y su diferenciaL∖D{\displaystyle L\setminus D}son lenguajes libres de contexto. [ 13 ]

Decidibilidad

En la teoría del lenguaje formal, las cuestiones relativas a los lenguajes regulares suelen ser decidibles, pero las relativas a los 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 A y B dadas arbitrariamente:

  • Equivalencia: esL(A)=L(B){\displaystyle L(A)=L(B)}¿ [ 14 ]
  • Desunión: esL(A)∩L(B)=∅{\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 tanto, la variante del problema donde B es una gramática regular es decidible (ver "Vacío" más adelante).
  • Contención: esL(A)⊆L(B){\displaystyle L(A)\subseteq L(B)} [ 18 ] Nuevamente, la variante del problema donde B es una gramática regular es decidible, mientras que aquella donde A es regular generalmente no lo es . [ 19 ]
  • Universalidad: esL(A)=Σ∗{\displaystyle L(A)=\Sigma ^{*}}¿ [ 20 ]
  • Regularidad: esL(A){\displaystyle L(A)}¿Un lenguaje regular? [ 21 ]
  • Ambigüedad: ¿es cada gramática paraL(A){\displaystyle L(A)}¿ambiguo? [ 22 ]

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

  • Vacío: Dada una gramática libre de contexto A , esL(A)=∅{\displaystyle L(A)=\emptyset } ¿ [ 23 ]
  • Finitud: Dada una gramática libre de contexto A , esL(A){\displaystyle L(A)}¿finito? [ 24 ]
  • Membresía: Dada una gramática libre de contexto G y una palabraw{\displaystyle w}, hacew∈L(GRAMO){\displaystyle w\in L(G)} Los algoritmos eficientes de tiempo polinomial para el problema de pertenencia son el algoritmo CYK y el algoritmo de Earley .

Según Hopcroft , Motwani , Ullman (2006), [ 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 ]

Lenguajes que no son libres de contexto

El conjunto{anortebnortedonortednorte|norte>0}{\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 demostrar que un lenguaje dado no es 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 ]

Notas

  1. ↑ significado deδ{\displaystyle \delta }sus argumentos y resultados:δ(statmi1,rmiad,pagopag)=(statmi2,pagtúsh){\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 la mejor cota superior conocida hasta entonces. Véase Multiplicación de matrices#Complejidad computacional para ver las mejoras en las cotas 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 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 1975 .
  3. ↑ Lee 2002 .
  4. ↑ Knuth 1965 .
  5. 1 2 3 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ágs. 131-132, Corolario del Teorema 6.2.
  8. ↑ Hopcroft y Ullman 1979 , pág. 132, Teorema 6.3.
  9. ↑ Hopcroft y Ullman 1979 , págs. 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. ↑ Scheinberg 1960 .
  13. ↑ Beigel y Gasarch .
  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. 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. ^ Bar -Hillel, Perles y Shamir 1961 .
  26. ↑ Hopcroft y Ullman 1979 .
  27. ↑ Stack Exchange. "¿Cómo demostrar que un lenguaje no es libre de contexto? "

Obras citadas

  • Bar-Hillel, Yehoshua ; Perles, Micha Asher; Shamir, Eli (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 .
  • Beigel, Richard; Gasarch, William . "Una prueba de que si L = L1 ∩ L2 donde L1 es CFL y L2 es Regular, entonces L es Context Free que no utiliza PDA" (PDF) . Departamento de Ciencias de la Computación de la Universidad de Maryland . Archivado (PDF) del original el 12 de diciembre de 2014. Recuperado el 6 de junio de 2020 .
  • 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 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
  • Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª  ed.). Addison-Wesley. ISBN 0-321-45536-3.
  • Knuth, DE (julio de 1965). "Sobre la traducción de lenguas de izquierda a derecha". Information and Control . 8 (6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .
  • Lee, Lillian (enero de 2002). "El análisis rápido de gramáticas libres 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) del original el 27 de abril de 2003. 
  • Salomaa, Arto (1973). Lenguajes formales . Serie de monografías de la ACM. Nueva York: Academic Press. ISBN 978-0126157505.
  • Scheinberg, Stephen (1960). «Nota sobre las propiedades booleanas de los lenguajes libres de contexto» (PDF) . Information and Control . 3 (4): 372–375 . doi : 10.1016/s0019-9958(60)90965-7 . Archivado (PDF) del original el 26 de noviembre de 2018.
  • Valiant, Leslie G. (abril de 1975). "Reconocimiento general libre de contexto en menos de tiempo cúbico" (PDF) . Journal of Computer and System Sciences . 10 (2): 308– 315. doi : 10.1016/s0022-0000(75)80046-8 .

Lecturas adicionales

  • Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). «Lenguajes libres de contexto y autómatas de pila». En G. Rozenberg; A. Salomaa (eds.). Manual de lenguajes formales (PDF) . Vol.  1. Springer-Verlag. pp. 111–174 . Archivado (PDF) del 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 (1.ª  ed.). PWS Publishing. págs. 91–122 . ISBN  978-0-534-94728-6.( Accesible para usuarios con discapacidades visuales )