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.[1][2][3]
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
[modifica]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 = u1 ⇒ ... ⇒ un = v per algun n≥0 i algunes cadenes u₂, ..., un-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
[modifica]La següent gramàtica, que comença amb el símbol S, genera el llenguatge { anbncn : 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 anBC(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
[modifica]Propietats de clausura
[modifica]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
[modifica]El problema de decisió que pregunta si una cadena pertany a un gramàtica sensible al context G és PSPACE-completa.[4]
Vegeu també
[modifica]Referències
[modifica]- ↑ 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, 2016-09. DOI: 10.1109/synasc.2016.064.