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

Baze de date - gestionarea cărților într-o bibliotecă

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

Medii de programare vizuală (JAVA) - evidența autovehiculelor înmatriculate

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

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...

Sistem informatic pentru gestiunea unei librării

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

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...

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...

Autocad pentru începători

C1.1.CONCEPTUL DE CAD TERMINOLOGIE - COMPUTER AIDED ENGINEERING -CAE-vizeazăetapeledecercetare,inovaresiconcepţie; - COMPUTER AIDED DRAWING/...

Securitatea informațională a business-ului

Lecţia 1 Introducere în securitatea informaţională 1.Informaţia ca obiect de valoare şi protecţie 4 2.Conceptele de bază ale Securităţii...

Te-ar putea interesa și

Metode de Pregătire a Prescolarului pentru Adaptarea la Regimul Vietii de Scolaritate

INTRODUCERE Consideraţii generale ‘‘Cât se poate privi în zare, peste timp, nu există decât cerere de oameni pregătiTi Si mai ales bine echipaTi...

Construcții Complexe în Sintaxa Limbii Române

I. DELIMITĂRI CONCEPTUALE 1. Preliminarii 1.1. În sintaxă, orice şir de constituenţi reprezentând un enunţ sau numai părţi componente ale...

Studiul asupra Metodelor de Interpretare a Dreptului

PARTEA I CONSIDERATII GENERALE PRIVIND NOŢIUNEA DREPTULUI Secţiunea 1 1.1. Sensurile şi etimologia termenului „drept”. Sensul filosofic şi...

Aspecte ale interventiei pentru corectarea tulburărilor de limbaj la copiii cu deficiență mintală

Limbajul și gândirea se dezvoltă în tandem cu formarea și aprofundarea tuturor proceselor psihice și cu lărgirea volumului de cunoștințe, sub...

Proiect Pedagogie

Clasa scolara e un grup de invatare care se aseamana, in multe privinte, cu un grup de munca dar are si cateva caracteristici proprii. Asemanarea...

Sisteme Lindenmayer în Viața Artificială

Partea I – Consideratii teoretice (studiu bibliografic) Capitolul I – Introducere 1. TEORIA LIMBAJELOR FORMALE CLASICE Ca definiţie generală un...

Gramaticile Eco-matriceale

CAPITOLUL I INTRODUCERE Gramaticile eco-matriceale stratificate sunt un nou model al sistemelor paralele n-dimensionale care permit reprezentarea...

Logica Computațională

Ce este logica? Logica este ramura filosofiei care se ocupã cu analiza modelelor de raþionament prin care o concluzie este obþinutã dintr-un set de...

Ai nevoie de altceva?