Probleme Rezolvabile Algoritmic Pentru Limbaje Independente de Context

CAPITOLUL I

INTRODUCERE

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:

In particular, pentru , este multimea secventelor pe vocabularul V care au lungimea 2. In general, este multimea secventelor pe vocabularul V care au lungimea egala cu n , .

Pentru P se folosesc curent notatiile:

. Este clar ca . In particular, pentru L=V, reprezinta multimea a tuturor secventelor pe vocabularul V, astfel ca nu se creaza confuzii in utilizarea notatiei .

2. SISTEME DE RESCRIERE

Notiunea de sistem de rescriere permite tratarea unitara a celor doua modele de descriere a limbajelor: modelul generativ si modelul analitic. Ideea de baza a acestei notiuni este aceea ca secventele unui limbaj se pot obtine unele din altele prin rescrierea anumitor subsecvente.

Definitie. Un sistem de rescriere este un cuplu SR=(V,P) unde V este un alfabet iar P este o multime finita de perechi de secvente pe alfabetul V.

O pereche se numeste regula de productie sau regula de rescriere si se noteaza de obicei . Se spune ca se rescrie in sau produce in raport cu sistemul de rescriere SR.

Definitie. Fie SR=(V,P) un sistem de rescriere si . Spunem ca deriva direct in in raport cu sistemul de rescriere SR si notam

daca secventele si admit reprezentarea:

, si .

Se mai spune ca secventa se obtine din secventa prin rescrierea subsecventei in subsecventa conform cu productia .

Notatia pentru relatia deriva direct a devenit o notatie consacrata in teoria limbajelor formale. Cand aceasta notatie se foloseste intr-un context in care apare si implicatia logica, vom prefera sa folosim pentru implicatia logica notatia “”

Pentru relatia binara pe vom considera inchiderea tranzitiva si inchiderea reflexiva .

Astfel, vom spune ca deriva propriu in , , daca exista secventele astfel incat si , .

Spunem ca deriva in , si notam daca sau .

Putem considera si puterile rela\iei .

Relatia este o relatie binara tranzitiva iar relatia este o relatie binara reflexiva si tranzitiva.

Un sistem de rescriere se transforma intr-un mecanism generativ prin fixarea unei submultimi finite de secvente din notata AX. Elementele lui AX se numesc axiome.

Definitie. Fie SR=(V,P) un sistem de rescriere s]i AX un sistem de axiome din . Numim limbaj generat de sistemul de rescriere SR, in raport cu sistemul de axiome AX, multimea

De obicei, notiunile generale de sisteme de rescriere si limbaj generat definite mai sus li se aduc modificari. Una dintre acestea consta in partitionarea vocabularului V in doua submultimi:

se numeste vocabular neterminal iar elementele lui sunt simboluri neterminale. .

se numeste vocabular terminal iar elementele lui sunt simboluri terminale.

O alta modificare ar fi aceea ca multimea AX sa contina o singura axioma X. In raport cu aceste modificari, limbajul generat de sistemul de rescriere definit in relatia (4) se inlocuieste cu:

Transformarea unui sistem de rescriere intr-un mecanism analitic se face prin fixarea unui sistem de axiome. De aceasta data axiomele vor fi rezultatul derivatiei.

Definitie. Fie SR=(V,P) un sistem de rescriere si AX un sistem de axiome din . Numim limbaj acceptat de sistemul de rescriere SR in raport cu sistemul de axiome AX, multimea:

Daca si aici partionam vocabularul si punem conditia ca AX sa contina o singura axioma X, atunci limbajul acceptat de sistemul de rescriere SR se defineste prin:

Sunt acceptate (sau recunoscute) de catre sistemul de rescriere SR acele secvente w pe vocabularul terminal care prin aplicarea unui numar finit de reguli de rescriere se reduc la axioma X.

CAPITOLUL II

LIMBAJE INDEPENDENTE DE CONTEXT

§1. Gramatici formale.

Gramaticile formale sunt cazuri particulare de sisteme de rescriere.

Definitie. Se numeste gramatica generativa un cuadruplu unde:

– este un alfabet ale carui elemente se numesc simboluri neterminale;

– este un alfabet ale carui elemente se numesc simboluri terminale;

;

– si se numeste simbol initial;

-P este o multime finita de perechi ,unde

si contine cel putin un simbol neterminal.

O pereche se numeste productie si se noteaza de obicei, . Se citeste produce .

Relatia deriva direct (eventual ) se defineste la fel ca in cazul sistemelor de rescriere. Daca , atunci daca exista o productie astfel incat si . Cu alte cuvinte se obtine din prin rescrierea lui in , conform productiei .

Relatiile , si se definesc ca si in cazul sistemelor de rescriere.

Definitie. Fie o gramatica generativa. Limbajul generat de gramatica G este prin definitie:

Ierarhia lui Chomsky. Fie o gramatică formală.

Spunem că G este de tip 0 (fără restricții).

Spunem că G este de tip 1 dacă producțiile sale satisfac restricția , exceptând eventual producția caz în care S nu apare în partea dreaptă a nici unei producții. Se mai spune că gramatica G este cu lungime crescătoare.

Spunem că G este de tip 2 dacă producțiile sale sunt de forma , unde . Gramaticile de tip 2 se mai numesc și gramatici independente de context (context-free).

Spunem că gramatica G este de tip 3 dacă producțiile sale sunt de forma sau , unde și . Gramaticile de tip 3 se mai numesc și gramatici liniare la dreapta.

Definiție. Se spune că limbajul L este de tipul i dacă există o gramatică formală de tipul i care generează L, .

Notăm cu L(i) clasa limbajelor de tip i , .

Este posibil ca același limbaj să fie generat de gramatici de tipuri diferite. Este evident că orice gramatică de tip este și de tip 0. Prin urmare:.

Orice gramatică de tip 2 este echivalentă cu o gramatica tot de tip 2 dar care nu are producții de forma exceptând eventual producția , caz în care, S nu apare în partea dreapta a nici unei producții.

Prin urmare .Evident că orice gramatica de tip 3 este și de tip 2. Prin urmare . Au loc deci incluziunile:

.

În realitate toate incluziunile precedente sunt stricte.

Se spune că gramatica G este dependentă de context dacă toate productiile sale sunt de forma

unde și , exceptând eventual producția , caz în care S nu apare în partea dreapta a nici unei producții.

În raport cu o gramatică dependentă de context, producția (1) arată că neterminalul A se rescrie în secvența , numai în contextul . Acest fapt justifică denumirea de gramatică dependentă de context cât și denumirea de gramatică independentă de context pentru gramaticile de tip 2.

