Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

CUPRINS
1.Capitolul 1. Introducere
1.1.Metode de reprezentare a limbajelor...1
1.2.Sisteme de rescriere.......4
2.Capitolul 2. Limbaje independente de context.....7
2.1.Gramatici formale.........7
2.2.Grafuri si arbori..........9
2.3.Arbori generatori......11
2.4.Gramatici independente de context........12
2.5.Proprietati de inchidere ale limbajelor
independente de context.14
3.Capitolul 3.Probleme rezolvabile algoritmic
pentru limbaje independente de context..18
3.1.Problema multimii vide...........18
3.2.Problema multimii infinite......19
3.3.Problema aparentei...20
4.Capitolul 4. Limbaje independente de context si
automate pushdown.....23
4.1.Automate pushdown23
4.2.Legatura dintre limbaje independente si automate
pushdown........27
5.Capitolul 5. Limbaje independente de context deterministe...39
5.1.Automate pushdown deterministe..........39
5.2.Proprietati ale limbajelor independente de context
deterministe.....40
5.3.Gramatici LL(K)......42
5.4.Gramatici LR(K)......44
6. Aplicatie......49
Bibliografie.....64

Alte date

?

CAPITOLUL I

INTRODUCERE

1. METODE DE REPREZENTARE ALE LIMBAJELOR

Un limbaj natural sau artificial (in particular multimea programelor corecte intr-un limbaj de programare dat) este o multime de secvente formate cu caracterele (simbolurile) unei multimi date (vocabular). Daca un limbaj este finit, atunci reprezentarea limbajului se poate face prin enumerarea secventelor sale. Daca limbajul este infinit atunci sunt necesare metode finite de reprezentare a multimii infinite de secvente. In acelasi timp, metodele de reprezentare trebuie sa reflecte o anumita structura a secventelor, specifica limbajului considerat.

Se porneste cu o secventa oarecare si se analizeaza daca secventa face parte din limbajul dat. Altfel spus, secventele limbajului dat sunt recunoscute sau acceptate.

Celor doua tipuri de metode le corespund doua notiuni fundamentale in teoria limbajelor formale.

Metodelor generative le corespund gramaticile formale. O gramatica formala genereaza secventele unui limbaj.

Metodelor analitice le corespund automatele. Un automat recunoaste sau accepta secventele unui limbaj.

Prin alfabet intelegem orice multime finita si nevida. Uneori in locul termenului de alfabet se foloseste termenul echivalent vocabular.

Un alfabet se noteaza de obicei cu litere majuscule ale alfabetului latin sau grec. Sunt preferate literele eventual cu indici.

Elementele unui alfabet se numesc simboluri sau caractere.

Exemple de alfabet: , , .

Daca este un alfabet si sunt elemente ale lui , nu neaparat distincte, atunci o expresie de forma

se numeste secventa pe alfabetul . Uneori in locul termenului secventa se mai folosesc termenii echivalenti cuvant sau string.

Numarul natural din relatia (1) poarta numele de lungime a secventei si se noteaza cu .

Se considera si secventa de lungime 0. Aceasta secventa nu contine nici un simbol, poarta numele de secventa vida si va fi notata cu .

Multimea tuturor secventelor pe alfabetul se noteaza cu .

Daca si sunt doua secvente din atunci daca si numai daca :

Daca sunt simboluri distincte ale alfabetului , atunci, conform (2): .

Fie si sunt doua secvente din . Secventa

se noteaza si se spune ca se obtine prin concatenarea sau juxtapunerea secventelor si .

Aplicatia

este o lege de compozitie interna pe . Este evident faptul ca aceasta lege de compozitie este asociativa si admite secventa ca element neutru. Prin urmare (3) defineste pe o structura de monoid. Acest monoid poarta numele de obicei de semigrup liber generat de alfabetul .

Exceptand cazul in care alfabetul este format dintr-un singur element, monoidul nu este comutativ. De exemplu, pentru , monoidul este format din toate secventele care se pot forma cu cifrele 0 si 1. Putem ordona elementele in dupa lungime, iar secventele de lungimi egale le ordonam dupa valoarea lor in baza 2. Astfel:

Multimea contine toate reprezentarile binare ale numerelor naturale, dar si alte secvente ca .

Fie un alfabet. Prin limbaj pe alfabetul se intelege orice submultime a lui . Deci limbajele pe alfabetul apartin multimii a partilor lui . Multimea vida este un limbaj pe orice alfabet si poarta numele de limbaj vid.

Multimea este de asemenea un limbaj pe orice alfabet.

Limbajele si sunt diferite. Limbajul vid nu contine nici o secventa pe cand contine o secventa, anume secventa vida.

Insusi este un limbaj pe si anume limbajul format din toate secventele de lungime 1. Intregul monoid este un limbaj pe numit limbaj universal pe . Pentru , multimea reprezentarilor binare ale numerelor prime: este un limbaj infinit pe alfabetul .

Daca este un simbol din alfabetul si , atunci cu notam numarul aparitiilor simbolului in secventa . De exemmplu si .

Operatiile obisnuite cu multimi: reuniune, intersectie, diferenta, complementara se pot considera si pe multimea P a limbajelor pe alfabetul . In afara acestora exista si alte operatii specifice limbajelor. Dintre acestea vom considera aici operatia de inmultire a limbajelor:

P× P? P

P

unde

Limbajul definit de (3) poarta numele de produs al limbajelor si .

Se deduce usor ca operatia de inmultire a limbajelor este asociativa si admite ca element neutru limbajul . Prin urmare P are la randul sau o structura de monoid.

Pentru un limbaj oarecare pe alfabetul , definim puterile limbajului , astfel: