Extras din curs
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:
Preview document
Conținut arhivă zip
- Gramatici Libere de Context.doc