Se poate arăta (vezi Salomaa, cap. 9) că pentru orice gramatică G de tip 1 există o gramatică dependentă de context, echivalentă cu G.

Prin urmare clasa limbajelor dependente de context coincide cu clasa a limbajelor de tip 2.

§2. GRAFURI SI ARBORI

Definitie. Numim graf orientat o pereche (V,E) unde V este o multime finita de elemente numite varfuri (sau noduri) si E este o multime de perechi de varfuri numite arce(sau muchii). Daca este un arc, atunci spunem ca a este originea arcului si b este extremitatea arcului.

Mai spunem ca este un arc de la varful a la varful b. Se mai foloseste si terminologia: a este predecesorul lui b si b este succesorul lui a.

Este convenabil sa reprezentam varfurile unui graf prin puncte in plan si arcele prin segmente (sau chiar arce) orientate care unesc punctele. Se pot considera si grafuri in care arcele nu presupun o orientare. In acest curs intervin numai grafuri in care arcele au o orientare. Chiar daca nu vom preciza de fiecare data, prin graf vom intelege peste tot un graf orientat.

Definitie. Fie (V,E) un graf. Prin drum (sau lant) in graful (V,E) intelegem o secventa de varfuri

cu proprietatea ca .

Spunem ca (1) este un drum de la .

Lungimea unui drum este, prin definitie, numarul de arce din care ee toate incluziunile precedente sunt stricte.

Se spune că gramatica G este dependentă de context dacă toate productiile sale sunt de forma

unde și , exceptând eventual producția , caz în care S nu apare în partea dreapta a nici unei producții.

În raport cu o gramatică dependentă de context, producția (1) arată că neterminalul A se rescrie în secvența , numai în contextul . Acest fapt justifică denumirea de gramatică dependentă de context cât și denumirea de gramatică independentă de context pentru gramaticile de tip 2.

Se poate arăta (vezi Salomaa, cap. 9) că pentru orice gramatică G de tip 1 există o gramatică dependentă de context, echivalentă cu G.

Prin urmare clasa limbajelor dependente de context coincide cu clasa a limbajelor de tip 2.

§2. GRAFURI SI ARBORI

Definitie. Numim graf orientat o pereche (V,E) unde V este o multime finita de elemente numite varfuri (sau noduri) si E este o multime de perechi de varfuri numite arce(sau muchii). Daca este un arc, atunci spunem ca a este originea arcului si b este extremitatea arcului.

Mai spunem ca este un arc de la varful a la varful b. Se mai foloseste si terminologia: a este predecesorul lui b si b este succesorul lui a.

Este convenabil sa reprezentam varfurile unui graf prin puncte in plan si arcele prin segmente (sau chiar arce) orientate care unesc punctele. Se pot considera si grafuri in care arcele nu presupun o orientare. In acest curs intervin numai grafuri in care arcele au o orientare. Chiar daca nu vom preciza de fiecare data, prin graf vom intelege peste tot un graf orientat.

Definitie. Fie (V,E) un graf. Prin drum (sau lant) in graful (V,E) intelegem o secventa de varfuri

cu proprietatea ca .

Spunem ca (1) este un drum de la .

Lungimea unui drum este, prin definitie, numarul de arce din care este format drumul.

Spunem ca drumul (1) este un ciclu daca .

Definitie.Un arbore orientat si ordonat este un graf orientat T=(V,E) care are proprietatile:

Exista un varf , numit radacina, care nu are predecesori;

Fiecare varf diferit de radacina are exact un predecesor;

Pentru fiecare varf , exista un drum de la r la v;

Pe multimea succesorilor fiecarui varf este definita o relatie de ordine totala.

In continuare prin arbori vom intelege arbori orientati si ordonati. Convenim ca pe reprezentarea in plan a unui arbore, arcele sa fie orientate de sus in jos. In acest mod nu mai este necesar sa reprezentam sagetile care dau sensul.

De asemenea, convenim ca ordinea pe multimea succesorilor fiecarui varf sa fie ordinea "de la stanga la dreapta".

Toate drumurile intr-un arbore au orientarea de sus in jos. Daca exista un drum de la varful v la varful v', atunci spunem ca v este un stramos al lui v' iar v' este un descendent al lui v.

Se spune ca v este un varf maximal (sau terminal) daca v nu are succesori. Celelalte varfuri ale arborelui sunt varfuri interioare.

In figura 1, este un varf maximal iar si r sunt noduri interioare.

Relatia "la stanga" intre descendentii varfurilor unui arbore T se extinde la o relatie de ordine partiala pe multimea E a varfurilor arborelui.

Fie doua varfuri care nu sunt situate pe acelasi drum. Exista drumurile:

Notam .

Varfurile si sunt succesori ai aceluiasi varf al arborelui.

Definim: v la stanga lui este la stanga lui .

Fie T un arbore si n un nod interior al sau. Varful n impreuna cu toti descendentii sai si arcele corespunzatoare formeaza un nou arbore T' cu radacina

§3.Arbori generatori

Fie o gramatica independenta de context. Este convenabil ca fiecarei derivatii in gramatica G sa-i asociem un arbore. Unul din motive este acela ca exista derivatii care difera numai prin ordinea de aplicare a productiilor si ca urmare ar trebui sa fie considerate identice.

Un alt motiv este acela al utilizarii gramaticilor independente de context in procesul de compilare. Un program (sau o portiune a acestui program) este privit ca o secventa generata de o gramatica. Generarea codului corespunzator programului se face pe baza unui arbore care se asociaza secventei in faza de analiza sintactica.

Chiar structura enunturilor intr-o limba naturala poate fi reprezentata mai simplu folosind arborii. Un arbore generator in raport cu o gramatica independenta de context presupune pe langa si o "etichetare" a nodurilor. Aceasta inseamna ca fiecarui varf i se asociaza o anumita eticheta.

Definitie. Fie o gramatica independenta de context. Un arbore generator in raport cu gramatica G este un arbore T orientat, ordonat, cu nodurile etichetate, astfel incat :

i) Etichetele nodurilor apartin multimii ;

ii) Eticheta oricarui nod interior al arborelui (deci si a radacinii este un simbol neterminal al gramaticii;

iii) Daca n este un nod interior al lui T cu eticheta A si (in aceasta ordine, de la stanga la dreapta) sunt succesorii lui n, cu etichetele respectiv, atunci

