# Gramàtica sensible al context

En lingüística i informàtica, una gramàtica sensible al context és una gramàtica formal en la qual cada regla dreta o esquerra de producció es pot embolcallar per un context de símbols terminals i no terminals. Les gramàtiques sensibles al context son més generals que les gramàtiques lliures de context, en el sentit que hi ha llenguatges que es poden descriure amb una gramàtica sensible al context però no amb una gramàtica lliure de context.
Un llenguatge formal que es pot descriure amb una gramàtica sensible al context s'anomena un llenguatge sensible al context.
Les gramàtiques sensibles al context estan classificades com de tipus 1 a la jerarquia de Chomsky.
Aquestes gramàtiques van ser introduïdes per Chomsky com un intent de descriure la sintaxi del llenguatge natural donat que una paraula pot ser adequada en una certa posició depenent del context.

## Definició formal

Una gramàtica formal G = (N, Σ, P, S), on N és un conjunt de símbols no terminals, Σ és un conjunt de símbols terminals, P és un conjunt de regles de producció i S és el símbol inicial, és sensible al context si totes les regles P son de la forma:
   αAβ → αγβ
on A ∈ N, α,β ∈ (N∪Σ)$^*$ i γ ∈ (N∪Σ)$^+$.
Una cadena u ∈ (N∪Σ)$^*$ produeix directament, o es deriva cap a, una cadena v ∈ (N∪Σ)$^*$, escrit com u ⇒ v si u es pot escriure com lαAβr i v es pot escriure com lαγβr per algunes regles de producció (αAβ→αγβ) ∈ P i algunes cadenes de context l, r ∈ (N∪Σ)$^*$. Més generalment, u produeix o es deriva cap a, v escrit com u ⇒$^*$ v si u = u$_1$ ⇒ ... ⇒ u$_n$ = v per algun n≥0 i algunes cadenes u₂, ..., u$_n$$_{-1}$ (N∪Σ)$^*$. Per tant, la relació (⇒$^*$) és la clausura transitiva reflexiva de la relació (⇒).
El nom de sensible al context ve donat per l'α i β que formen el context d'A i determinen si A es pot reemplaçar per γ o no. Això és diferent de les gramàtiques lliure de context, on el context d'un símbol no terminal no es pren en consideració.

## Exemple

La següent gramàtica, que comença amb el símbol S, genera el llenguatge { a$^n$b$^n$c$^n$ : n ≥ 1 }:
* S → aBC
* S → aSBC
* CB → CZ
* CZ → WZ
* WZ → WC
* WC → BC
* aB → ab
* bB → bb
* bC → bc
* cC → cc
Les regles 1 i 2 permeten transformar S a a$^n$BC(BC)$^{n-1}$ Les regles 3 fins a 6 permeten successivament intercanviar cada CB per BC. Regles 7 a 10 permet reemplaçar un símbol no terminal B i C amb el seu corresponent terminals b i c respectivament. Una cadena de generació per la cadena aaabbbccc és la següent:
    S
    →₂ aSBC
    →₂ aaSBCBC
    →$_1$ aaaBCBCBC
    →₃ aaaBCZCBC
    →₄ aaaBWZCBC
    →₅ aaaBWCCBC
    →₆ aaaBBCCBC
    →₃ aaaBBCCZC
    →₄ aaaBBCWZC
    →₅ aaaBBCWCC
    →₆ aaaBBCBCC
    →₃ aaaBBCZCC
    →₄ aaaBBWZCC
    →₅ aaaBBWCCC
    →₆ aaaBBBCCC
    →₇ aaabBBCCC
    →₈ aaabbBCCC
    →₈ aaabbbCCC
    →$_9$ aaabbbcCC
    →$_{10}$ aaabbbccC
    →$_{10}$ aaabbbccc

## Propietats
### Propietats de clausura

Les gramàtiques sensibles al context son tancades a la unió, intersecció, concatenació, substitució, homomorfisme invers, complement i clausura de Kleene.
Tot llenguatge enumerable recursivament L es pot escriure com h(L) per algun llenguatge sensible al context L i algun homomorfisme h.

### Problema computacional

El problema de decisió que pregunta si una cadena pertany a un gramàtica sensible al context G és PSPACE-completa.

## Vegeu també

* Jerarquia de Chomsky
* Complexitat computacional

## Referències

* ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
* ↑ C., Martin, John. Introduction to languages and the theory of computation. 4th ed. Nova York, NY: McGraw-Hill, 2011. ISBN 9780073191461.
* ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
* ↑ Lita, Catalin-Valeriu «On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses» (en anglès). 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). IEEE, 01-09-2016. DOI: 10.1109/synasc.2016.064.
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. :