Lenguaje sensible al contexto

En la teoría del lenguaje formal , un lenguaje sensible al contexto es un lenguaje formal que puede definirse mediante una gramática sensible al contexto , donde la aplicabilidad de una regla de producción puede depender del contexto de los símbolos circundantes. A diferencia de las gramáticas libres de contexto , que pueden aplicar reglas independientemente del contexto, las gramáticas sensibles al contexto permiten que las reglas se apliquen solo cuando están presentes símbolos vecinos específicos, lo que les permite expresar dependencias y concordancias entre partes distantes de una cadena.

Estos lenguajes corresponden a los lenguajes de tipo 1 en la jerarquía de Chomsky y se definen de forma equivalente mediante gramáticas no contractivas (gramáticas en las que las reglas de producción nunca disminuyen la longitud total de una cadena). Los lenguajes sensibles al contexto pueden modelar fenómenos del lenguaje natural, como la concordancia sujeto-verbo , las dependencias seriales cruzadas y otras relaciones sintácticas complejas que no pueden ser capturadas por tipos de gramática más simples, lo que los hace importantes para la lingüística computacional y el procesamiento del lenguaje natural .

Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing lineal acotada no determinista , también llamada autómata lineal acotado . Es decir, una máquina de Turing no determinista con una cinta de solo${\displaystyle kn}$células, donde${\displaystyle n}$es el tamaño de la entrada y${\displaystyle k}$es una constante asociada a 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 pueden ser aceptados usando 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 usa una máquina de Turing determinista . Claramente, LINSPACE es un subconjunto de NLINSPACE, pero no se sabe si LINSPACE = NLINSPACE. ^{[ 2 ]}

Uno de los lenguajes más simples sensibles al contexto pero no libres de contexto es${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$: el lenguaje de todas las cadenas que constan de n ocurrencias del símbolo "a", luego n "b", luego n "c" (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 igual frecuencia ( aabccb , baabcaccb , etc.) y también es sensible al contexto. ^{[ 4 ] [ 5 ]}

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 ni regular ni libre de contexto aplicando los lemas de bombeo respectivos para cada una de las clases de lenguajes a L.

Similarmente:

${\displaystyle L_{\textit {Cruz}}=\{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 a partir de dos gramáticas libres de contexto que generan formas sentenciales en los formatos ${\displaystyle a^{m}C^{m}}$ y ${\displaystyle B^{n}d^{n}}$ y luego complementarlos con una producción de permutación como ${\displaystyle CB\rightarrow BC}$, un nuevo símbolo de inicio y azúcar sintáctico estándar.

${\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${\displaystyle S\rightarrow aSc|R}$y${\displaystyle R\rightarrow bRc|bc}$muestra). Debido a la propiedad conmutativa del producto, la gramática más intuitiva para${\displaystyle L_{\textit {MUL3}}}$es ambiguo. Este problema puede evitarse considerando una definición del lenguaje de alguna manera más restrictiva, por ejemplo${\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$Esto puede especializarse en ${\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}$y, de esto, a${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$,${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$, etc.

${\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${\displaystyle L_{\textit {Cuadrado}}=\{w^{2}:w\in \Sigma ^{*}\}}$,${\displaystyle L_{\textit {Cubo}}=\{w^{3}:w\in \Sigma ^{*}\}}$, etc.

${\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 se refiere a 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 multitape lineal acotado que acepta${\displaystyle L_{PRIMES2}}$. ^{[ 7 ]}

${\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}$es un lenguaje sensible al contexto (el "1" en el nombre de este lenguaje se refiere a 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 (véase: Formal Languages ​​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 EXPSPACE -difícil, por ejemplo, el conjunto de pares de expresiones regulares equivalentes con exponenciación.

• La unión , intersección y concatenación de dos lenguajes sensibles al contexto también son sensibles al contexto; asimismo, la suma de Kleene de un lenguaje sensible al contexto también 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 de una cadena a un lenguaje definido por una gramática sensible al contexto arbitraria, o por una gramática sensible al contexto determinista arbitraria, es un problema PSPACE-completo .

• Lista de generadores de analizadores sintácticos para lenguajes sensibles al contexto
• Lenguajes indexados : un subconjunto estricto de los lenguajes sensibles al contexto.
• Jerarquía de Weir
• Formalismo gramatical ligeramente sensible al contexto : una colección de formalismos para diversas subclases de lenguajes sensibles al contexto.

• Sipser, M. (1996), Introducción a la teoría de la computación , PWS Publishing Co.