iv) Daca nodul n are eticheta , atunci n este singurul succesor al predecesorului sau.

Daca in definitie eticheta radacinii este A, atunci spunem de obicei ca T este un A-arbore. Un arbore generator in raport cu o gramatica se mai numeste si arbore derivational. De un interes special sunt S-arborii pentru care etichetele nodurilor terminale apartin multimii .

Daca sunt etichetele nodurilor terminale ale arborelui T (in aceasta ordine), atunci se spune ca arborele T produce secventa .

Teorema. Fie o gramatica independenta de context. Daca in raport cu gramatica G

atunci exista un A-arbore care produce .

Demonstratie. Rationam prin inductie dupa lungimea derivatiei (2).

Teorema. Fie o gramatica independenta de context si T un A-arbore care produce secventa .

Atunci

Demonstratie. Rationam prin inductie dupa numarul m al nodurilor interioare ale arborelui T.

Teorema. Fie o gramatica independenta de context. Atunci limbajul generat de gramatica G este exact multimea acelor secvente , cu proprietatea ca exista un S-arbore care produce w.

Demonstratie. Fie . Rezulta si . Din teorema anterioara rezulta ca exista un S-arbore care produce w.

Reciproc, fie astfel incat exista un S-arbore T care produce secventa w. Avem , deci .

§4. Gramatici independente de context

Din punct de vedere al aplicațiilor la descrierea limbajelor de programare și în compilare, gramaticile independente de context constituie clasa cea mai importanta de gramatici din ierarhia lui Chomsky.

O gramatica independenta de context poate fi folosită pentru a descrie structura sintactică a unui limbaj de programare. Structura sintactica a unui program este determinată de regulile ( de producție) folosite pentru scrierea programului.

Analizorul sintactic al unui compilator poate fi privit ca un mecanism care determină dacă pentru o secvență de intrare (programul sursă) exista o derivație în raport cu gramatica independentă de context.

Gramaticile independente de context sunt necesare deoarece într-un limbaj de programare există construcții care nu pot fi realizate cu ajutorul gramaticilor liniare la dreapta. Dintre construcțiile de acest gen amintim: structurile bloc determinate de begin si end; expresiile aritmetice cu un număr arbitrar de paranteze balansate.

O gramatică independentă de context ( context-free) este o gramatică formală în care toate producțiile sunt de forma unde A este un simbol neterminal și . Se spune că L este un limbaj independent de context dacă există o gramatică independentă de context G care generează limbajul L, .

Originea gramaticilor independente de context se află în descrierea limbajelor naturale. Reguli de forma:

<enunț>:=<grup nominal><grup verbal>

<grup verbal>:=<verb><grup adverbial>, etc.,

sunt reguli de producție într-o gramatica independenta de context.

De asemenea definițiile sub forma Backus-Naur de forma

<identificator>:=<literă>/<identificator><literă>/<identificator cifră>, etc.,

sunt folosite pentru descrierea sintaxei limbajului ALGOL sunt reguli de productie într-o gramatică independenta de context.

În orice gramatica formala G, daca , , atunci .

§5.Proprietati de inchidere ale limbajelor independente de context

Propoziție. Dacă și sunt limbaje independente de context, atunci este un limbaj independent de context. Mai mult, dacă și sunt limbaje neambigue, disjuncte, atunci este un limbaj neambiguu.

Demonstrație. Putem considera că și sunt limbaje pe același alfabet terminal . Fie gramatici independente de context, astfel încât . Putem presupune că . Fie

unde S este un nou simbol. G este o gramatică independentă de context.

Este ușor de verificat că .

Fie . Dacă (, deoarece și sunt disjuncte), atunci există o singură derivație la stânga de forma

Rezultă că este singura derivație la stânga a secvenței w în gramatica G.

Asemănător se tratează cazul ().

Prin urmare gramatica G este neambiguă și este un limbaj independent de context neambiguu.

Propoziție. Clasa a limbajelor independente de context nu este inchisă la operațiile de intersecție și complementară.

Demonstrație. Fie și . este un limbaj independent de context fiind generat de gramatica:

este de asemenea un limbaj independent de context, fiind generat de gramatica

.

L nu este un limbaj independent de context. Deci nu este inchisă la intersecție.

Dacă ar fi inchisă la complementară, atunci din relația

ar rezulta că este închisă la intersecție, ceea ce este fals.

Rezulta ca mulțimea a limbajelor independente de context nu este o algebră boole de mulțimi.

Dacă este o secvență pe un alfabet dat, atunci se folosește notatia . Dacă L este un limbaj, atunci .

Propoziție. Dacă L este un limbaj independent de context pe alfabetul , atunci este un limbaj independent de context pe alfabetul .

Demonstrație. Fie o gramatică independentă de context, astfel încât . Fie unde .

G’ este de asemenea o gramatică independentă de context.

Se arată ușor că, pentru , are loc echivalența

În particular,

adică

Teoremă. (a substituției) Fie o substituție pe astfel încat , pentru orice . Dacă L este un limbaj independent de context pe alfabetul atunci este un limbaj independent de context.

Demonstratie. Fie și cu gramatici independente de context, astfel încât si . Putem presupune că mulțimile si sunt disjuncte.

Fie morfismul definit pe generatori prin și .

Construim gramatica independentă de context

unde

Fie . Există , astfel încât . Există , astfel încât . Există derivațiile:

Din (1), (2), (3) rezultă:

Din (4) și (5) obținem:

Rezultă. Deci .

Reciproc, fie . Ținând seama de (1) rezultă că există o derivație de forma

Tot din (1) rezultă

Rezultă și . Având în vedere că mulțimile sunt disjuncte,

Dacă notăm , atunci .

În final este un limbaj independent de context.

Consecință. Dacă și sunt limbaje independente de context ,(pe alfabetele , respectiv ) atunci și sunt limbaje independente de context.

CAPITOLUL III

PROBLEME REZOLVABILE ALGORITMIC PENTRU

LIMBAJE INDEPENDENTE DE CONTEXT

§1.Problema mulțimii vide.

Are următorul enunț: “Fiind dat un limbaj independent de context L să se determine dacă ”

Teoremă. Problema mulțimii vide pentru limbajele independente de context reprezentate prin gramatici independente de context este rezolvabilă algoritmic.

Demonstrație Fie o gramatică independentă de context și . Limbajul L este nevid dacă și numai dacă există o derivație de forma:

(1)

