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 de manera equivalente mediante una gramática no contractual ). La sensibilidad al contexto se conoce como tipo 1 en la jerarquía de lenguajes formales de Chomsky.

Propiedades computacionales

Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing lineal acotada y no determinista , también llamada autómata lineal acotada . 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 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 pueden aceptarse utilizando espacio lineal en una máquina de Turing no determinista. ^[1] La clase LINSPACE (o DSPACE( O ( n ))) se define igual, 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 más simples sensibles al contexto pero no libres de contexto es : el lenguaje de todas las cadenas que consta de n apariciones del símbolo "a", luego n "b", luego n "c" (abc, aabbcc, aaabbccc , 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]} ${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$

Se puede demostrar que L es un lenguaje sensible al contexto construyendo un autómata lineal acotado que acepte L . Se puede demostrar fácilmente que el lenguaje no es regular ni está libre de contexto aplicando 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 inicial 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 idioma sensible al contexto (el "3" en el nombre de este idioma pretende significar un alfabeto ternario); es decir, la operación "producto" define un lenguaje sensible al contexto (pero la "suma" define sólo un lenguaje libre de contexto como muestra la gramática ) . 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 de alguna manera más restrictiva del lenguaje, por ejemplo . Este puede especializarse en y, de este, a , , 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 idioma pretende significar un alfabeto binario). Hartmanis demostró esto utilizando lemas de bombeo para lenguajes regulares y libres de contexto sobre un alfabeto binario y, luego, 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 idioma pretende significar un alfabeto unario). Esto se lo atribuyó A. Salomaa a Matti Soittola mediante un autómata acotado lineal 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. 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 problema difícil de EXPSPACE , por ejemplo, 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 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 de PSPACE completo .

Ver también

• Autómata lineal acotado
• Lista de generadores de analizadores para lenguajes sensibles al contexto
• Jerarquía chomsky
• Idiomas indexados : un subconjunto estricto de los idiomas sensibles al contexto
• Jerarquía de vertedero

Referencias

1. Rothe, Jörg (2005), Teoría de la complejidad y criptología , Textos de informática teórica. Una serie EATCS, Berlín: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0, señor  2164257.
2. Odifreddi, PG (1999), Teoría clásica de la recursión. 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, señor  1718169.
3. Pullum, Geoffrey K. (1983). La libertad de contexto y el procesamiento informático de los lenguajes humanos. Proc. XXI 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, los lenguajes y la computación de autómatas. Addison Wesley
7. J. Hartmanis y H. Shank (julio de 1968). "Sobre el reconocimiento de números primos por parte de autómatas" (PDF) . Revista de la 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, los lenguajes y la computación de autómatas . Addison-Wesley. ISBN 9780201029888.; Ejercicio 9.10, p.230. En la edición de 2000, se omitió el capítulo sobre lenguajes sensibles al contexto.
10. Immerman, Neil (1988). "El espacio no determinista está cerrado bajo complementación" (PDF) . SIAM J. Computación . 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.