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.
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 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 lenguaje correspondiente), aunque ir en el sentido contrario (producir una gramática dada un autómata) no es tan directo.
Ejemplos de
Un ejemplo de lenguaje libre de contexto es , el idioma de todas las cadenas de longitud uniforme no vacías, cuyas primeras mitades completas 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 pushdown dónde se define de la siguiente manera: [nota 1]
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 con . 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 cadenas de forma inequívoca en el subconjunto (sin contexto)que es la intersección de estos dos lenguajes. [1]
Lenguaje Dyck
El lenguaje de todos los paréntesis correctamente emparejados es generado por la gramática.
Propiedades
Análisis sin contexto
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, determinar si dónde es el lenguaje generado por una gramática determinada ; 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 demostrado que la multiplicación de matrices booleanas O ( n 3 − ε ) es reducible a O ( n 3−3ε ) análisis sintáctico CFG, 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:
- el sindicato de L y P [5]
- la inversión de L [6]
- la concatenación de L y P [5]
- la estrella de Kleene de L [5]
- la imagen de L bajo un homomorfismo [7]
- la imagen de L bajo un homomorfismo inverso [8]
- el desplazamiento circular de L (el lenguaje) [9]
- 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, 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 se puede cerrar bajo diferencia, ya que el complemento se puede expresar por diferencia:. [12]
Sin embargo, si L es un lenguaje libre de contexto y D es un lenguaje regular, entonces su intersección y su diferencia son lenguajes libres de contexto. [13]
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.
Los siguientes problemas son indecidibles para las gramáticas A y B libres de contexto dadas arbitrariamente :
- Equivalencia: es ? [14]
- 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] por lo tanto, la variante del problema donde B es una gramática regular es decidible (ver "Vacuidad" más abajo).
- Contención: es ? [18] 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. [19]
- Universalidad: es ? [20]
- Regularidad: es un idioma regular? [21]
- Ambigüedad: es toda gramática para ¿ambiguo? [22]
Los siguientes problemas son decidibles para lenguajes arbitrarios sin contexto:
- Vacío: dada una gramática A libre de contexto , es ? [23]
- Finitud: dada una gramática A libre de contexto , es¿finito? [24]
- Membresía: dada una gramática G libre de contexto y una palabra, lo hace ? Los algoritmos eficientes de tiempo polinómico para el problema de pertenencia son el algoritmo CYK y el algoritmo de Earley .
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] Por tanto, existen lenguajes sensibles al contexto que no están libres de contexto. Para demostrar que un lenguaje dado 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]
Notas
- ^ significado deArgumentos y resultados:
- ↑ 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.
- ^ 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
- ^ Hopcroft y Ullman 1979 , p. 100, teorema 4.7.
- ↑ 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.
- ^ 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 .
- ^ 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 .
- ↑ a b c Hopcroft y Ullman , 1979 , p. 131, Corolario del teorema 6.1.
- ^ Hopcroft y Ullman 1979 , p. 142, ejercicio 6.4d.
- ^ Hopcroft y Ullman 1979 , p. 131-132, Corolario del teorema 6.2.
- ^ Hopcroft y Ullman 1979 , p. 132, Teorema 6.3.
- ^ Hopcroft y Ullman 1979 , p. 142-144, ejercicio 6.4c.
- ^ Hopcroft y Ullman 1979 , p. 142, ejercicio 6.4b.
- ^ Hopcroft y Ullman 1979 , p. 142, Ejercicio 6.4a.
- ^ 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 .
- ^ 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 .
- ^ Hopcroft y Ullman 1979 , p. 203, Teorema 8.12 (1).
- ^ Hopcroft y Ullman 1979 , p. 202, Teorema 8.10.
- ^ Salomaa (1973) , p. 59, teorema 6.7
- ^ Hopcroft y Ullman 1979 , p. 135, Teorema 6.5.
- ^ Hopcroft y Ullman 1979 , p. 203, Teorema 8.12 (2).
- ^ Hopcroft y Ullman 1979 , p. 203, Teorema 8.12 (4).
- ^ Hopcroft y Ullman 1979 , p. 203, Teorema 8.11.
- ^ Hopcroft y Ullman 1979 , p. 205, Teorema 8.15.
- ^ Hopcroft y Ullman 1979 , p. 206, Teorema 8.16.
- ^ Hopcroft y Ullman 1979 , p. 137, Teorema 6.6 (a).
- ^ Hopcroft y Ullman 1979 , p. 137, Teorema 6.6 (b).
- ^ 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
- ^ a b 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.
- ^ Hopcroft y Ullman, 1979 .
- ^ ¿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.
- Salomaa, Arto (1973). Idiomas formales . Serie de monografías ACM.
Otras lecturas
- 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.