Condiția (1) este echivalentă cu S este un simbol productiv. Un simbol este productiv dacă există în gramatica G o derivație de forma . Algoritmul care rezolvă problema mulțimii vide pentru limbajele independente de context constă în determinarea simbolurilor productive și verificarea apartenentei .

Algoritmul care determină mulțimea a simbolurilor productive este următorul:

I: gramatică independentă de context

O: sau

M: 1.

2.

3.

4.Dacă atunci și mergi la 2.

5.Dacă atunci altfel

§2. Problema mulțimii infinite

Are următorul enunț:”Fiind dat un limbaj independent de context L să se determine dacă mulțimea L este infinită“.

Teoremă. Problema mulțimii infinite pentru limbajele independente de context reprezentate prin gramatici independente de context este rezolvabilă algoritmic.

Demonstrație. Fie L un limbaj generat de gramatica independentă de context G. Atunci există o gramatică G’ sub forma normală Chomsky care generează . L este infinit dacă și numai dacă L’ este infinit. Putem presupune că gramatica nu are simboluri inutilizabile. Asociem pentru gramatica G’ un graf construit astfel:

Vârfurile (nodurile) lui sunt simboluri neterminale ale lui G’. Daca , atunci există un arc de la A la B, dacă și numai dacă, în P există o producție de forma sau . Facem afirmația:

(2) În există un drum de lungime k de la A la B în raport cu gramatica G’ există o derivație de forma .

Afirmația (2) se demonstrează ușor prin inducție. Vom arăta că limbajul L este infinit dacă și numai dacă graful are cicluri.

Să presupunem mai întâi că graful are cicluri.

Există deci un drum de la un anumit vârf A, tot la A, de lungime . Conform (2) există o derivație de forma

Deoarece G’ este chiar o gramatică proprie, există derivații de forma:

(3)

Din (3) si (4) rezultă derivații de forma:

Deoarece secvențele distincte aparțin lui L, rezultă că L este infinit. Să presupunem că graful nu are cicluri. Atunci condițiile din (2) sunt echivalente și cu condiția că există un A-arbore în care un nod terminal are eticheta B. Deoarece nu are cicluri, orice drum în arborii generatori în raport cu G’ are lungime mai mică decât . Orice secvență generată de G’ are lungimea cel mult . Deci L’ (și L) este finit.

A rezultat echivalența:

“Limbajul L este infinit graful are cicluri”.

Un algoritm pentru rezolvarea problemei mulțimii infinite cuprinde următoarele etape:

Se dă L un limbaj generat de gramatica independentă de context G;

Se construiește gramatica G’ sub forma normală Chomsky care generează .

Pentru gramatica G’ se construiește graful ca mai sus.

Se cercetează dacă graful are cicluri (există algoritmi simpli pentru aceasta).

Dacă are cicluri, atunci L este infinit, altfel L este finit.

3. Problema apartenenței

Are urmatorul enunț: “Fiind dat un limbaj independent de context L pe un alfabet și o secvență , să se determine dacă .”

Considerăm că limbajul L este descris cu ajutorul unei gramatici independente de context. Vom arăta că problema apartenenței pentru limbaje independente de context este rezolvabilă algoritmic.

Dacă secvența w este secvența vidă, atunci simbolul inițial al gramaticii aparține mulțimii (conține toate simbolurile , ). Astfel că în continuare presupunem . Există mai multe abordări ale problemei.

Să presupunem mai întâi că gramatica G care generează L are forma normală Greibach. Producțiile gramaticii au forma . Fiecare producție într-o derivație aduce exact un simbol terminal. Dacă , atunci orice derivație a lui w are exact lungimea n. Pentru și să notăm numărul producțiilor de forma . Fie . Rezultă că o secvență de lungime are cel mult derivații la stânga în raport cu gramatica G. Pentru a determina dacă secvența este suficient să încercăm sistematic toate derivațiile la stânga de lungime n, în care pe locul i al secvenței derivate se află simbolul . Timpul necesar este de ordinul lui si crește exponențial cu lungimea n a secvenței w. Există și alți algoritmi pentru problema apartenenței în care timpul are un ordin mai mic.

Algoritmul CYK (Cocke- Younger- Kasami) presupune că gramatica G are forma normală Chomsky. Producțiile gramaticii G sunt de forma sau .

Considerăm că și folosim notația:

(1)

Din multimea fac parte acele neterminale care pot deriva în subsecvența de lungime j a lui w ce începe cu .Pentru , relația (1) devine:

astfel că mulțimile se pot calcula consultănd direct multimea P a producțiilor gramaticii G. Vom arăta că pentru mulțimile se pot calcula recursiv.

Fie și . Există derivația

(2)

Punem în evidență primul pas al derivației (2):

Există k, , astfel încât

și

Deci:

, astfel încât și

Deoarece k și j-k sunt mai mici decât j, rezultă că se poate calcula mulțimea în funcție de mulțimile , calculate anterior. În final, și dacă și numai dacă .

CAPITOLUL IV

LIMBAJE INDEPENDENTE DE CONTEXT

SI AUTOMATE PUSHDOWN

§1. Automate pushdown

Automatele pushdown constituie modelul natural al mecanismelor de recunoaștere (acceptare) a limbajelor independente de context.

Numele automatelor pushdown este dat de tipul memoriei auxiliare care este organizată tip stivă.

Banda de intrare (BI) este organizată la fel ca la un automat finit. Este împarțită în celule, limitată la stângă și nelimitată la dreapta. în fiecare celulă poate fi înscris un simbol al unui alfabet de intrare. Doar un număr finit de celule, începând cu prima din stânga, sunt ocupate.

Legătura între unitatea centrală (UC) și banda de intrare se face printr-un cap de intrare (CI). La un moment dat capul de intrare este plasat pe o celulă a benzii de intrare și citește conținutul acesteia. Capul de intrare se poate deplasa la dreapta câte o celulă. La momentul inițial capul de intrare este plasat pe prima celulă din stânga.

Memoria auxiliară este reprezentată sub forma unei benzi pushdown (BP). Banda pushdown sau banda internă este de asemenea împărțită în celule, limitată la un capat și nelimitată la celalalt. Este convenabil să reprezentăm banda pushdown pe verticală, cu capatul limitat in sus. Există în acest mod o celulă în vârful benzii. Conținutul memoriei auxiliare se reprezintă cu ajutorul unui alfabet intern. Doar un număr finit de celule ale BP, începând cu cea din vârf, sunt ocupate cu simboluri ale alfabetului intern.

