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 = {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
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.
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.
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
Abril 06, 2022
lenguaje, sensible, contexto, ciencias, computación, lenguaje, sensible, contexto, lenguaje, formal, puede, definido, gramáticas, sensibles, contexto, cuatro, tipos, gramáticas, jerarquía, chomsky, siendo, esta, gramática, menos, frecuente, tanto, teoría, como. En las ciencias de la computacion un lenguaje sensible al contexto es un lenguaje formal que puede ser definido por gramaticas sensibles al contexto Es uno de los cuatro tipos de gramaticas en la jerarquia de Chomsky siendo esta gramatica la menos frecuente tanto en la teoria como en la practica Indice 1 Propiedades computacionales 2 Ejemplos 3 Propiedades 4 Vease tambien 5 ReferenciasPropiedades computacionales EditarComputacionalmente un lenguaje sensible al contexto es equivalente a una maquina de Turing no determinista linealmente acotada tambien llamado Automata linealmente acotado Se trata de una maquina de Turing no determinista con una cinta de solo kn posiciones donde n es el tamano de la entrada y k es la constante asociada a la maquina Esto significa que cada lenguaje formal que puede ser decidido por una maquina es un lenguaje sensible al contexto Ejemplos EditarUn ejemplo de un lenguaje sensible al contexto que no es libre de contexto es L anbncn n gt 0 no es un lenguaje libre de contexto pero si es un lenguaje sensible al contexto Una gramatica para L TransicionesS e aB abS aSBC bB bbCB HB bC bcHB HC cC ccHC BCL puede demostrarse como un lenguaje sensible al contexto mediante la construccion de un automata lineal acotado que acepta L Se puede demostrar facilmente que este lenguaje no es ni regular ni independiente del contexto por la aplicacion del Lema del bombeo Un ejemplo de un lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decision es un problema EXPSPACE hard por ejemplo el conjunto de pares equivalentes de expresiones regulares con exponenciacion Propiedades EditarLa union interseccion y concatenacion de dos Lenguajes sensibles al contexto es un Lenguaje sensible al contexto El complemento de un lenguaje sensible al contexto es en si mismo sensible al contexto Cada gramatica libre de contexto es un lenguaje sensible al contexto La composicion de una cadena en un lenguaje definido por una gramatica sensible al contexto arbitraria o por una gramatica determinista sensible al contexto arbitraria es un problema PSPACE completo Vease tambien EditarAutomata linealmente acotado Jerarquia de Chomsky Gramaticas sensibles al contexto Maquina de TuringReferencias EditarSipser M 1996 Introduction to the Theory of Computation PWS Publishing Co Traducido de exactamente la version 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 Obtenido de https es wikipedia org w index php title Lenguaje sensible al contexto amp oldid 130199658, wikipedia, wiki, leyendo, leer, libro, biblioteca,
