En la teoría del lenguaje formal , un lenguaje sensible al contexto es un lenguaje que puede definirse mediante una gramática sensible al contexto (y, de manera equivalente, mediante una gramática sin contracciones ). El sensible al contexto es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky .
Propiedades computacionales
Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing no determinista delimitada lineal , también llamada autómata limitado lineal . Esa es una máquina de Turing no determinista con una cinta de solo celdas, donde es el tamaño de la entrada y es una constante asociada a la máquina. Esto significa que cada lenguaje formal que puede ser decidido por una máquina de este tipo es un lenguaje sensible al contexto, y cada lenguaje sensible al contexto puede ser decidido por una máquina de este tipo.
Este conjunto de lenguajes también se conoce como NLINSPACE o NSPACE ( O ( n )), porque pueden aceptarse utilizando el espacio lineal en una máquina de Turing no determinista. [1] La clase LINSPACE (o DSPACE ( O ( n ))) se define de la misma manera, excepto que se utiliza una máquina de Turing determinista . Claramente, LINSPACE es un subconjunto de NLINSPACE , pero no se sabe si LINSPACE = NLINSPACE . [2]
Ejemplos de
Uno de los lenguajes sensibles al contexto más simples pero no libres de contexto es : el idioma de todas las cadenas que consta de n apariciones del símbolo "a", luego n "b", luego n "c" (abc, aabbcc, aaabbbccc, etc.). Un superconjunto de este lenguaje, llamado lenguaje de Bach, [3] se define como el conjunto de todas las cadenas donde "a", "b" y "c" (o cualquier otro conjunto de tres símbolos) aparecen con la misma frecuencia (aabccb, baabcaccb , etc.) y también es sensible al contexto. [4] [5]
L puede ser demostrado ser un lenguaje sensible al contexto mediante la construcción de un autómata linealmente acotado que acepta L . El idioma se puede demostrar fácilmente que ser ni regulares ni libre de contexto mediante la aplicación de los respectivos lemas de bombeo para cada una de las clases de idiomas a L .
Similar:
es otro lenguaje sensible al contexto; la gramática sensible al contexto correspondiente se puede proyectar fácilmente comenzando con dos gramáticas libres de contexto que generan formas oracionales en los formatos y y luego complementarlos con una producción de permutación como , un nuevo símbolo inicial y azúcar sintáctico estándar.
es otro idioma sensible al contexto (el "3" en el nombre de este idioma significa un alfabeto ternario); es decir, la operación "producto" define un lenguaje sensible al contexto (pero la "suma" define solo un lenguaje libre de contexto como la gramática y muestra). Debido a la propiedad conmutativa del producto, la gramática más intuitiva paraes ambiguo. Este problema puede evitarse considerando una definición de algún modo más restrictiva del lenguaje, p. Ej.. Esto se puede especializar para y, de esto, a , etc.
es un lenguaje sensible al contexto. La gramática sensible al contexto correspondiente se puede obtener como una generalización de las gramáticas sensibles al contexto para, etc.
es un lenguaje sensible al contexto. [6]
es un idioma sensible al contexto (el "2" en el nombre de este idioma significa un alfabeto binario). Esto fue demostrado por Hartmanis usando lemas de bombeo para lenguajes regulares y sin contexto sobre un alfabeto binario y, después de eso, dibujando un autómata multitape delimitado lineal que acepta. [7]
es un idioma sensible al contexto (el "1" en el nombre de este idioma significa un alfabeto unario). Esto fue acreditado por A. Salomaa a Matti Soittola por medio de un autómata lineal acotado sobre un alfabeto unario [8] (páginas 213-214, ejercicio 6.8) y también a Marti Penttonen por medio de una gramática sensible al contexto también sobre un unario. alfabeto (Ver: Lenguajes formales de A. Salomaa, página 14, Ejemplo 2.5).
Un ejemplo de lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión sea un EXPSPACE -problema difícil, digamos, el conjunto de pares de expresiones regulares equivalentes con exponenciación.
Propiedades de los lenguajes sensibles al contexto
- La unión, intersección, concatenación de dos lenguajes sensibles al contexto es sensible al contexto, también el Kleene plus de un lenguaje sensible al contexto es sensible al contexto. [9]
- El complemento de un lenguaje sensible al contexto es en sí mismo sensible al contexto [10], un resultado conocido como el teorema de Immerman-Szelepcsényi .
- La pertenencia a una cadena en un lenguaje definido por una gramática sensible al contexto arbitraria, o por una gramática sensible al contexto determinista arbitraria, es un problema completo de PSPACE .
Ver también
- Autómata delimitado lineal
- Lista de generadores de analizadores sintácticos para lenguajes sensibles al contexto
- Jerarquía de Chomsky
- Idiomas indexados : un subconjunto estricto de los idiomas sensibles al contexto
- Jerarquía de vertedero
Referencias
- ^ Rothe, Jörg (2005), Teoría de la complejidad y criptología , Textos en informática teórica. An EATCS Series, Berlín: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0, MR 2164257.
- ^ Odifreddi, PG (1999), Teoría de la recursividad clásica. Vol. II , Estudios de lógica y fundamentos de las matemáticas, 143 , Amsterdam: North-Holland Publishing Co., p. 236, ISBN 978-0-444-50205-6, Señor 1718169.
- ^ Pullum, Geoffrey K. (1983). Liberación de contexto y procesamiento informático de lenguajes humanos . Proc. 21ª Reunión Anual de la ACL .
- ^ Bach, E. (1981). " Componentes discontinuos en gramáticas categóricas generalizadas" Archivado el 21 de enero de 2014 en la Wayback Machine . NELS , vol. 11, págs. 1-12.
- ^ Joshi, A .; Vijay-Shanker, K .; y Weir, D. (1991). "La convergencia de formalismos gramaticales ligeramente sensibles al contexto". En: Sells, P., Shieber, SM y Wasow, T. (Editores). Problemas fundamentales en el procesamiento del lenguaje natural . Cambridge MA: Bradford.
- ^ Ejemplo 9.5 (p. 224) de Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas. Addison-Wesley
- ^ J. Hartmanis y H. Shank (julio de 1968). "Sobre el reconocimiento de primas por autómatas" (PDF) . Revista de la ACM . 15 (3): 382–389. doi : 10.1145 / 321466.321470 . hdl : 1813/5864 .
- ^ Salomaa, Arto (1969), Teoría de los autómatas , ISBN 978-0-08-013376-8 , Pergamon, 276 páginas. doi : 10.1016 / C2013-0-02221-9
- ^ John E. Hopcroft; Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley.; Ejercicio 9.10, p.230. En la edición de 2000, se omitió el capítulo sobre lenguajes sensibles al contexto.
- ^ Immerman, Neil (1988). "El espacio no determinista se cierra bajo complementación" (PDF) . SIAM J. Comput . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . doi : 10.1137 / 0217058 .
- Sipser, M. (1996), Introducción a la teoría de la computación , PWS Publishing Co.