Legătura între UC și BP se face printr-un cap de citit și scris (CCS) plasat totdeauna pe celula din vârful benzii. La un moment dat, CCS citește simbolul din prima celulă și îl înlocuiește cu o secvență. În functie de lungimea secvenței, celelalte simboluri pot fi "împinse în jos" un număr corespunzator de celule. Există și posibilitatea ca secvența care trebuie înscrisă să fie secvența vidă. În acest caz, celelalte simboluri sunt împinse câte o celulă în sus.

Unitatea centrala (UC) poate fi privită ca un program care dictează funcționarea automatului. UC se poate afla într-un număr finit de stări. Există o stare inițială a UC, după cum există și stări finale ale UC.

O descriere instantanee a automatului pushdown este numită configurație (C). O configurație cuprinde starea unității centrale, secvența rămasă de citit pe BI și conținutul memoriei auxiliare (continutul BP).

Trecerea de la o configuratie la alta se numeste pas. Există două tipuri de pași.

În primul tip, CI trece la simbolul următor de pe BI, simbolul din vârful BP este înlocuit cu o secvență și se schimbă starea unitații centrale.

Al doilea tip de pas, seamănă cu primul, în afara de CI care rămâne pe aceeași celulă. Acest tip de pas poate fi privit ca o transformare a conținutului memoriei auxiliare.

Automatul pushdown funcționează în mod nedeterminist. Pentru o configurație dată, pot exista mai multe configurații următoare. Automatul are mai multe evoluții în paralel.

Se pot defini și automate pushdown deterministe. Spre deosebire de cazul automatelor finite, automatele pushdown deterministe nu au aceeași putere de acceptare ca automatele nedeterministe.

Există doua tipuri de acceptare:

– după criteriul stării finale;

– după criteriul benzii vide;

O secvență este acceptată după criteriul stării finale dacă, automatul pushdown pornind din configurația inițială cu secvența w pe banda de intrare, ajunge într-o stare finală, după ce a terminat de citit w.

O secvență w este acceptată după criteriul benzii vide, dacă, automatul pushdown, pornind din configurația inițiala cu secvența w pe banda de intrare, după ce a terminat de citit w, a "golit" și memoria auxiliară (pe banda pushdown nu mai este înscris nici un simbol).

Definiție.Se numește automat pushdown un sistem

unde :

Q este o mulțime finită ale cărei elemente se numesc stări;

– este un alfabet de intrare;

– este un alfabet intern;

– este functia de tranzitie a automatului și

unde notează mulțimea părtilor finite ale lui ;

– și se numește stare inițială;

– și se numește simbol intern inițial;

-, elementele lui F se numesc stări finale.

Ca interpretare:

– elementele lui Q reprezintă stările unității centrale;

– simbolurile lui pot fi înscrise în celulele de pe BI;

– conținutul memoriei auxiliare se reprezintă cu ajutorul alfabetului intern . Simbolurile lui pot fi înscrise în celulele BP. Nu este obligatoriu ca și să fie disjuncte;

reprezintă un anumit conținut inițial al memoriei auxiliare;

funcția de tranziție reprezintă modul în care a fost programată unitatea centrală.

O valoare se interpretează astfel:

Dacă UC se află în starea p, capul de intrare citește simbolul a și în vârful BP se află simbolul Z, atunci:

– UC trece în starea q;

– CCS înscrie secvența în locul lui Z. În acest scop, celelalte simboluri de pe BP pot fi împinse în jos (sau în sus) un număr corespunzător de celule.

Definiție. Se numește configurație a automatului pushdown M, un triplet unde .

Ca interpretare, în configurația :

– q reprezintă starea curentă UC;

– w reprezintă secvența de pe BI rămasă de citit;

– reprezintă conținutul BP. Simbolul din vârful BP este primul simbol al lui .

Definiție. Relația trece direct între configurații se definește astfel:

dacă

unde .

Pentru relația se consideră:

– trece după i pași – puterea i a relației ;

– închiderea tranzitivă a relației ; la fel ca pentru automate finite.

Se observă că automatul pushdown poate face un pas (prin relația trece direct) chiar dacă pe BI nu a mai rămas nici un simbol de citit dar nu poate face nici un pas dacă pe BP nu există cel puțin un simbol Z. De asemenea, se observă că, fiecare pas al automatului depinde de simbolul din vârful BP și nu depinde de simbolurile plasate sub acesta. Deci, dacă

, atunci

Dacă pot apare confuzii, atunci trecerile în raport cu automatul M se notează

, respectiv și .

Definiție. Fie un automat pushdown. Numim limbaj acceptat de M după criteriul stării finale mulțimea

O configurație de forma este numită configurație inițială.

O configurație de forma cu este o configurație finală.

Cunoscând că un automat pushdown funcționează nedeterminist, M acceptă w după criteriul stării finale dacă există o evoluție a lui M, din configurația inițială într-o configurație finală.

Definiție. Fie un automat pushdown. Numim limbaj acceptat de automatul M după criteriul benzii vide, mulțimea:

În acceptarea după criteriul benzii vide nu intervin stările finale. Important este ca BP să fie "golită" după citirea secvenței w.

§2. Legatura dintre limbajele independente de context și automatele pushdown

Teoremă. Pentru orice limbaj independent de context L există un automat pushdown M, astfel încat .

Demonstrație. Fie o gramatică independentă de context, astfel încăt . Producțiile din P sunt de forma , unde și .

Construim automatul pushdown M astfel:

unde funcția de tranziție ,

ia următoarele valori:

i)

ii)

iii)Toate celelalte valori ale funcției sunt egale cu mulțimea vidă.

Automatul pushdown construit astfel face un pas corespunzător valorii (i) dacă simbolul din vârful benzii interne este un neterminal al lui G și face un pas corespunzător valorii (ii) dacă simbolul din vârful benzii interne este un simbol terminal al lui G. Valorile de tipul (i) arată că automatul M reproduce pe banda internă derivațiile din stânga ale gramaticii G.

Valorile de tipul ( ii) arată că, în caz de concordanță între simbolul citit pe banda de intrare și simbolul din vârful benzii interne, pe fiecare din cele două benzi se trece la simbolul următor.

Pentru și vom stabili echivalența:

(1)

Implicația "" o demonstrăm prin inducție după lungimea derivației .

Fie . Rezultă .

Conform (i), , deci

Conform (ii)

Deci .

Presupunem adevărată implicația "" pentru derivații de lungime mai mică decât un anumit și fie .

Punem în evidență primul pas al derivației:

Dacă , atunci, din () rezultă că secvența w admite reprezentarea

