# Llenguatge sensible al context

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge sensible al context si està definit per una gramàtica sensible al context.

## Propietats
### Propietats de clausura

* La unió, intersecció, i concatenació de dos llenguatges sensibles al context és un llenguatge sensible al context.
* El complement d'un llenguatge sensible al context és també un llenguatge sensible al context.
* Cada gramàtica lliure de context és un llenguatge sensible al context.
* La composició d'una cadena amb un llenguatge definit per una gramàtica sensible al context arbitraria o per una gramàtica determinista sensible al context arbitraria, és un problema PSPACE-complet.

### Propietats computacionals

Computacionalment, un llenguatge sensible al context és equivalent a una màquina de Turing no determinista fitada linealment, també anomenada autòmat fitat linealment. Es tracta d'una màquina de Turing no determinista amb una cinta de només kn posicions, on n és la mida de l'entrada i k és una constant associada a la màquina. Això vol dir que cada llenguatge formal que es pot decidir per una màquina és un llenguatge sensible al context.
El conjunt de llenguatges és conegut com a NLINSPACE o NSPACE (O(n)), ja que es poden acceptar usant un espai lineal en una màquina de Turing no determinista. La classe LINSPACE o DSPACE (O(n)) és defineix igual, però fent servir una màquina de Turing determinista. Clarament LINSPACE és un subconjunt de NLINSPACE però no se sap si LINSPACE = NLINSPACE.

## Vegeu també

* Jerarquia de Chomsky
* Gramàtica sensible al context

## Referències

* ↑ Jörg., Rothe,. Complexity theory and cryptology : an introduction to cryptocomplexity. Berlín: Springer, 2005. ISBN 9783540285205.
* ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
* ↑ 1950-, Odifreddi, Piergiorgio,. Classical recursion theory : the theory of functions and sets of natural numbers. Amsterdam: North-Holland, 1989-1999. ISBN 0444872957.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :