Llenguatge sensible al context

De Viquipèdia
Salta a la navegació Salta a la cerca

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.[1][2]

Propietats[modifica]

Propietats de clausura[modifica]

  • 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[modifica]

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.[3]

Vegeu també[modifica]

Referències[modifica]

  1. Jörg., Rothe,. Complexity theory and cryptology : an introduction to cryptocomplexity. Berlín: Springer, 2005. ISBN 9783540285205. 
  2. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  3. 1950-, Odifreddi, Piergiorgio,. Classical recursion theory : the theory of functions and sets of natural numbers. Amsterdam: North-Holland, 1989-1999. ISBN 0444872957.