și

Conform ipotezei de inductie,

(2)

Din din (i), (ii) și (2), rezultă:

În final, .

Implicația "” din (1) o demonstrăm prin inducție după numărul de pași din .

Dacă , atunci, ținând seama de valorile funcției , deducem , deci .

Presupunem "" adevarată pentru un numar de pași mai mic decât un anumit și fie

(3)

Deoarece în vârful benzii interne se află un neterminal, primul pas în (3) se face cu o valoare de tipul (i):

(4)

Rezultă și

(5) ,

Fie prefixul lui care este citit pe banda de intrare până în momentul în care conținutul benzii interne devine prima dată mai scurt decât .

Deci: .

(6) ,

Din (5) și (6) rezultă

(7)

Se repetă raționamentul cu (7): este prefix pentru , etc.

În final:

(8) , ,

Conform ipotezei de inducție:

(9)

Din (4) și (9), deducem

și demonstrația echivalenței (1) se încheie.

Dacă în (1) luăm , atunci obținem:

sau adică .

Teoremă. Pentru orice automat pushdown M, există un automat pushdown M', astfel încât .

Demonstrație. Deoarece automatul M acceptă după criteriul benzii vide, putem presupune că M nu are stări finale. Construim automatul M' care să simuleze automatul M și care să intre în stare finală atunci când M a golit banda internă.

unde și sunt stări noi și este un simbol nou.

Valorile funcției de tranzitie ' sunt definite prin:

1.

2.

3.

4. Toate celelalte valori ale funcției ' sunt mulțimea vidă.

Valoarea (1) aduce automatul M’ în configurația inițială a automatului M, având în plus simbolul la baza benzii interne (a stivei).

Valorile de tipul (2) permit automatului M' să simuleze automatul M. Dacă simulând automatul M, automatul M' rămâne doar cu simbolul pe banda internă (situație care corespunde golirii benzii interne a lui M), atunci M' trece prin (3) în starea finală . Dacă în plus a fost citită toată intrarea, atunci M' este într-o configurație de acceptare. Aceste considerații pot fi reprezentate și în modul următor.

Fie .

(1)

Datorită (1):

(2)

Datorită (1) și (2):

(3)

Datorită (3):

(4)

Din (2),(3) și (4) rezultă

adică . Deci .

Urmărind funcționarea lui M' se observă că singurul mod de acceptare a unei secvențe de către M' este dat de tranziții de forma (2),(3),(4). Dar din (3) rezultă (1). Deci

adică. În final, .

Teoremă. Pentru orice automat pushdown M, există un automat pushdown M', astfel încât .

Demonstrație. În principiu automatul M' va simula automatul M. Automatul M' va avea o stare pe care o va folosi la golirea benzii pushdown. Pentru a evita acceptarea secvențelor care produc golirea simultană a benzii de intrare și a benzii pushdown, fără ca automatul să fie în stare finală, la baza stivei se plasează un simbol .

Automatul M' intră în starea numai în situația în care M' simulându-l pe M intră într-o stare finală.

Fie: automatul pushdown dat.

Construim

unde și sunt stări noi și este simbolul intern nou și unde valorile funcției ’ sunt definite prin:

1.

2. ;

3.

4. ;

5. Toate celelalte valori ale funcției ’ sunt mulțimea vidă.

Valoarea (1) aduce M' in configurația inițială a lui M, cu excepția faptului că la baza benzii pushdown (a stivei) a fost plasat simbolul .

Valorile de tipul (2) îi permit automatului M' să simuleze automatul M.

Dacă M' ajunge într-o stare , atunci M' poate face mai departe tranziții cu valori de tipul (2) sau poate intra în starea de golire printr-o valoare de tipul (3).

Valorile de tipul (4) permit golirea benzii interne.

Fie .

unde și .

Conform (1):

(1)

Conform (2) și (1) :

(2)

Dacă unde si , atunci din (2) și (3) rezultă:

(3)

Din (3) și din (4) rezultă:

(4)

Din (1), (2), (3) și din (4) rezultă:

(5)

adică .

A fost demonstrată incluziunea

Reciproc, fie .

unde . Singura tranziție a lui M' din starea

este cea data de (1), deci:

(6)

Ștergerea simbolului de pe banda internă se poate face numai cu o valoare de tipul (3) sau de tipul (4). Dacă ștergerea lui se face cu o valoare de tipul (3), atunci

deci și .

Tranzițiile se fac numai cu valori de tipul 2) și ca urmare

deci . Dacă ștergerea lui se face cu o valoare de tipul (4), atunci într-o configurație anterioară, automatul M' a intrat în starea . Din acel moment coținutul benzii de intrare nu se mai modifică. Trecerea în starea se poate face numai cu o valoare de tipul (3). Deci, reluând (6):

unde și .

Toate tranzițiile se fac cu valori de tipul (2) și prin urmare:

,

adică . A fost demonstrată incluziunea .

În final .

Teoremă. Pentru orice automat pushdown M, L(M) este un limbaj independent de context.

Demonstratie. Fie automatul pushdown

Vom construi o gramatică independentă de context G care generează .

Alfabetul neterminal al lui G va fi:

unde S este un simbol nou și are rolul de simbol inițial al gramaticii G.

Alfabetul terminal al lui G va fi chiar alfabetul de intrare al automatului pushdown M.

Mulțimea P a producțiilor gramaticii G este formată din următoarele producții:

1. , pentru orice

2. Dacă si

pentru orice .

3. Dacă , atunci .

Au fost definite toate componentele gramaticii .

Gramatica G este independentă de context. Rămâne să verificăm egalitatea

Pentru aceasta vom stabili mai întâi urmatoarea echivalență:

oricare ar fi .

Implicația "" o demonstrăm prin inducție după numărul de pași. Fie

Rezultă . Conform (3):

si .

Presupunem că "" are loc pentru tranziții ale automatului M cu un număr de pași mai mic decât un anumit . Fie . Scriem w sub forma unde și punem în evidență primul pas:

Deci și . Din (2) rezultă

(2)

pentru orice .

În tranziția

notăm cu prefixul lui y citit până în momentul în care conținutul benzii interne devine pentru prima dată egal cu . Fie starea automatului pushdown în acel moment. Deci .

(3)

(4)

Conform ipotezei de inducție, din (3) rezultă

(5)

Repetând raționamentul cu relația (4), deducem:

– exista stările

–

astfel încât

(6)

Conform ipotezei de inducție, din (6) rezultă:

(7)

