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

editar

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

editar

Un ejemplo de un lenguaje sensible al contexto que no es libre de contexto es
L = {anbncn | 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

editar
  • 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

editar

Referencias

editar