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.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.Esto significa que cada lenguaje formal que puede ser decidido por una máquina es un lenguaje sensible al contexto.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.