În relația (2) alegem în rolul stărilor exact stările din relațiile (3) și (6). Din(2),(5) și (7) rezultă:

Implicația "" în (1) o demonstrăm prin inducție după lungimea derivației. Fie : .

Rezultă . Singurele produții de acest fel sunt cele de forma (3). Deci:

, și

Presupunem implicația "" din (1) adevărată pentru derivații de lungime mai mică decât un anumit . Fie

(8)

Primul pas în (8) se face folosind o producție de forma (2):

unde și

(9)

Va rezulta:

(10)

(11)

Din ipoteza de inducție și din relațiile (10) și (11) rezultă:

(12)

(13)

Din (9),(12) și (13) rezultă:

Se incheie demonstrația echivalenței (1).

Fie acum .

, pentru o anumită stare

Din (1) rezultă .

Conform (1), și, prin urmare:

adică . Am demonstrat că

(14)

Fie .

(15)

Primul pas în (15) se face cu o producție de forma (1), deci

(16)

Din (18) și (1) rezultă

adică . Am demonstrat

(17)

Din (14) și (17) rezultă .

Consecință. Fie un alfabet și L un limbaj pe alfabetul .. Sunt echivalente afirmațiile:

(i) L este un limbaj independent de context;

(ii) Există un automat pushdown care acceptă L după criteriul benzii vide;

(iii) Există un automat pushdown care acceptă L după criteriul stării finale.

CAPITOLUL V

LIMBAJE INDEPENDENTE DE CONTEXT DETERMINISTE

§1.Automate pushdown deterministe

În cazul general al unui automat pushdown

(1)

valorile funcției de tranziție aparțin mulțimii .

Prin urmare, pentru o configurație dată pot exista mai multe configurații următoare. Caracterul nedeterminist al unui automat pushdown rezultă și din urmatorul motiv.

Pentru o configurație dată este posibil ca ambele mulțimi și să fie nevide. În această situație este posibil atât un pas în care capul de intrare (CI) trece de la simbolul următor de pe banda de intrare, cât și un pas în care CI rămâne pe loc.

Definiție. Spunem că automatul pushdown este determinist dacă:

i)

ii)

Raportul între automatele pushdown nedeterministe și automatele pushdown deterministe nu este de aceeași natură cu cea pentru automatele finite. Automatele finite deterministe și automatele finite nedeterministe au aceeași putere de acceptare. Nu este cazul automatelor pushdown.

Limbajele si sunt independente de context. Prin urmare este un limbaj independent de context. Există un automat pushdown M care acceptă limbajul L. Totusi, nu există automate deterministe care să accepte L .

Se spune că este un limbaj independent de context deterministic dacă există un automat pushdown determinist care acceptă L.

Mulțimile regulate sunt limbaje independente de context deterministice. Prin urmare familia limbajelor independente de context deterministice este strict cuprinsă între familia mulțimilor regulate și familia limbajelor independente de context. Sintaxa mai multor limbaje de programare utilizează limbaje independente de context asupra cărora se pun de obicei diferite restricții. În general, acestea conduc la limbaje independente de context deterministe. Probabil cea mai importantă dinte aceste clase de limbaje este clasa limbajelor LR.

§2. Proprietăți ale limbajelor independente de context deterministe

Familia limbajelor independente de context deterministe este o submulțime proprie a familiei limbajelor independente.

Teoremă. Familia limbajelor independente de context nu este inchisă la intersecție și reuniune.

Demonstrație. Limbajele și sunt limbaje independente de context deterministe dar nu este limbaj independent de context. Din relațiile De Morgan și închiderea la complementară, rezultă că familia limbajelor independente de context deterministe nu este inchisă la reuniune.

Au fost demonstrate următoarele proprietăți privind limbajele independente de context deterministe ([1],[5],[11],[12]):

Fie și două automate pushdown deterministe. Următoarele probleme sunt nedecidabile:

este limbaj independent de context determinist

este limbaj independent de context determinist

este limbaj independent de context determinist

Fie P un automat pushdown determinist. Este decidabil dacă este regulat.

Fie si două automate pushdown deterministe. Este decidabil dacă .

Fie L un limbaj independent de context determinist și R un limbaj regulat. Următoarele limbaje sunt limbaje independente de context deterministe:

LR – L/R

LR – MAX(L)

MIN(L) – LR

Fie L un limbaj independent de context determinist și R un limbaj regulat. Următoarele

limbaje pot să nu fie limbaje independente de context deterministe:

RL

{x|xRL}

{x|yR, yxL}

h(L) unde h este homomorfism

Dacă L este un limbaj independent de context determinist și h este un homomorfism, atunci este determinist.

Fie L o familie de limbaje cu și . Fie . L este inchisă la:

reuniune marcată dacă L

concatenare marcată dacă L

* marcată dacă L

Familia limbajelor independente de context deterministe este inchisă la reuniune, concatenare și marcate.

§3. Gramatici LL(k)

Fie o gramatică neambiguă și . Atunci există o unică derivare la stânga astfel încât și . Dacă dorim ca secvența să poată fi determinată cunoscând primele j simboluri (partea din cuvântul de intrare citită până în acel moment), următoarele k simboluri (pentru un anumit k) și neterminalul A. Dacă aceste trei cantități determină în mod unic producția folosită pentru expandarea lui A, vom spune că gramatica G este LL(k). Vom considera că neterminalul care derivează este cel mai din stânga.

Definiție.Fie o gramatică independentă de context, k un număr natural și . Definim funcția astfel:

Definiție.Fie o gramatică independentă de context. Spunem că G este LL(K) dacă:

(1)

(2)

(3)

implică .

O gramatică este de tip LL dacă ea este LL(k) pentru un anumit k.

Teoremă. Fie o gramatică independentă de context. Atunci G este LL(k) dacă și numai dacă este adevărată condiția : astfel încât există derivarea și pentru orice producții distincte, rezultă .

Demonstrație. “” Fie G o gramatică este de tip LL(k). Presupunem prin reducere la absurd ca astfel încât pentru orice derivație și . Fie . Rezultă:

.

Am obținut

(1)

(2)

(3)

și totusi .Deci gramatica nu este LL(k). Ajungem la o contradicție, deci presupunerea făcută este falsă.

“” Presupunem prin absurd că G nu este LL(k); deci sunt adevărate conditiile 1), 2) și 3) din definiția gramaticii LL(k) și totusi . Conditia 1) implică existența derivației ; analog 2) implică . De aici și din 3) rezultă

Deci , contradicție. Rezultă că presupunerea făcută este falsă, deci G este LL(k).

