Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing no determinista lineal acotada , también llamada autómata lineal acotado . Es decir, 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 con la máquina. Esto significa que todo lenguaje formal que pueda ser decidido por dicha máquina es un lenguaje sensible al contexto, y todo lenguaje sensible al contexto puede ser decidido por dicha máquina.
Este conjunto de lenguajes también se conoce como NLINSPACE o NSPACE( O ( n )), porque se pueden aceptar 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
Uno de los lenguajes sensibles al contexto más simples, pero no libres de contexto , es el lenguaje de todas las cadenas que constan de n ocurrencias del símbolo "a", luego n "b"s, luego n "c"s (abc, aabbcc, aaabbbccc, etc.). Un superconjunto de este lenguaje, llamado lenguaje 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]
Se puede demostrar que L es un lenguaje sensible al contexto mediante la construcción de un autómata lineal acotado que acepte L. Se puede demostrar fácilmente que el lenguaje no es regular ni libre de contexto mediante la aplicación de los respectivos lemas de bombeo para cada una de las clases de lenguaje a L.
Similarmente:
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
luego complementándolas con una producción de permutación como , un nuevo símbolo de inicio y azúcar sintáctico estándar.
es otro lenguaje sensible al contexto (el "3" en el nombre de este lenguaje pretende significar 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 para es ambigua. Este problema se puede evitar considerando una definición algo más restrictiva del lenguaje, p. ej . . Esto se puede especializar en y , a partir de esto, en , , 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 lenguaje sensible al contexto (el "2" en el nombre de este lenguaje pretende significar un alfabeto binario). Esto fue demostrado por Hartmanis utilizando lemas de bombeo para lenguajes regulares y libres de contexto sobre un alfabeto binario y, después de eso, esbozando un autómata multicinta lineal acotado que acepta . [7]
es un lenguaje sensible al contexto (el "1" en el nombre de este lenguaje pretende significar un alfabeto unario). Esto fue atribuido por A. Salomaa a Matti Soittola mediante un autómata lineal acotado sobre un alfabeto unario [8] (páginas 213-214, ejercicio 6.8) y también a Marti Penttonen mediante una gramática sensible al contexto también sobre un alfabeto unario (Ver: Formal Languages por 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 problema EXPSPACE -hard, digamos, el conjunto de pares de expresiones regulares equivalentes con exponenciación.
Propiedades de los lenguajes sensibles al contexto
La unión , intersección y concatenación de dos lenguajes sensibles al contexto es sensible al contexto, al igual que el Kleene plus de un lenguaje 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 arbitraria sensible al contexto, o por una gramática arbitraria sensible al contexto determinista, es un problema PSPACE-completo .
^ Rothe, Jörg (2005), Teoría de la complejidad y criptología , Textos en informática teórica. Una serie EATCS, Berlín: Springer-Verlag, pág. 77, ISBN978-3-540-22147-0, Sr. 2164257.
^ Odifreddi, PG (1999), Teoría de la recursión clásica. Vol. II , Estudios de lógica y fundamentos de las matemáticas, vol. 143, Ámsterdam: North-Holland Publishing Co., pág. 236, ISBN978-0-444-50205-6, Sr. 1718169.
^ Pullum, Geoffrey K. (1983). Libre de contexto y procesamiento informático de lenguajes humanos. Proc. 21.ª Reunión Anual de la ACL .
^ Bach, E. (1981). "Constituyentes discontinuos en gramáticas categoriales generalizadas" Archivado el 21 de enero de 2014 en 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). Cuestiones 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 de autómatas, lenguajes y computación. Addison-Wesley
^ J. Hartmanis y H. Shank (julio de 1968). "Sobre el reconocimiento de primos por autómatas" (PDF) . Journal of the ACM . 15 (3): 382–389. doi :10.1145/321466.321470. hdl : 1813/5864 . S2CID 17998039.
↑ Salomaa, Arto (1969), Teoría de los autómatas , ISBN 978-0-08-013376-8 , Pérgamo, 276 páginas. doi :10.1016/C2013-0-02221-9
^ John E. Hopcroft; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN9780201029888.; Ejercicio 9.10, p.230. En la edición de 2000 se ha omitido el capítulo sobre lenguajes sensibles al contexto.
^ Immerman, Neil (1988). "El espacio no determinista está cerrado bajo complementación" (PDF) . SIAM J. Comput . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . doi :10.1137/0217058. Archivado (PDF) desde el original el 25 de junio de 2004.
Sipser, M. (1996), Introducción a la teoría de la computación , PWS Publishing Co.