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.[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
- ↑ 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.