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₁ ⇒ ... ⇒ 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ⁿbⁿcⁿ : n ≥ 1 }:

1. S → aBC
2. S → aSBC
3. CB → CZ
4. CZ → WZ
5. WZ → WC
6. WC → BC
7. aB → ab
8. bB → bb
9. bC → bc
10. cC → cc

Les regles 1 i 2 permeten transformar S a aⁿ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

→₁ aaaBCBCBC

→₃ aaaBCZCBC

→₄ aaaBWZCBC

→₅ aaaBWCCBC

→₆ aaaBBCCBC

→₃ aaaBBCCZC

→₄ aaaBBCWZC

→₅ aaaBBCWCC

→₆ aaaBBCBCC

→₃ aaaBBCZCC

→₄ aaaBBWZCC

→₅ aaaBBWCCC

→₆ aaaBBBCCC

→₇ aaabBBCCC

→₈ aaabbBCCC

→₈ aaabbbCCC

→₉ aaabbbcCC

→₁₀ aaabbbccC

→₁₀ 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