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
Categoria:Llenguatges formals Categoria:Complexitat computacional