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