Gramatici libere de context

Definitia 1: O gramatica G = (V, , S, R) se numeste gramatica independenta de context daca toate regulile sale sunt de forma:

A  x,

unde A  V si x  (V)*.

Definitia 2: Un limbaj generat de o gramatica independenta de context se numeste limbaj independent de context.

Observatii:

1. Orice limbaj regulat este i.d.c.

2. Limbajul L = { anbn | n  0 } (despre care am aratat ca nu este regulat) este i.d.c.. Intr-adevar, limbajul L este generat de gramatica i.d.c. G = ({S}, , S, R) cu regulile:

S  aSb

S  

Definitia 3: O derivatie se numeste derivatie la stanga daca la fiecare pas al derivatiei variabila cea mai din stanga se inlocuieste.

O derivatie se numeste derivatie la dreapta daca la fiecare pas al derivatiei variabila cea mai din dreapta se inlocuieste.

Exemplu: Fie gramatica i.d.c. G = ({S, A, B}, {a, b}, S, R) ale carei reguli sunt:

S  AB

A  aA

B  Bbb

A  a

B  

Este usor de observat ca limbajul generat de G este L(G) = {amb2n | m  1, n  0}. Scriem in continuare doua derivatii care conduc la acelasi cuvant:

S  AB  aAB  aaB  aaBbb  aabb

si, respectiv:

S  AB  ABbb  Abb  aAbb  aabb

Se observa ca in cazul primei derivari de fiecare data variabila cea mai din stanga se inlocuieste, iar la a doua derivare variabila cea mai din dreapta se inlocuieste. Asadar, prima derivare este la stanga, iar a doua este la dreapta.

Arbore de derivare

O alta modalitate de a prezenta o gramatica i.d.c. este printr-un arbore de derivare.

Definitia 4: Fie G = (V, , S, R) o gramatica indepenenta de context. Un arbore se numeste arbore de derivare al gramaticii G daca si numai daca indeplineste simultan regulile:

1. S este radacina arborelui

2. Fiecare frunza este etichetata cu  sau un terminal a  

3. Fiecare nod intermediar (care nu este frunza) este etichetat cu un neterminal A  V

4. Daca un varf este etichetat cu neterminalul A  V si copii lui sunt a1, a2, …., an, atunci gramatica G contine regula:

A  a1a2….an

5. Un nod care are ca si fiu pe  nu mai poate avea alti copii.

Definitia 5: Un arbore se numeste arbore partial de derivare pentru gramatica G daca si numai daca indeplineste simultan regulile 1, 3, 4, si 5 de mai sus si regula:

2'. Fiecare frunza este etichetata cu , cu un terminal a   sau cu un neterminal A  V.

Parcurgand un arbore de derivare in adancime, iar copiii de la stanga la dreapta si luand in considerare numai terminalele, se obtine o propozitie a limbajului L(G).

Parcurgand un arbore partial de derivare in adancime si luand in considerare numai frunzele, se obtine o asa numita forma propozitionala a gramaticii G.

Un arbore de derivare da o descriere explicita si usoara a unei derivari.

Exemplu: Pentru gramatica din exemplul de mai sus arborele de mai jos este un arbore partial de derivare: