Lenguaje sensible al contexto

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, equivalentemente, mediante una gramática no contráctil ). El lenguaje sensible al contexto se conoce como tipo 1 en la jerarquía de Chomsky de lenguajes formales.

Propiedades computacionales

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. ${\displaystyle kn}$ ${\displaystyle n}$ ${\displaystyle k}$

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]} ${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$

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:

${\displaystyle L_{\textit {Cross}}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$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. ${\displaystyle a^{m}C^{m}}$ ${\displaystyle B^{n}d^{n}}$ ${\displaystyle CB\rightarrow BC}$

${\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}$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. ${\displaystyle S\rightarrow aSc|R}$ ${\displaystyle R\rightarrow bRc|bc}$ ${\displaystyle L_{\textit {MUL3}}}$ ${\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$ ${\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}$ ${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$ ${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$

${\displaystyle L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}}$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. ${\displaystyle L_{\textit {Square}}=\{w^{2}:w\in \Sigma ^{*}\}}$ ${\displaystyle L_{\textit {Cube}}=\{w^{3}:w\in \Sigma ^{*}\}}$

${\displaystyle L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}}$Es un lenguaje sensible al contexto. ^[6]

${\displaystyle L_{\textit {PRIMES2}}=\{w:|w|{\mbox{ is prime }}\}}$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] ${\displaystyle L_{PRIMES2}}$

${\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}$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 .

Véase también

• Autómata lineal acotado
• 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 Weir

Referencias

1. 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, ISBN 978-3-540-22147-0, Sr.  2164257.
2. 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, ISBN 978-0-444-50205-6, Sr.  1718169.
3. Pullum, Geoffrey K. (1983). Libre de contexto y procesamiento informático de lenguajes humanos. Proc. 21.ª Reunión Anual de la ACL .
4. 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.
5. 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.
6. 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
7. 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.
8. 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 
9. John E. Hopcroft; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 9780201029888.; Ejercicio 9.10, p.230. En la edición de 2000 se ha omitido el capítulo sobre lenguajes sensibles al contexto.
10. 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.