Definiție. Fie o gramatică independentă de context. Definim funcția , unde k este un întreg pozitiv iar astfel:

Funcțiile PRIMk și URMk pot fi extinse la mulțimi de cuvinte formate peste alfabetul : dacă , atunci:

Definiție. Fie o gramatică independentă de context. Ea se numește LL(k) în sens tare dacă este satisfacută condiția: dacă sunt două A-producții distincte, atunci

Proprietate. Orice gramatică LL(1) este LL(1) în sens tare. Pentru k>1 această proprietate nu mai este adevărată.

§4. Gramatici LR(k)

Gramaticile LR au fost introduse în 1965 de catre Knuth iar clasa limbajelor generate de ele este clasa limbajelor independente de context deterministe. Analiza LR prezintă avantajul generalității, toate limbajele de programare ce acceptă o definiție sintactică BNF fiind analizabile LR.

Pentru efectuarea unei analize sintactice de tip LR se dispune de următoarele informații:

o pozitie inițială în cuvântul de analizat pe care o notăm cu p,

întregul context stânga al cuvântului sursă, adică

următoarele k simboluri ale sursei situate după poziția p, adică ,

analiza ce se efectuează este o analiză la dreapta; adică la fiecare pas, neterminalul care derivează este cel mai din dreapta.

Gramatica G trebuie să aibă astfel de proprietăți încât informațiile 1-4 să ne asigure următoarele:

dacă p indică sau nu limita dreapta a părții reductibile,

dacă p indică limita dreaptă a părții reductibile atunci 1-4 determină și limita din stânga,

dacă a fost determinată partea reductibilă, 1-4 determină și productia ce va fi utilizată pentru reducere.

Fie o gramatică independentă de context și . Pentru vrem să determinăm șirul astfel încât: . Fie și ; informațiile 1-4 trebuie să determine în mod unic producția folosită în derivarea . În cazul gramaticilor LR toate derivările sunt la dreapta.

Definiție. Fie o gramatică independentă de context. Se numește gramatica extinsă a lui G, gramatica unde . Producția o vom numerota cu 0 iar celelalte cu 1,2,…,p.

Definiție. Fie o gramatică independentă de context și gramatica sa extinsă.G este LR(k), , dacă:

(1)

(2)

(3)

implică ( adică ).

Definiție. Cuvântul este un prefix viabil în gramatica dacă și este un prefix al lui ; se numește partea deschisă.

Definiție. Fie o gramatică independentă de context. Vom spune că este linie LR(k), dacă și . se numește nucleul iar u șirul de anticipare al liniei.

Definiție. Linia LR(k) este validă pentru prefixul viabil dacă există o derivare de forma și .

Definiție. Funcția (-free first) este o restricție a funcției PRIM și este definită astfel:

și

și ultima producție folosită nu este -producție când .

Lemă. Fie o gramatică extinsă care nu este LR(k). Atunci:

(1)

(2)

(3)

(4)

implică .

Demonstrație.Din definiția gramaticii LR(k) deducem că pot fi satisfăcute toate condițiile din lemă exceptând . Presupunând se ajunge la contradiția .

Teoremă. O gramatică este LR(k) dacă și numai dacă este indeplinită următoarea condiție, pentru orice : dacă este linie LR(k) validă pentru prefixul viabil atunci nu există nici o altă linie validă pentru cu .

Demonstrație.”” Presupunem prin absurd că și există prefixul viabil astfel încât și sunt două linii valide pentru prefixul . Înseamnă că:

cu

cu

și . În plus, , .

Cazul I. Dacă atunci și

Deoarece cele două linii LR(k) sunt distincte, înseamnă că fie , fie . În plus, , deci G nu este LR(k).

Cazul II. Dacă atunci

,

,

În acest caz G nu poate fi LR(k) deoarece .

Cazul III. Presupunem că conține cel puțin un simbol neterminal. Atunci unde , deoarece conform definiției, și prin urmare un simbol neterminal de început nu poate fi înlocuit prin cuvântul vid. Astfel, avem derivațiile:

cu . Deci .

Deoarece gramatica este LR(k) rezultă că , adică , egalitate imposibilă deoarece .

“”Presupunem că G nu este LR(k). Atunci avem

dar . Putem alege derivările astfel încât să aibă lungimea cât mai mică posibil. Ținând seama de lemă presupunem că . Notăm cu ultima formă derivațională la dreapta în derivarea astfel încât lungimea părții sale deschise nu depășește , adică .

Derivarea de mai sus se poate scrie cu . Din alegerea lui avem . În plus , în derivarea nu se folosește ca ultimă producție o -producție, căci dacă ar fi ultima producție folosită atunci nu ar fi ultima formă derivațională la dreapta în derivarea a cărei parte deschisă nu depășeste în lungime . Astfel, .Rezultă că este linie LR(k) valida pentru , unde .

Din deducem că este linie validă pentru .

Să arătăm acum că liniile și sunt distincte. Pentru aceasta presupunem contrariul; deci coincide cu

Atunci ultima derivare de mai sus este de forma

cu . Atunci și , contrar ipotezei că G nu este LR(k).

BIBLIOGRAFIE

Aho A., Ullman J., The theory of Parsing, Translation and Compiling, Prentice-Hall, 1972.

Căzănescu V., Introducere în teoria limbajelor formale, Editura Academiei, București, 1983.

Dincă A., Andrei M., Limbaje formale si aplicatii, Editura Universitaria, Craiova, 2002, pp316.

Hopcroft J., Ullman J., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.

Hopcroft J., Ullman J., Formal Languages and their Relation to Automata, Addison-Wesley, 1969.

Iancu I., Proiectarea compilatoarelor, Editura Universitaria, Craiova, 2002.

Marcus S., Gramatici și automate finite, Editura Academiei, Bucuresti, 1964.

Salomaa A., Formal Languages, Academic Press, New York, 1973.

Salomaa A., Rozenberg G., Handbook of Formal Languages, Springer, 1977.

Rus T., Mecanisme formale pentru specificarea limbajelor, Editura Academiei, București, 1983.

Simovici D., Limbaje formale și tehnici de compilare, Editura didactică și pedagogică, București, 1978.

Serbănați L.D., Limbaje de programare și compilatoare, Editura Academiei, București, 1987.

Vaida D., Limbaje formale și tehnici de compilare, Tipografia Universității din București, 1976.

Vaida D., Limbaje formale și tehnici de compilare, Tipografia Universității din București, 1984.