Gramatici Libere de Context

Curs
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 18 în total
Cuvinte : 3064
Mărime: 428.93KB (arhivat)
Cost: Gratis

Extras din document

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

Gramatici Libere de Context - Pagina 1
Gramatici Libere de Context - Pagina 2
Gramatici Libere de Context - Pagina 3
Gramatici Libere de Context - Pagina 4
Gramatici Libere de Context - Pagina 5
Gramatici Libere de Context - Pagina 6
Gramatici Libere de Context - Pagina 7
Gramatici Libere de Context - Pagina 8
Gramatici Libere de Context - Pagina 9
Gramatici Libere de Context - Pagina 10
Gramatici Libere de Context - Pagina 11
Gramatici Libere de Context - Pagina 12
Gramatici Libere de Context - Pagina 13
Gramatici Libere de Context - Pagina 14
Gramatici Libere de Context - Pagina 15
Gramatici Libere de Context - Pagina 16
Gramatici Libere de Context - Pagina 17
Gramatici Libere de Context - Pagina 18

Conținut arhivă zip

  • Gramatici Libere de Context.doc

Alții au mai descărcat și

Medii de Programare Vizuala (JAVA) - Evidenta Autovehiculelor Inmatriculate

1. Enuntul temei: Sa se realizeze un proiect pentru evidenta autovehiculelor inmatriculate in circulatie. Pentru fiecare autoturism se considera...

Baze de Date - Gestionarea Cartilor intr-o Biblioteca

1 Introducere Trebuie menţionat faptul că lucrarea de faţă îşi propune înainte de toate să identifice cele mai importante aspecte şi probleme ale...

Sistemul Dinamic de Rutare a Pachetelor

CAPITOLUL 1 PREZENTARE GENERALĂ Această secţiune prezintă o imagine de ansamblu asupra sistemului dinamic de rutare a pachetelor (DPRS) şi...

Probleme Rezolvate Oracle

I. SISTEME DE GESTIUNE A BAZELOR DE DATE 1. Facultăţi Se dă următoarea structură de fişier: Denumire C,20 (Denumirea facultăţii) Localitate...

Subsistem Informatic Privind Evidența Fondului de Cărți în Bibliotecă

INTRODUCERE J. C. Levinson sublinia că cei care studiază “cu asiduitate proprii clienţi, clienţii concurenţei şi clienţii întregului lor domeniu...

Sistem Informatic pentru Gestiunea unei Librarii

I. Prezentarea sistemului informatic I.1. Descrierea generală a sistemului informatic Scopul aplicației ce urmează a fi proiectată este acela de...

Sisteme de Operare

1.1 Sisteme de calcul. Structura sistemelor de calcul Sistemele de operare sunt colecţii de programe existente pe sistemele de calcul . Prin...

Programarea Orientata spre Obiecte - Limbajul Java

1. INTRODUCERE IN PROGRAMAREA ORIENTATA SPRE OBIECTE OBIECTE D. Un obiect este un un mod simplificat de a identifica într-un program un lucru, o...

Ai nevoie de altceva?