Lenguaje sensible al contexto

En las ciencias de la computación, un lenguaje sensible al contexto es un lenguaje formal que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática la menos frecuente, tanto en la teoría como en la práctica.

Propiedades computacionales

Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing no determinista linealmente acotada, también llamado Autómata linealmente acotado. Se trata de una máquina de Turing no determinista con una cinta de sólo kn posiciones, donde n es el tamaño de la entrada y k es la constante asociada a la máquina. Esto significa que cada lenguaje formal que puede ser decidido por una máquina es un lenguaje sensible al contexto.

Ejemplos

Un ejemplo de un lenguaje sensible al contexto que no es libre de contexto es
L = {aⁿbⁿcⁿ | n>= 0} no es un lenguaje libre de contexto, pero si es un lenguaje sensible al contexto. Una gramática para L:

Transiciones
S → ε	aB → ab
S → aSBC	bB → bb
CB → HB	bC → bc
HB → HC	cC → cc
HC → BC

L puede demostrarse como un lenguaje sensible al contexto mediante la construcción de un autómata lineal acotado que acepta L. Se puede demostrar fácilmente que este lenguaje no es ni regular, ni independiente del contexto, por la aplicación del Lema del bombeo. Un ejemplo de un lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión es un problema EXPSPACE-hard, por ejemplo, el conjunto de pares equivalentes de expresiones regulares con exponenciación.

Propiedades

La unión, intersección, y concatenación de dos Lenguajes sensibles al contexto es un Lenguaje sensible al contexto.
El complemento de un lenguaje sensible al contexto es en sí mismo sensible al contexto.
Cada gramática libre de contexto es un lenguaje sensible al contexto.
La composición de una cadena en un lenguaje definido por una gramática sensible al contexto arbitraria, o por una gramática determinista sensible al contexto arbitraria, es un problema PSPACE-completo.

Véase también

Referencias

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Traducido de , exactamente la versión http://en.wikipedia.org/wiki/Context-sensitive_language, bajo licencia GFDL y CC-CI 3.0
Immerman, Neil (1988). «Nondeterministic space is closed under complementation». SIAM J. Comput. 17 (5): 935-938. doi:10.1137/0217058.

Datos: Q1430282