Limbaje Formale Si Automate 1

2.1 Gramatici ......................................................................................................................2.1.1 Ierarhia Chomsky...............................................................................................................

2.1.1.1 Exerciii .............................................................................................................................2.1.2 Verificarea limbajului generat de ctre o gramatic

2.1.2.1 Exerciii ............................................................................................................................. 2.1.3 Transformri asupra gramaticilor independente de context............................................................. 11

2.1.3.1 Eliminarea ambiguitii............................................................................................................... 12 2.1.3.2 Eliminarea - produciilor .......................................................................................................... 16 2.1.3.3 Eliminarea recursivitii stnga................................................................................................... 16 2.1.3.4 Factorizare stnga ............................................................................................................. 2.1.3.5 Eliminarea simbolilor neterminali neutilizai.............................................................................. 19 2.1.3.6 Substituia de nceputuri(corner substitution)............................................................................. 20

2.1.4 Construcii dependente de context ................................................................................................... 22 2.1.4.1 Exerciii ...................................................................................................................................... 23

2.1.5 Proprieti ale limbajelor independente de context.......................................................................... 24 2.1.5.1 Exerciii ...................................................................................................................................... 25

2.2 Mulimi regulate, expresii regulate. ...................................................................................................... 25

2.3 Acceptoare............................................................................................................................................... 28 2.3.1 Automate finite ................................................................................................................................ 29

2.3.1.1 Construcia unui automat finit nedeterminist care accept limbajul descris de o expresie regulat dat 30

2.3.1.2 Conversia unui automat finit nedeterminist (AFN) ntr-un automat finit determinist(AFD)...... 34 2.3.1.3 Construcia unui automat finit determinist care accept limbajul descris de o expresie regulat

dat 37 2.3.1.4 Simularea unui automat finit determinist.................................................................................... 43 2.3.1.5 Simularea unui automat finit nedeterminist ................................................................................ 44 2.3.1.6 Probleme de implementare pentru automatele finite deterministe i nedeterministe.................. 45 2.3.1.7 Minimizarea numrului de stri pentru AFD.............................................................................. 46

LIMBAJE FORMALE SI AUTOMATENotite de curs

AndreiTextFor Evaluation Only.Copyright (c) by VeryPDF.com IncEdited by VeryPDF PDF Editor Version 2.2

2.3.2 Automate cu stiv (pushdown) ........................................................................................................ 49 2.3.2.1 Automate cu stiv cu acceptare prin stiv goal ......................................................................... 52 2.3.2.2 Relaia ntre automate cu stiv i limbajele independente de context......................................... 53

2.3.3 Maina Turing.................................................................................................................................. 57 2.3.3.1 Calcule realizate de Maina Turing ............................................................................................ 60 2.3.3.2 Compunerea mainilor Turing .................................................................................................... 63 2.3.3.3 Extensii pentru maina Turing.................................................................................................... 67 2.3.3.4 Automate liniar mrginite ........................................................................................................... 73 2.3.3.5 Relaia ntre maina Turing i gramatici ..................................................................................... 74 2.3.3.6 Elemente de calculabilitate ......................................................................................................... 77

2.3.3.6.1 Maina Turing Universal ................................................................................................... 77 2.3.3.7 . Maina Turing cu limit de timp............................................................................................... 81


Fie T o mulime de simboluri denumita alfabet. Orice submulime a mulimii T* reprezint un limbaj

asupra alfabetului T. Elementele limbajului se numesc propoziii. Dac limbajul este finit atunci el poate s fie definit prin enumerare. De exemplu considernd alfabetul B = {0, 1} atunci L = {01, 10, 101} este un limbaj. Mulimea cuvintelor din limbajul natural este i el un limbaj pentru care se poate pune problema enumerrii tuturor cuvintelor, chiar dac lista care ar rezulta este imens, deci este un limbaj reprezentabil prin enumerare. Dar cazul interesant este cel n care limbajul este infinit. S considerm de exemplu limbajul "irurilor formate din 0 i 1 a cror lungime este divizibila cu 3". Evident este vorba de un limbaj infinit. Textul prin care am specificat limbajul constituie o reprezentare finit a limbajului. Nu este singura soluie posibil de reprezentare finit. De exemplu dac notam cu L limbajul respectiv atunci:

L = { w {0,1}* | |w| mod 3 = 0} este un alt mod de a specifica acelai limbaj. Se pune problema dac dndu-se un limbaj oarecare este posibil ntotdeauna construirea unei

reprezentri finite. S considerm c o astfel de reprezentare finit se realizeaz utiliznd simboli dintr-un alfabet finit A. Se poate demonstra c mulimea A* este infinit numrabil (se poate construi o bijecie f : N A*). Deci exist o mulime infinit numrabil de reprezentri finite. Numrul de limbaje ce se pot construi utiliznd simboli dintr-un alfabet dat T, este 2|T*| deci mulimea limbajelor este infinit nenumrabila. Rezult deci c ar trebui s reprezentm un numr infinit nenumrabil de obiecte avnd la dispoziie numai un numr infinit numrabil de reprezentri. Din acest motiv nu orice limbaj va putea s fie reprezentabil ntr-un mod finit. Nu putem s oferim un exemplu de limbaj pentru care nu avem o reprezentare finit pentru c exemplul ar fi tocmai o reprezentare finit a limbajului respectiv. Spre norocul nostru, nu suntem interesai de toate limbajele ci numai de o clas mai mic a limbajelor infinite cu reprezentri finite.

n general exist doua mecanisme distincte de definire finit a limbajelor: prin generare sau prin recunoatere. n primul caz este vorba de un "dispozitiv" care tie s genereze toate propoziiile din limbaj (i numai pe acestea) astfel nct alegnd orice propoziie din limbaj ntr-un interval finit de timp dispozitivul va ajunge s genereze propoziia respectiv. n al doilea caz este vorba de un "dispozitiv" care tie s recunoasc (s accepte ca fiind corecte) propoziiile limbajului dat.

2.1 Gramatici O gramatic reprezint cel mai important exemplu de generator de limbaje. Prin definiie o gramatic

este G = (N, T, P, S) unde :

N este o mulime finit de simboli numit mulimea simbolilor neterminali; T este o mulime finit de simboli numit mulimea simbolilor terminali,

(T N = ); P este o submulime finit din (N T)* N (N T)* x (N T)*; numit mulimea produciilor

gramaticii. Un element (, ) P este notat cu i se numete producie. S N este un simbol special numit simbol de start al gramaticii G.

n cele ce urmeaz vom utiliza o serie de notaii devenite "clasice". i anume :

literele mici de la nceputul alfabetului latin (a,b,c,...) reprezint elemente din T (simboli terminali); literele mici de la sfritul alfabetului latin (u, v, x,...) reprezint elemente din T* (iruri de simboli

terminali);

1 Elemente de teoria limbajelor formale


literele mari de la nceputul alfabetului latin (A, B, C,...) reprezint elemente din N (simboli neterminali);

literele mari de la sfritul alfabetului latin (U, V, X,...) reprezint elemente din N T (simboli terminali sau neterminali);

literele alfabetului grecesc (, , ...) reprezint iruri din (N T)* (iruri de simboli terminali i neterminali). O form propoziional pentru o gramatic G se definete recursiv n modul urmtor: (1) S este o form propoziional; (2) dac este o forma propoziional i exist o producie atunci este o form propoziional. O form propoziional care conine numai simboli terminali se numete propoziie generat de G.

Notm cu L(G) mulimea tuturor propoziiilor generate de G altfel spus L(G) este limbajul generat de gramatica G.

Se observ c o gramatic este o reprezentare finit (toate elementele sale sunt finite) pentru un limbaj care poate s fie infinit. Conform observaiei fcute la nceputul acestui capitol nu orice limbaj are o reprezentare finit, cu alte cuvinte nu pentru orice limbaj exist o gramatic care s l reprezinte.

Dou gramatici G i G' sunt echivalente dac i numai dac L(G) = L(G'). Asupra formelor propoziionale se definete o relaie numit relaie de derivare n modul urmtor.

Fie i doua forme propoziionale, dac i numai dac exist w1, w2 i P astfel nct = w1 w2 i = w1 w2.

Relaia poate s fie extins obinndu-se derivarea n k pai. i anume k dac exist 0, 1, ..., k forme propoziionale astfel nct = 0, i-1 i ,1 i k i k = .

nchiderea tranzitiv a relaiei se noteaz cu + . nchiderea tranzitiv i reflexiv a relaiei se noteaz cu =*>.

S considerm de exemplu gramatica G = ({A,S}, {0,1}, P, S) unde P = {S 1A1, S 0S0, 1A 11A1, A } (cu s-a notat irul vid de simboli). O derivare posibil este:

S 0S0 00S00 001A100 0011A1100 00111100

deci 00111100 este o propoziie n L(G). n general L(G) = { w | w T+, S + w}.

2.1.1 Ierarhia Chomsky. Noam Chomski este lingvist i lucreaz n domeniul limbajelor naturale. Ierarhia care i poarta

numele a rezultat dintr-o ncercare a acestuia de a formaliza limbajele naturale. Gramaticile sunt clasificate conform complexitii produciilor n urmtoarea ierarhie :

gramatici de tip 0 (fr restricii) - au produciile de forma:

cu (N T)* N (N T)* , (N T)*

gramatici de tip 1 (dependente de context) - au produciile de forma : A , , (N T)*, A N, (N T)+


sau de forma S n al doilea caz S nu apare n membrul drept al nici unei producii. Se utilizeaz termenul de

dependen de context deoarece producia A poate s fie interpretat sub forma - dac simbolul neterminal A apare ntre i atunci poate s fie nlocuit cu .

gramatici de tip 2 (independente de context) - au produciile de forma :

A , A N, (N T)*.

Denumirea de independent de context apare n contrast cu gramaticile de tipul 1 (dependente de context)

gramatici de tip 3 (regulate la dreapta) au producii de forma:

A aB cu A N , B (N {}) si a T+. Corespunztor gramaticilor, despre limbajele generate de acestea se poate spune respectiv c sunt

regulate, independente de context, dependente de context sau de tipul zero. Se poate arata c un limbaj ce poate s fie generat de o gramatic regulat poate s fie generat i de ctre o gramatic independent de context. Un limbaj independent de context poate s fie generat i de o gramatic dependent de context iar un limbaj dependent de context poate s fie generat i de o gramatic de tipul zero. Deoarece cu ct o gramatic este mai restrictiv ea reprezint un mecanism mai simplu, suntem ntotdeauna interesai de cea mai restrictiv gramatic care reprezint un limbaj dat.

S considerm cteva exemple: a) G1 = ({S},{0,1},{S 0S, S 1S, S }, S). Se observ c G1 este o gramatic regulat care

genereaz limbajul {0,1}* b) G2 = ({S, A},{0,1},{S AS, S , A , A 0, A 1}, S). Se observ c G2 este o

gramatic independent de context iar limbajul generat este tot {0,1}*. Rezult deci c un acelai limbaj poate s fie definit de mai multe gramatici diferite eventual chiar de tipuri diferite.

c) G3 = ({, T, F},{a, +, *, (, )}, P, ) cu P = { + T, T, T T * F, T F, F (), F a}. S considerm un exemplu de derivare n aceast gramatic :

+ T T + T F + T a + T a + T * F a + F * F a + a * F a + a * a. Se observ c gramatica G3 este o gramatic independent de context i este o gramatica care descrie

limbajul expresiilor aritmetice cu paranteze care se pot forma cu operandul a i cu operatorii + i *. n cele ce urmeaz pentru simplificarea notaiilor dac pentru un neterminal exist mai multe producii

: A w1, A w2, ... A wk le vom reprezenta sub o form mai compact: A w1 | w2 | ... | wk. De asemenea pentru specificarea unei gramatici nu vom mai preciza n general dect mulimea

produciilor sale, celelalte elemente rezultnd n mod banal din aceasta.

2.1.1.1 Exerciii S se construiasc gramaticile care genereaz limbajul:


1. irurilor formate din simboli a i b avnd un numr egal de a i b. 2. {anbn | n 1} 3. {anbmcmdn | n 1, m 1} 4. {anbncmdm | n 1, m 1} 5. irurilor formate cu simboli a i b care nu conin subirul abb 6. irurilor formate cu simboli a i b avnd lungimea divizibil cu 3 7. {aibj | i /= j, i, j > 0} 8. {ambn | n < m sau n > 2m, n, m 1} 9. irurilor formate dintr-un numr par de simboli a i un numr impar de simboli b 10.irurilor formate din simboli a, b i c, pentru care toi simboli a apar nainte de toi simboli b iar toi simboli b apar nainte de toi simboli c 11.{anbncn | n >_ 1} 12.{xcxR |x {a,b}*}, {xxR|x {a,b}*}, {x = xR|x {a,b}*} 13.{xx | x {a,b}*} 14.{anbncn | n 1 } 15.listelor de elemente care pot s nu conin nici un element, respectiv trebuie s conin cel puin un element, construirea listei este asociativ dreapta respectiv stnga (vor rezulta 4 variante)

2.1.2 Verificarea limbajului generat de ctre o gramatic n toate exemplele considerate pn acum s-a fcut "ghicirea" gramaticii care genereaz un limbaj dat

sau a limbajului generat de ctre o gramatic dat. Se pune ns problema cum se poate demonstra corectitudinea rezultatului unei astfel de ghiciri. S considerm de exemplu gramatica:

G = ({S}, {(,)}, {S (S)S | }, S) Aceast gramatica genereaz toate irurile de paranteze bine nchise (echilibrate). Dorim ns s

demonstrm aceast afirmaie. De fapt aici trebuie s demonstrm egalitatea a dou mulimi: mulimea reprezentat de limbajul generat de G i mulimea irurilor de paranteze bine formate. Deci demonstraia presupune demonstrarea dublei incluziuni. Adic trebuie s demonstrm c orice ir derivat din S satisface condiia enunat i apoi trebuie s demonstrm incluziunea n sens invers. Dndu-se un ir de paranteze bine nchise trebuie s artm c acest ir poate s fie derivat din S. Pentru prima parte a demonstraiei vom utiliza inducia asupra numrului de pai n derivare. Considerm c irul vid care se obine ntr-un pas din S este un ir de paranteze bine nchise. S presupunem c pentru toate derivrile realizate n mai puin de n pai se obin iruri de paranteze bine nchise i s considerm o derivare de exact n pai. O astfel de derivare poate s arate ca :

S (S)S * (x)S * (x)y unde x i y sunt iruri de terminale derivate din S n mai puin de n pai, adic sunt iruri de paranteze

bine nchise. Rezult c irul (x)y este un ir de paranteze bine nchise. Cu alte cuvinte orice ir derivat din S este "corect".

S considerm acum i includerea n sens invers. De data asta demonstraia se face prin inducie asupra lungimii irului. Pentru primul pas observm c irul vid este un ir derivabil din S. S presupunem acum ca orice ir cu mai puin de 2n simboli este derivabil din S. S considerm un ir w de paranteze bine nchise avnd lungimea de 2n, cu n mai mare sau egal cu 1. Sigur irul ncepe cu o parantez deschis. Fie (x) cel mai scurt prefix format din paranteze bine nchise. Se observ c w = (x)y, unde x i y sunt iruri


de paranteze bine nchise de lungime mai mic dect 2n. n acest caz x i y pot s fie derivate din S. Rezult c exist o derivare:

S (S)S * (x)y n care pentru obinerea irurilor x i respectiv y s-au utilizat mai puin de 2n pai i deci w este un ir

derivabil din S. Desigur o astfel de demonstraie este practic imposibil de realizat pentru un limbaj "adevrat". n general se pot face ns demonstraii "pe poriuni".

2.1.2.1 Exerciii

1. Fie gramatica G : S AA, A AAA, a, A bA, Ab, s se arate ca limbajul L(G) este limbajul tuturor irurilor formate din simboli a avnd un numr par de simboli.

2. Fie gramatica G : S aB | bA, A a | aS | bAA, B b | bS | aBB s se arate ca L(G) este setul tuturor irurilor din {a,b}+ care au un numr egal de apariii pentru a i pentru b.

2.1.3 Transformri asupra gramaticilor independente de context Din punctul de vedere al procesului de compilare, gramaticile sunt utilizate pentru faza de analiz

sintactic, pentru care se utilizeaz gramatici independente de context. Exist o serie de metode de analiza sintactic, bine puse la punct att din punct de vedere teoretic ct i practic. Fiecare dintre aceste metode impune ns o serie de restricii asupra gramaticilor utilizate. n general atunci cnd se construiete o gramatic se pleac de la forma general a structurilor pe care aceasta trebuie s le descrie i nu de la metoda de analiza sintactica ce va fi utilizat. n acest mod se obine o gramatic ce poate s fie "citit" uor de ctre proiectant. Pentru a satisface ns condiiile impuse de ctre metodele de analiza sintactic sau de ctre generarea de cod, se realizeaz transformri asupra gramaticilor. Aceste transformri trebuie s pstreze neschimbat limbajul generat. n cele ce urmeaz vom prezenta cteva transformri tipice asupra gramaticilor independente de context. Pentru a explica semnificaia acestor transformri n contextul analizei sintactice vom prezenta nti noiunea de arbore de derivare.

Un arbore de derivare este o reprezentare grafic pentru o secven de derivri (de aplicri ale relaiei ntre formele propoziionale). ntr-un arbore de derivare nu se mai poate identifica ordinea n care s-a fcut substituia simbolilor neterminali. Fiecare nod interior arborelui, reprezint un neterminal. Descendenii unui nod etichetat cu un neterminal A sunt etichetai de la stnga la dreapta prin simbolii care formeaz partea dreapt a unei producii care are n partea stnga neterminalul A. Parcurgnd de la stnga la dreapta frunzele unui astfel de arbore se obine o form propoziional. S considerm de exemplu din nou gramatica irurilor de paranteze bine formate:

G = ({S}, {(,)}, {S (S)S | }, S) Fie urmtoarea secven de derivri: S ( S ) S ( ( S ) S ) S ( () S ) S ( () ( S ) S ) S ( () () S ) S ( () () ) S ( () () ) ( S ) S + ( ()() ) () Se obine arborele de derivare:


S

/ / \ \ / / \ \ / / \ \ ( S ) S

/ / \ \ / / \ \ / / \ \ ( S ) S / / \ \ | | ( S ) S | / / \ \ / / \ \ ( S ) S | |

Arborele de derivare este construit de ctre analizorul sintactic. Aceasta construcie se poate face pornind de la rdcin aplicnd succesiv producii - n acest caz se spune c analiza sintactic este top-down (descendent). Dar, se poate porni i invers de la irul de atomi lexicali (frunze) identificndu-se simbolii neterminali din care se poate obine un ir de atomi lexicali. n acest caz se spune c analiza sintactic este de tip bottom-up (ascendent).

Deoarece arborele de derivare descrie relaia ierarhica ntre entitile sintactice (neterminale) i atomii lexicali (terminale) se poate asocia o interpretare n termeni de evaluare a entitilor sintactice. Astfel, considernd de exemplu gramatica expresiilor aritmetice pentru irul a + a * a se obine arborele derivare :

/ | \ / | \ + T | / | \ T / | \ | T * F F | | | F a a | a

n care se poate observa c a fost evideniat faptul c operaia de nmulire este prioritar fa de operaia de adunare (aspect semantic).

2.1.3.1 Eliminarea ambiguitii O gramatic care produce mai muli arbori de derivare pentru aceeai propoziie este o gramatic

ambigu. Deoarece exist tehnici de analiz sintactic care lucreaz numai cu gramatici neambigue vom ncerca s construim gramatici care genereaz acelai limbaj i care sunt neambigue. S considerm de exemplu urmtoarea gramatic :

instr if expresie then instr | if expresie then instr else instr | alte_instr S construim arborele de derivare pentru propoziia :


if E1 then if E2 then S1 else S2

instr / /\ \ / / \ \ / / \ \ / expr \ \ / / \ then \ if / E1 \ \ ------- instr / /\ \ \ \ / / \ \ \ \ / / \ \ \ \ / expr \ \ \ \ / / \ then \ \ \ if / E2 \ \ \ \ ------- instr \ \ / \ else \ / S1 \ instr ------ / \ / S2 \ ------

Pentru aceast propoziie mai exist ns un arbore de derivare. instr / / \ \ \ \ / / \ \ \ \ / / \ \ \ \ / expr \ \ \ \ / / \ then \else \ if / E1 \ \ \ ------- instr instr / \ / \ / /\ \ / S2 \ / / \ \ ------ if / then\ expr instr / \ / \ / E2 \ / S1 \ ------ ------

n toate limbajele de programare care accept construcii de tip if then else se consider cu sens prima

derivare n care fiecare clauza else este atribuit instruciunii if cea mai interioar. Rezult deci condiia pe care trebuie s o satisfac o instruciune if. Instruciunea cuprins ntre then i else trebuie s nu fie o instruciune if sau s fie o instruciune if cu clauza else. Rezult urmtoarea gramatic obinut prin transformarea gramaticii anterioare:

instr if_cu_else| if_fara_else if_cu_else if expresie then if_cu_else else if_cu_else | alte_instr if_fara_else if expresie then instr | if expresie then if_cu_else else if_fara_else Se observ c aceast gramatic genereaz acelai limbaj cu gramatica anterioar dar accept o

derivare unic pentru propoziia :


if E1 then if E2 then S1 else S2 instr | if_fara_else / /\ \ / / \ \ / / \ \ / expr \ \ / / \ then \ if / E1 \ \ ------- instr | if_cu_else / /\ \ \ \ / / \ \ \ \ / / \ \ \ \ / expr \ \ \ \ / / \ then \ \ \ if / E1 \ \ \ \ ------- instr \ \ / \ else \ / S1 \ instr ------ / \ / S2 \ ------

Se numete producie ambigu o producie care are n partea dreapt mai multe apariii ale aceluiai

simbol neterminal. Existena unei producii ambigue nu implic faptul c gramatica este ambigu. S considerm gramatica G = ({S, A}, {a, b, c }, {S aAbAc, A a | b}). Se observ c aceast gramatic nu este ambigu, gramatica genernd limbajul {aabac, aabbc, abac, abbc}

S considerm de exemplu i gramatica pentru expresii aritmetice: G = ({}, {a, +, *}, { + | * | a}, ) Gramatica G este o gramatic ambigu (se poate verifica uor utiliznd de exemplu irul a + a * a). n

gramatica G nu au fost evideniate relaiile de preceden dintre operatori. Aceasta gramatica poate s fie transformata ntr-o gramatica neambigu n care operaia de nmulire este mai prioritar dect cea de adunare n doua moduri:

1. + T | T T T * F | F F a

2. T + | T T F * T | F F a

Fie irul a * a * a. Pentru cele doua gramatici se obin arborii de derivare respectivi:


| | T T / | \ / | \ / | \ / | \ T * F F * T / | \ | | / | \ / | \ a a / | \ T * F F * T | | | | F a a F | | a a

Se observ c primul arbore evideniaz asociativitatea stnga a operatorului * n timp ce al doilea arbore evideniaz asociativitatea dreapta. n funcie de definiia limbajului este de preferat prima variant sau a doua.

n cazul general dac pentru un neterminal A exist produciile: A A B A | 1 | 2 | ... | n , BN, 1, ... n T* acestea pot s fie nlocuite cu: A A' B A | A' A' A | 1 | 2 | ... | n

Producia A' A poate s fie eliminat (exist i A A') i se obine: A A' B A | A'

A' 1 | 2 | ... | n Dac se construiete arborele de derivare se observ c n acest caz se utilizeaz asociativitatea

dreapt. Pentru a se descrie asociativitatea stnga se utilizeaz transformarea: A A B A' | A' A' 1 | 2 | ... | n. Trebuie s remarcam ns faptul c exist limbaje pentru care nu se pot construi gramatici neambigue.

Un astfel de limbaj se numete inerent ambiguu. De exemplu limbajul : L = { aibjckdl | i = k sau j = l, i, j, k, l 0} este inerent ambiguu. O gramatic care descrie acest limbaj va trebui probabil s considere c L este

de fapt reuniunea a dou limbaje: L = { anbjcndl | n, j, l 0} i L = { aibnckdn | i, n, j, k 0} Un ir de forma apbpcpdp va face parte din ambele limbaje i deci probabil c va avea doi arbori de

derivare. Exemplul anterior nu constituie ns o demonstraie, o demonstraie adevrat depete ca dificultate cadrul textului curent.


2.1.3.2 Eliminarea - produciilor Se spune ca o gramatic este - free dac satisface una dintre urmtoarele condiii:

a. Nu exist nici o producie care s aib n partea dreapta irul vid b. Exist o singura producie care are n partea dreapta irul vid i anume o producie de forma S

. Simbolul S nu apare n acest caz n partea dreapt a nici unei producii. Algoritmul de transformare pleac de la gramatica G = (N, T, P, S) i construiete gramatica G' = (N',

T, P', S') care satisface condiiile : (i) L(G) = L(G') (i) G' este - free. Descrierea algoritmului este : i = 0 Ni = {A | A P} repeta

i = i + 1 Ni = { A | A P, a N*i-1} Ni-1

pn Ni = Ni-1 Ne = Ni dac S Ne

N' = N {S'} P' = {S' , S' S}

altfel N' = N S' = S P' =

pentru fiecare p P executa

dac p este de forma : A a0 B1 a1 ... Bk ak, k 0, Bi Ne, 1 i k, aj ((N \ Ne) T)*, 0 j k

P' = P' ({A a0 X1 a1 ... Xk ak | Xi {Bi, }} \{A })

altfel P' = P' {p} Fie de exemplu gramatica S aSbS | bSaS | . Aplicnd algoritmul anterior se obine: S' S, S aSbS | aSb | abS | ab | bSaS | bSa | baS | ba

2.1.3.3 Eliminarea recursivitii stnga O gramatic este recursiv stnga dac exist un neterminal A astfel nct exist o derivare A + A

pentru (T N)*. O analiz sintactic descendent determinist nu poate s opereze cu o astfel de gramatic, deci este necesar o transformare. S considerm nti cazul cel mai simplu pentru care n gramatic exist producii de forma A A | . n acest caz limbajul generat este de forma n cu n 0. Acelai limbaj poate s fie generat de ctre gramatica: A A', A' A'| .


S considerm de exemplu gramatica expresiilor aritmetice : + T | T, T T * F | F, F () | a Se observ c pentru un ir de forma a + a * a, examinnd numai primul simbol terminal(a) nu este

clar cu care dintre produciile pentru trebuie s se nceap derivarea. Aplicnd ideea anterioar se obine :

T ', ' +TE' | , T FT', T' *FT' | , F () | a n acest caz derivarea va ncepe sigur prin aplicarea produciei TE' i se obine derivarea TE'

FT''. n acest moment se vede c pentru F trebuie s se aplice producia F a. Deci se obine + aT''. Urmeaz simbolul terminal + datorit cruia pentru T' se va aplica producia T' , etc.

n general dac pentru un neterminal A exist produciile : A A1 |A2 | ... |Am | 1 | 2 | ... | n unde i nu ncepe cu A, 1 i n, se pot nlocui aceste producii cu : A 1A' | 2A' | ... | nA' A' 1A' | 2A' | ... | mA'| Aceast construcie elimin recursivitatea stng imediat. S considerm ns gramatica: A1 A2 a | b A2 A3 c | d A3 A1 e | f cu A1 simbolul de start al gramaticii. Se observ c este posibil urmtoarea derivare: A1 A2a => A3 ca => A1 eca deci gramatica este recursiv stnga. Se observ c dac am considerat o ordine a simbolilor, toate

produciile mai puin ultima, respect regula "un simbol neterminal este nlocuit de un ir care ncepe cu alt simbol neterminal cu un numr de ordine mai mare". Existena unei producii care nu respect condiia conduce la apariia recursivitii stnga.

Dac gramatica nu permite derivri de tipul A + A (fr cicluri) i nu conine - producii poate s fie transformat n vederea eliminrii recursivitii stnga utiliznd urmtorul algoritm, obinndu-se o gramatic echivalent fr recursivitate stnga.


Se aranjeaz neterminalele n ordinea A1, ..., An pentru i = 1 pn la n executa pentru j = 1 pn la i - 1 executa

nlocuiete fiecare producie de forma Ai Aj cu produciile Ai 1 | 2 | ... | k unde Aj 1|2| ... |k sunt toate produciile pentru Aj

elimin recursivitatea stnga ntre produciile Ai S considerm pasul i. Produciile Ak Al care au mai rmas (pentru care k < i), au l > k. n aceasta

iteraie prin variaia lui j se ajunge ca pentru orice producie de forma Ai Am , m i. Dac se elimin recursivitatea direct rmne m > i. S considerm de exemplu din nou gramatica :

A1 A2a | b, A2 A2c | A1d | e Considerm pentru neterminale ordinea : A1, A2. Pentru A1 (i = 1) nu exist recursivitate stnga

direct deci nu se face nici o modificare. Pentru i = 2, producia A2 A1d se inlocuiete cu A2 A2ad | bd. Rezult deci c A2 A2c | A2ad | bd | e.

Eliminnd recursivitatea stnga se obine : A1 A2a | b, A2 bdA2' | eA2', A2' cA2' | adA2' |

2.1.3.4 Factorizare stnga Acest tip de transformare este util pentru producerea unei gramatici potrivite pentru analiza sintactic

descendent de tip determinist. Ideea este c dac nu este clar care dintre produciile alternative poate s fie aplicat pentru un neterminal se va amna luarea unei decizii pn cnd s-a parcurs suficient din irul de intrare pentru a se putea lua o decizie. S considerm de exemplu produciile :

S A b S | A A B c A | B B a | dSd S presupunem c ncercm s construim irul derivrilor pentru a b a c a pornind de la simbolul de

start al gramaticii. Din recunoaterea simbolului a la nceputul irului nu se poate nc trage concluzia care dintre cele doua producii corespunztoare neterminalului S trebuie s fie luata n considerare (abia la ntlnirea caracterului b pe irul de intrare se poate face o alegere corect). n general pentru producia A 1 | 2 dac se recunoate la intrare un ir nevid derivat din nu se poate tii dac trebuie aleas prima sau a doua producie. Corespunztor este util transformarea: A A', A' 1 | 2.

Algoritmul de factorizare funcioneaz n modul urmtor. Pentru fiecare neterminal A se caut cel mai lung prefix comun pentru dou sau mai multe dintre produciile corespunztoare neterminalului A. Dac atunci se nlocuiesc produciile de forma A 1 | 2 | ... | n | (unde reprezint alternativele care nu ncep cu ) cu :

A A' | A' 1 | 2 | ... | n


A' este un nou neterminal. Se aplic n mod repetat aceast transformare pn cnd nu mai exist dou

alternative producii cu un prefix comun pentru acelai simbol neterminal. Relund exemplul considerat se obine : S AX X bS | A BY Y cA | B a | dSd Deci n analiza irului a b a la ntlnirea simbolului b pentru neterminalul Y se va utiliza producia Y

, n acest mod rezult irul de derivri : S AX BYX aYX ...

2.1.3.5 Eliminarea simbolilor neterminali neutilizai Un simbol neterminal neutilizat este un simbol care: nu poate s apar ntr-o form propoziional, adic ntr-un ir derivat din simbolul de start al

gramaticii (simbol inaccesibil) din care nu poate deriva un ir format numai din simboli terminali (simbol nefinalizabil) care apare n formele propoziionale numai datorit sau mpreun cu simboli neterminali ce

satisfac una dintre condiiile anterioare. Pornind de la o gramatic G = (N, T, P, S) se poate obine o gramatic fr simboli nefinalizai i care

satisface urmtoarele condiii: (i) L(G) = L(G') (i) A N, A + w, w T*. utiliznd urmtorul algoritm : N0 = i = 0 repeta

i = i + 1 Ni = { A | A P si (Ni-1 T)* } Ni-1

pn Ni = Ni-1 N' = Ni P' P conine numai produciile din P care au n partea stnga simboli din N' si n partea dreapta simboli din N' si T. Prin inducie asupra numrului de pai se poate demonstra corectitudinea algoritmului. S considerm

ca exemplu o gramatic avnd produciile : P = {S A, A a, B b, B a}, se observ c B este un simbol neterminal inaccesibil. Aparent condiia de inaccesibilitate pentru un neterminal const din ne apariia n partea dreapt a unei producii. Dac ns considerm o gramatic avnd produciile: {S A, A a, B cC, C bB} se observ c este necesar o alt condiie.

Pornind de la o gramatic G = (N, T, P, S) se poate construi o gramatic fr simboli inaccesibili G' = (N', T, P', S) care s satisfac condiiile:

(i) L(G) = L(G')


(i) A N', w (N T)*, S w i A apare n w

utiliznd urmtorul algoritm. N0 = {S} i = 0 repeta

i = i + 1; Ni = {A | A apare n partea dreapta a unei producii pentru un neterminal din Ni-1} Ni-1

pn Ni = Ni-1 N' = Ni P' conine numai producii care corespund neterminalelor din N' si care conin n partea dreapta simboli neterminali numai din N' Prin inducie asupra numrului de pai se poate determina corectitudinea algoritmului. Utiliznd

algoritmii pentru eliminarea simbolilor nefinalizai i cel pentru eliminarea simbolilor inaccesibili se obine o gramatic care nu conine simboli neutilizai. Ordinea n care se aplic aceti algoritmi nu este indiferent. S considerm de exemplu gramatica cu produciile:

S a | A, A AB, B b. Dac se aplic nti algoritmul pentru eliminarea simbolilor nefinalizai, rmn produciile S

a i B b. Prin eliminarea simbolilor inaccesibili rmne numai producia S a. Dac ns se aplic nti algoritmul pentru eliminarea simbolilor inaccesibili i apoi cel pentru eliminarea simbolilor nefinalizai vor rmne pn la sfrit produciile S a i B b, adic nu se obine o gramatic fr simboli neutilizai. Rezultatul obinut nu este ntmpltor n sensul c nu se poate gsii un exemplu pentru care ordinea corect de aplicare a celor doi algoritmi s fie invers. Ideea este c prin eliminarea unui simbol neterminal neaccesibil nu pot s apar simboli neterminali nefinalizai, n timp ce prin eliminarea unui simbol neterminal nefinalizat pot s apar simboli neterminali inaccesibili deoarece anumii simboli neterminali puteau s fie accesibili numai prin intermediul simbolului neterminal respectiv.

2.1.3.6 Substituia de nceputuri(corner substitution) Anumite metode de analiz sintactic impun ca partea dreapt a fiecrei producii care nu este irul

vid s nceap cu un terminal. S considerm de exemplu gramatica avnd produciile:

lista a(numr) lista | *elem lista | a elem a(numr) | *elem n acest caz dac pe irul de intrare se gsete terminalul a nu este clar care dintre produciile pentru

neterminalul lista trebuie s fie utilizat. Dac factorizm produciile neterminalului lista: lista aX | *elem lista X (numr) lista | elem a(numr) | *elem


Se observ ca n acest caz n funcie de simbolul terminal curent se poate decide n mod determinist care este producia urmtoare ce trebuie s fie aplicat pentru derivare (construirea arborelui de derivare).

O gramatic independent de context pentru care este ndeplinit condiia ca partea dreapt a oricrei producii ncepe cu un terminal sau este irul vid se numete gramatic de tip Q. O form particular de gramatica de tip Q este forma normal Greibach. n acest caz nu exist --producii cu excepia cel mult a unei --producii corespunztoare simbolului de start al gramaticii. n cazul n care aceasta producie exist simbolul de start al gramaticii nu apare n partea dreapt a nici unei producii. n forma normal Greibach produciile sunt de forma Aa cu a T i N*. S presupunem c o gramatic are produciile:

P a1 1 | a2 2 | ... | an n | unde ai T, i j ai aj, 1 i, j n. O procedur care recunoate irurile derivate din P este de

forma: p(){

switch (caracter_urmtor){ case a1 : avans(); a1 /* tratare a1 */ case a2 : avans(); a2 ...

case an : avans(); an default: /* ? - producie */

} } Pe baza transformrilor anterioare se poate elabora un algoritm pentru construirea unei gramatici n

forma normal Greibach pentru o gramatic independent de context care nu este recursiv stnga. Se definete nti o relaie de ordine asupra neterminalelor unei gramatici. i anume A < B dac exist

o producie A B . Considernd aceast relaie se observ c se poate construi o relaie parial de ordine care poate s fie extinsa la o relaie liniar de ordine. Dac gramatica pentru care se construiete aceast relaie nu este recursiv dreapta atunci produciile celui "mai mare" neterminal ncep sigur cu simboli terminali. Rezult algoritmul:

Se construiete relaia de ordine asupra N astfel nct N = {A1, A2, ..., An} si A1 < A2 < ... < An.

pentru i = n - 1 pn la 1 pas = -1 executa fiecare producie de forma Ai Aj cu i < j se nlocuiete cu Ai 1 | ... | m unde Aj 1 | ...| m (se observa ca 1, ..., m ncep cu terminale)

pentru fiecare producie de forma p = A a X1 ... Xk execut

pentru i = 1 pn la k execut dac Xi T N = N {Xi'} P = P { Xi' Xi}

P = P \ {p} {A aX1'X2' ... Xk'}

Prin inducie asupra numrului de pai se poate demonstra c algoritmul realizeaz transformarea

dorit. De exemplu pentru gramatica expresiilor aritmetice n forma fr --producii:


T ' | T , ' +TE' | +T, T FT' | F, T' *FT' | *F F () | a Relaia de ordine liniar poate s fie ' < < T' < T < F. Se pornete de la F, pentru care toate

produciile ncep cu un terminal. Rezult modificarea produciilor pentru T: T () T' | a T' | () | a. Urmeaz T' care nu necesit transformri. Pentru se obine: ()T'' | a T' ' | ()' | aE' | ()T' | aT' | () | a De asemenea ' nu se modific. Rezult urmtoarea gramatic n forma normal Greibach: (EAT'' | a T' ' | (EAE' | aE' | (EAT' | aT' | (EA | a ' +TE' | +T T (EA T' | a T' | (EA | a. T' *FT' | *F F (EA | a A )

2.1.4 Construcii dependente de context Anumite construcii specifice limbajelor de programare nu pot s fie descrise prin limbaje

independente de context. S considerm cteva exemple : 1. Fie limbajul L1 = {wcw| w {0,1}*}. Acest limbaj realizeaz abstractizarea condiiei ca un

identificator s fie declarat nainte de a fi utilizat. L1 nu poate s fie generat de o gramatic independent de context. Din acest motiv condiia ca un identificator s fie definit nainte de a fi utilizat nu pot s fie verificat prin analiz sintactic, deci va fi verificat de ctre analiza semantic.

2. Fie limbajul L2 = {anbmcndm | n > 1, m > 1}. Acest limbaj realizeaz abstractizarea corespondenei ca numr ntre numrul de parametrii cu care au fost declarate procedurile i numrul de parametrii cu care se utilizeaz acestea. Nici acest limbaj nu pot fi descris de o gramatic independent de context. Pe de alt parte limbajul L2' = {anbn | n > 1}, poate s fie descris de gramatica : S a S b | a b. Deci i aici dup o prim recunoatere fcut n analiza sintactic, partea de dependen de context va fi rezolvat de ctre faza de analiz semantic.

Observaie n general interpretnd gramaticile ca algoritmi de generare de iruri crora le corespund ca

echivaleni algoritmi de recunoatere de iruri, se constat c pentru cazul limbajelor regulate este necesar ca pentru recunoatere s se fac o numrare pn la o valoare finit (care poate ns s fie orict de mare). Astfel c limbajul LR = {anbn | 0 n 20000000000000} este un limbaj regulat. Numrul de a-uri ntlnite poate s fie memorat n neterminalele. De altfel, LR este un limbaj finit i deci automat este regulat (produciile gramatici pot s reprezinte de fapt lista irurilor care formeaz limbajul). Limbajul


LR1 = {w {0,1}* | |w| mod 3 = 0} este infinit i regulat. Se observ c pentru recunoaterea irurilor este necesar s se numere cte dou elemente. n schimb limbajul LI = {anbn | 0 n} nu este regulat, algoritmul pe care s-ar baza recunoaterea irurilor nu are o limit. Tratarea unei astfel de situaii se face n mod natural utiliznd un contor infinit sau o stiv.

2.1.4.1 Exerciii

1. Fie gramatica: A BC | a. B CA | Ab, C AB | cC | b S se construiasc gramatica echivalenta nerecursiva stnga

2. S se elimine simbolii neutilizai pentru gramatica: S A | B, A aB | bS | b, B AB | BA, C AS|b 3. S se construiasc gramatica echivalenta fr -producii pentru gramatica: S ABC, A BB | , B CC | , C AA | b 4. S se construiasc un algoritm care verific dac pentru o gramatic dat G, L(G) este mulimea

vid. S se demonstreze c algoritmul este corect


2.1.5 Proprieti ale limbajelor independente de context Limbajele formale sunt mulimi - putem s aplicm asupra lor operaii caracteristice mulimilor :

reuniune, intersecie, diferen dar i operaii specifice cum este de exemplu concatenarea. Dac L1 i L2 sunt dou limbaje, concatenarea lor este un limbaj L = L1L2 astfel nct:

L = { w | w = xy, x L1, y L2} O alt operaie specific ce se poate aplica asupra unui limbaj formal L este "Kleen star". Notaia

utilizat pentru rezultat este L* i reprezint mulimea irurilor obinute prin concatenarea a zero sau mai multe iruri din L (concatenarea a zero iruri este irul vid, concatenarea unui singur ir este el nsui etc.). Se va utiliza i notaia L+ pentru LL*.

Dac aplicnd o operaie asupra oricror doua limbaje independente de context obinem un limbaj independent de context vom spune c mulimea limbajelor independente de context este nchis sub operaia respectiv. Se poate demonstra c mulimea limbajelor independente de context este nchis sub operaiile: reuniune, concatenare i Kleen star.

S demonstrm de exemplu nchiderea sub operaia de reuniune. Fie doua gramatici G1 = (N1, T1, P1, S1), G2 = (N2, T2, P2, S2). Putem ntotdeauna s presupunem c N1 N2 = eventual prin redenumirea simbolilor neterminali din una dintre gramatici). Gramatica corespunztoare limbajului reuniune a limbajelor generate de ctre cele doua gramatici se poate construi n modul urmtor:

G = (N, T, P, S), N = N1 N2 {S}, T = T1 T2, P = P1 P2 {S S1 | S2} Pentru a demonstra c limbajul L(G) = L(G1) L(G2) trebuie s demonstrm includerea mulimilor

n ambele sensuri. Dac w L(G) nseamn c a fost obinut printr-o derivare ca S S1 * w sau S S2 * w. Deci un ir derivat din S aparine limbajului L(G1) L(G2). Invers dac alegem un ir w L(G1) L(G2) el este obinut dintr-o derivare din S1 sau din S2, deci se poate construi o derivare pentru acest ir i n G. Construcii similare se pot face i pentru operaia de concatenare i pentru operaia Kleen star. De exemplu L(G1)* pentru o gramatica G1 = (N1, T1, P1, S1) poate s fie generat de ctre:

G = (N1, T1, P1 {S1 | S1 S1}, S1) Clasa limbajelor independente de context nu este nchis la operaiile de intersecie i complementare.

S considerm de exemplu limbajele L1 = {anbncm | n,m 0}, L2 = {ambncn | n,m 0}. Limbajul L = L1 L2 este "cunoscut" ca fiind un limbaj dependent de context. S presupunem acum

c pentru un limbaj independent de context generat de ctre gramatica G = (N, T, P, S), limbajul complementar, adic T* - L(G) este ntotdeauna independent de context. n acest caz, fie L un limbaj obinut prin intersecia a dou limbaje independente de context: L1 i L2. Se poate scrie:

L = L1 L2 = T* - ((T* - L1) (T* - L2)). Dac mulimea limbajelor independente de context este nchis la operaia de complementare atunci

(T* - L1) i (T* - L2) sunt limbaje independente de context i la fel este i reuniunea lor i la fel va fi i complementarea limbajului obinut prin reuniune. Adic ar rezulta c L1 L2 este un limbaj independent de context ceea ce deja tim c nu este adevrat.

Dup cum s-a constatat acelai limbaj poate s fie descris de mai multe gramatici, eventual de tipuri diferite. Este util gsirea unui criteriu prin care s se indice tipul restrictiv al gramaticilor care pot s descrie un limbaj dat, ntr-o manier mai precis dect observaia de la pagina 24. De exemplu s considerm limbajul:


{ an * n | n > 1 } Se pune problema dac exist o gramatica independent de context care s-l genereze. Urmtorul

rezultat ne d un criteriu cu ajutorul cruia putem s demonstrm c o gramatic nu este independent de context.

Lema de pompare Fie L un limbaj independent de context. Atunci, exist o constanta k care este

caracteristic limbajului astfel nct dac z L i |z| k, atunci z poate s fie scris sub forma z = uvwxy cu vx , |vwx| k , |w| 1 i pentru orice i, uviwxiy L.

S utilizm rezultatul anterior pentru a studia limbajul: L = { an * n | n > 1 } s presupunem c L este independent de context. nseamn c exist un numr k (asociat limbajului)

astfel nct dac n * n k atunci an x n = uvwxy astfel nct v i x nu sunt amndou iruri vide i |vwx| k. S presupunem ca n este chiar k ( k * k > k). Rezult ca uv2wx2yL. Deoarece |vwx| k rezult 1 |vx| < k deci lungimea irului iniial k x k < |uv2wx2y| < k x k + k. Dup k x k urmtorul ptrat perfect este (k + 1) x (k + 1) care este mai mare deci k x k + k, adic |uv2wx2y| nu poate s fie un ptrat perfect, deci L nu poate s fie generat de o gramatic independent de context.

2.1.5.1 Exerciii 1. S se arate c limbajul { anbncn | n > 1 } nu este independent de context 2. S se arate c limbajul { anbncj | n > 1, j < n } nu este independent de context

2.2 Mulimi regulate, expresii regulate. Fie T un alfabet finit. Se numete mulime regulat asupra alfabetului T mulimea construit recursiv

n modul urmtor:

1. este o mulime regulat asupra alfabetului T; 2. Dac a T atunci {a} este o mulime regulat asupra alfabetului T; 3. Dac P i Q sunt mulimi regulate atunci PQ, PQ, P* sunt mulimi regulate asupra alfabetului T. 4. Nimic altceva nu este o mulime regulat.

Se observ deci c o submulime a mulimii T* este o mulime regulat asupra alfabetului T dac i

numai dac este mulimea vida, este o mulime care conine un singur simbol din T sau poate s fie obinut din aceste dou tipuri de mulimi utiliznd operaiile de reuniune (P Q), concatenare (PQ) sau nchidere P*.

Descrierea mulimilor regulate se poate face cu ajutorul expresiilor regulate. O expresie regulat este la rndul ei definit recursiv n modul urmtor (prin analogie cu definiia mulimilor regulate) :


1. este o expresie regulata care descrie mulimea ; 2. a T este o expresie regulat care descrie mulimea {a}; 3. dac p,q sunt expresii regulate care descriu mulimile P i Q atunci :

a. (p + q) sau (p | q) este o expresie regulat care descrie mulimea P Q; b. (pq) este o expresie regulat care descrie mulimea PQ; c. (p)* este o expresie regulat care descrie mulimea P*.

4. nimic altceva nu este o expresie regulat. De exemplu expresia (0 | 1)* reprezint mulimea {0,1}*, expresia regulat : (00 | 11)*((01 | 10)(00 |

11)*(01 | 10)(00 | 11)*)* reprezint mulimea care conine toate irurile formate din 0 i 1 i care conin un numr par din fiecare simbol. n particular pp* este notat cu p+. ntre operatorii utilizai n descrierea mulimilor regulate exist o serie de relaii de preceden. Cea mai prioritar operaie este operaia de nchidere (notat cu *), urmeaz operaia de concatenare, cel mai puin prioritar este operaia + (|). De exemplu, expresia regulat (0 | (1(0)*)) poate s fie scrisa i sub forma 0 | 10*.

Expresiile regulate au o serie de proprieti. Fie , , , expresii regulate. Spunem ca = dac i numai dac i descriu aceleai mulimi regulate. Sunt adevrate urmtoarele proprieti :

1. | = | 2. | ( |) = ( | ) | 3. () = () 4. ( |) = | 5. ( | ) = | 6. ? = ? = 7. * = | * 8. (*)* = * 9. | = Utiliznd expresii regulate se pot construi i rezolva ecuaii avnd ca soluii expresii regulate. S

considerm de exemplu ecuaia: X = aX + b unde a,b i X sunt expresii regulate. Se poate verifica uor c X = a * b este o soluie a acestei ecuaii.

Dac a este o expresie regulat care poate s genereze irul vid atunci soluia prezentat anterior nu este unic. S nlocuim n ecuaie pe X cu expresia regulat:

a*(b + ) Se obine: a*(b + ) = a[a*(b + )] + b = = a+ b + a+ + b = = (a+ + )b + a+ = a*b + a* = a*(b + ) Se numete punct fix al unei ecuaii cea mai mic soluie a ecuaiei respective. Propoziie Dac G este o gramatic regulat atunci L(G) este o mulime regulata. Demonstraia acestei teoreme se face prin construcie. Nu vom face demonstraia dar vom considera

un exemplu de construcie. Fie gramatica G = ({A, B, C}, {0,1}, P,A) cu P = {A 1A | 0B, B 0B | 1C, C 0B| 1A| }. Se cere s se construiasc expresia regulat care genereaz acelai limbaj ca i G. Se pot scrie urmtoarele ecuaii:

A = 1A + 0B B = 0B + 1C


C = 0B + 1A + Din prima ecuaie se obine: A = 1*0B. Din a doua ecuaie se obine: B = 0*1C. nlocuind n A se

obine: A = 1*00*1C = 1*0+1C. nlocuind n a treia ecuaie se obine: C = 0+1C + 1+0+1C + C = ( + 1+)0+1C + = 1*0+1C C = (1*0+1)* Rezult: A = 1*0+1 (1*0+1)* A = (1*0+1)+ Mulimea regulat descrie irurile de 0 i 1 care se termin cu sub irul 01. Evident o expresie mai

simpl pentru descrierea aceluiai limbaj este: (0 | 1)*01 Se observ c se poate considera c limbajul se obine prin concatenarea a doua limbaje unul descris

de expresia (0 | 1)* i cellalt descris de expresia 01. Rezult urmtoarea gramatic: S AB A 0A | 1A | B 01 Se observ c gramatica obinut nu este regulat. S transformm aceast gramatic prin substituie

de nceputuri: S 0AB | 1AB | B A 0A | 1A | B 01 Se obine: S 0S | 1S |01 Utiliznd factorizarea: S 0X | 1S X S | 1 Din nou prin nlocuire de nceputuri se obine: X 0X | 1S |1 Aplicnd factorizarea: X 0X | 1Y Y S |


Rezult gramatica descris de produciile: S 0X | 1S X 0X | 1Y Y 0X | 1S | . Se observ c s-a ajuns la aceeai gramatic cu cea iniial ( desigur dac redenumim neterminalele). Expresiile regulate reprezint o metod alternativ generativ pentru definirea limbajelor regulate.

Limbajele definite de gramatici regulate sunt utilizate la nivelul analizei lexicale, n majoritatea limbajelor de programare modul de scriere al numelor i al identificatorilor pot s fie descrise de gramatici respectiv de expresii regulate. Construirea expresiilor regulate corespunztoare atomilor lexicali reprezint prima etapa n proiectarea unui analizor lexical.

2.3 Acceptoare Un acceptor este un dispozitiv format dintr-o band de intrare, o unitate de control i o memorie

auxiliar. +---------------

|a0|a1|...|an| +---------------

\ cap de citire \ +---------+

| unitate | | de | | control | +---------+

| +-----------+

| memorie | | auxiliara | +-----------+

Banda de intrare este formata din elemente n care se nscriu simbolii din irul de intrare. La un

moment dat capul de citire este fixat pe un simbol. Funcionarea dispozitivului este dat de aciunile acestuia. ntr-o aciune capul de citire se poate deplasa la stnga sau la dreapta sau poate s rmn nemicat. n cadrul unei aciuni unitatea de control are acces la informaia din memoria auxiliar pe care o poate modifica. Se observ ca acest model este foarte general. Utiliznd diferite restricii asupra benzii de intrare, organizrii i accesului la memoria auxiliar se obin diferite cazuri particulare de acceptoare.

O aciune a acceptorului este formata din : deplasarea capului de citire la stnga sau la dreapta sau meninerea capului de citire pe aceeai poziie

i / sau; memorarea unei informaii n memoria auxiliar i / sau; modificarea strii unitii de control.

Comportarea unui acceptor poate s fie descris n funcie de configuraiile acestuia. O configuraie

este format din urmtoarele informaii :

starea unitii de control; coninutul benzii de intrare i poziia capului de citire;


coninutul memoriei. Rezult c o aciune a acceptorului poate s fie precizat prin configuraia iniial (nainte de aciune)

i cea final (dup execuia aciunii). Dac pentru o configuraie dat sunt posibile mai multe aciuni atunci spunem c acceptorul este

nedeterminist altfel este determinist. Un acceptor are o configuraie iniial n care unitatea de control este ntr-o stare iniial, capul de

citire este fixat pe simbolul cel mai din stnga al irului de intrare iar memoria are un coninut iniial specific. Acceptorul are o configuraie final pentru care capul de citire este situat pe simbolul cel mai din dreapta de pe banda de intrare. Se spune c dispozitivul a acceptat un ir de intrare w dac pornind din configuraia iniial ajunge n configuraia finala. Eventual, noiunea de acceptare poate s fie condiionata i de ajungerea ntr-o anumit stare a unitii de control sau de un anumit coninut al memoriei auxiliare. Evident dac acceptorul este nedeterminist dintr-o configuraie iniial pot avea loc mai multe evoluii. Dac exist ntre acestea una pentru care se ajunge la o configuraie final atunci se spune c dispozitivul a acceptat irul de intrare.

Limbajul acceptat de ctre un acceptor este format din mulimea irurilor acceptate de ctre acesta. Pentru fiecare tip de gramatica din ierarhia Chomsky exist o clasa de acceptoare care definesc

aceeai clas de limbaje. Dintre acestea cele utilizate pentru implementarea compilatoarelor sunt automatele finite care sunt acceptoare pentru limbaje regulate i automatele cu stiv (push-down), care sunt acceptoare pentru limbajele independente de context. Automatele finite sunt acceptoare fr memorie auxiliar iar automatele cu stiv sunt acceptoare pentru care accesul la memoria auxiliar se face conform unui mecanism de tip stiv.

2.3.1 Automate finite Un automat finit este un obiect matematic AF = (Q, T, m, s0, F) unde :

Q este mulimea finit a strilor; T este o mulime finit numit alfabet de intrare; m : Q x (T {}) P(Q) este funcia parial a strii urmtoare; s0 Q este o stare numit stare de start; F Q este o mulime de stri numit mulimea strilor finale (de acceptare).

Dac pentru q Q, a T m(q,a) este definit, atunci m(q,a) se numete tranziie, dac a = atunci

m(q,a) se numete -tranziie. Se observ ca pentru o combinaie stare(q Q), intrare(a T) pot s corespund mai multe stri urmtoare, deci aa cum a fost definit, automatul este nedeterminist (AFN).

Pentru reprezentarea unui automat finit se pot utiliza dou moduri de reprezentare, printr-o tabela de tranziie sau printr-un graf. S considerm de exemplu automatul care accepta limbajul definit de expresia (a | b)* abb. Poate s fie descris sub forma urmtoarei tabele :

simbol de intrare

stare a b 0 {0, 1} {0} 1 - {2} 2 - {3} 3 - +

Se observ c n fiecare intrare este specificat mulimea strilor urmtoare n care se trece pentru

starea i simbolul corespunztor intrrii respective. Acelai automat finit poate s fie descris de urmtorul graf de tranziie :


a ---

\ / +---+ +---+ +---+ +---+

start | | a | | b | | b |+-+| -------->| 0 |-->| 1 |-->| 2 |-->||3|| | | | | | | |+-+| +---+ +---+ +---+ +---+

/ \ ---

b Se observ c pentru fiecare stare exist cte un nod, ntre dou noduri exist un arc etichetat cu un

simbol de intrare dac i numai dac se poate trece din starea reprezentat de primul nod n starea reprezentat de al doilea nod la aplicarea la intrare a simbolului cu care este etichetat arcul. De remarcat modul n care a fost specificat starea final.

Se spune c un automat finit accept un ir de intrare dac exist o cale n graful de tranziie ntre nodul care reprezint starea de start i un nod care reprezint o stare final, astfel nct irul simbolilor care eticheteaz arcele care formeaz aceast cale este irul de intrare. De exemplu irul aabb este acceptat de automatul descris anterior, care va executa urmtoarele micri:

a a b b 0 0 1 2 3 Se observa c pentru acelai ir de intrare exist i alte secvene de intrri care ns nu duc ntr-o stare

de acceptare: a a b b 0 0 0 0 0 Un caz particular al automatelor finite este dat de automatele finite deterministe (AFD). n cazul

automatelor finite deterministe definiia funciei strii urmtoare se modific:

m : S x T S. Se observ c sunt satisfcute urmtoarele restricii: 1. nu exist -tranziii; 2. pentru (q, a) Q x T este definit cel mult o tranziie. Se observ ca n acest caz, pentru un ir de intrare dat, n graful de tranziie exist cel mult o cale care

pornete din starea de start i duce ntr-o stare de acceptare.

2.3.1.1 Construcia unui automat finit nedeterminist care accept limbajul descris de o expresie regulat dat Algoritmul pe care l vom prezenta utilizeaz direct structurile din definiia expresiilor regulate. Se

pleac de la o expresie regulat r asupra unui alfabet T i se obine un automat finit nedeterminist (N) care accept limbajul L(r).

Pentru construirea automatului se identific n structura expresiei r structurile care n mod recursiv compun expresia i se construiesc automatele finite nedeterministe (AFN) elementare corespunztoare.


1. Pentru expresia , automatul care accept limbajul corespunztor este : +---+ +-----+

start | | |+---+| ------->| i |------>|| f || | | |+---+| +---+ +-----+

2. Pentru expresia a, automatul care accept limbajul corespunztor este :

+---+ +-----+

start | | a |+---+| -------->| i |------>|| f || | | |+---+| +---+ +-----+

3. Fie dou expresii regulate r,t pentru care s-au construit automatele finite nedeterministe

corespunztoare N(r) i N(t). a. pentru expresia regulat r|t limbajul corespunztor este acceptat de :


-------------------------

| +---+ +-----+ | | | | N(r) |+---+| | --------->| |-- >|| ||---- / | | | |+---+| | \ / | +---+ +-----+ | \ +---+ / | | \ +-----+ | |/ ------------------------- \|+---+| ->| i | || f || | |\ ------------------------- /|+---+| +---+ \ | | / +-----+ \ | +---+ +-----+ | / \ | | | N(t) |+---+| | / ---------->| |-- >|| ||---/ | | | |+---+| | | +---+ +-----+ | | | -------------------------

b. pentru expresia regulat rt limbajul corespunztor este acceptat de : ----------------------------

| | --------------+----------- | | +---+ | +---+ | +-----+ | | | | N(r) | | | | N(t)|+---+| | --------->| i |--- -+> | |---- >|| f ||---- | | | | | | | |+---+| | | +---+ | +---+ | +-----+ | | | | | --------------+----------- | | | ----------------------------

Se observ ca n acest caz starea final a automatului corespunztor expresiei r coincide cu starea iniial a automatului corespunztor expresiei t.

c. pentru expresia regulata r* limbajul corespunztor este acceptat de : +-| i |----------> | |--- ---> | |-------->|| f || | | | | | | | | |+---+| +---+ | +---+ +---+ | +-----+ | | | /\ | -------------------------- | | | +---------------------------------------------+

d. pentru expresia (r) limbajul corespunztor este acceptat de automatul care accepta N(r).


Se observ c pentru fiecare AFN - elementar se adaug cel mult o stare iniial i o stare final. Corespunztor pentru o expresie regulat dat automatul va avea un numr de stri egal cu maxim dublul numrului de simboli de intrare care apar n expresie. Compunerea acestor automate elementare va produce evident un automat care recunoate limbajul generat de expresie. De exemplu pentru expresia regulata : (a|b)*abb se obine :

pentru fiecare a din expresie :

+---+ +-----+

| | a |+---+| -------->| i |------> || f || | | |+---+| +---+ +-----+

pentru fiecare b din expresie : +---+ +-----+

| | b |+---+| -------->| i |------> || f || | | |+---+| +---+ +-----+

pentru a | b : +---+ +-----+

| | a |+---+| ----------> | |------>|| ||---- / | | |+---+| \ / +---+ +-----+ \ +---+ / \ +-----+ | |/ \|+---+| ->| i | || f || | |\ /|+---+| +---+ \ / +-----+ \ +---+ +-----+ / \ | | b |+---+| / ---------->| |------>|| ||---/ | | |+---+| +---+ +-----+

n final se obine :


---------------+

/ | / +-+ +-+ | / | |a | | | / / >|2|->|3|\ | / / | | | | \ | +-+ +-+ / +-+ +-+ +-+ +-+ +-+ +-+ +--+ | | | |/ | | | |a | |b | |b |--| > |0|->|1| |6|->|7|->|8|->|9|->|10| | | | |\ /| | | | | | | | |--| +-+ +-+ \ +-+ +-+ / +-+ +-+ +-+ +-+ +--+ \ \ | |b | | / /\ \ \ > |4|->|5|/ / \ | | | | / \ +-+ +-+ / \ / --------------------

2.3.1.2 Conversia unui automat finit nedeterminist (AFN) ntr-un automat finit determinist(AFD) Din exemplele anterioare s-a observat c un acelai limbaj reprezentat de expresia regulat (a | b)*

abb poate s fie recunoscut de dou automate diferite - unul nedeterminist i unul determinist. Propoziie Pentru orice automat finit nedeterminist exist un automat finit determinist care accept

acelai limbaj. Avnd n vedere aceast echivalen ntre cele dou automate se pune problema, cum se poate

construi un automat determinist echivalent unui automat nedeterminist dat. n cele ce urmeaz vom considera c automatul finit nedeterminist a fost construit pornind de la o expresie regulat pe baza construciei prezentate n capitolul anterior. Algoritmul care construiete automatul determinist utilizeaz o metod de construire a submulimilor unei mulimi date. Diferena ntre automatele deterministe i cele nedeterministe este dat de cardinalitatea funciei m. Automatul determinist se va construi calculnd n mod recursiv strile acestuia, simulnd n paralel toate evoluiile posibile pe care le poate parcurge automatul nedeterminist. Starea iniial a automatului finit determinist va corespunde mulimii strilor din automatul nedeterminist n care se poate ajunge pornind din starea iniiala s0 i utiliznd numai -tranziii. Orice stare s' a automatului determinist corespunde unei submulimi Q' Q a automatului nedeterminist. Pentru aceasta stare i un simbol de intrare a T,

m(s',a) = {s Q | ( q Q')(s = m(q,a))}. Rezult deci c n funcionarea AFD care simuleaz de fapt funcionarea AFN se urmresc simultan

toate "cile" pe care poate evolua automatul finit nedeterminist. Algoritmul care construiete automatul finit determinist echivalent cu un automat nedeterminist dat utilizeaz dou funcii : -nchidere i mutare. Funcia -nchidere : P(Q) P(Q) determin pentru fiecare mulime Q' Q setul strilor n care se poate ajunge datorit -tranziiilor. Considernd o stare q a automatului finit determinist (AFD), aceasta reprezint de fapt o submulime Q' Q a automatului nedeterminist. Notm cu

-nchidere(Q) = -nchidere({s})

sQ


unde dac s S este o stare care nu are -tranziii atunci: -nchidere({s}) = {s} altfel -nchidere({s}) = -nchidere({s'}) {s} s' m(s,) Construcia funciei -nchidere pentru o mulime Q' se poate face utiliznd urmtorul algoritm : A = Q', B = ct timp A \ B execut fie t A \ B B = B {t} pentru fiecare u Q astfel nct m(t,) = u executa A = A {u} -nchidere(Q') = A Funcia mutare : P(Q) x T P(Q) este utilizat pentru construcia strii urmtoare a automatului

determinist. Astfel pentru o stare q a automatului determinist, cruia i corespunde o mulime Q' Q, i o intrare a T,

mutare(Q,a) = m(s,a) sQ' Construcia automatului determinist se face prin construcia unei tabele de tranziii tranz_AFD[] i a

unei mulimi de stri stari_AFD. stari_AFD = {-inchidere({s0})} A = ct timp stari_AFD \ A execut

fie t stari_AFD \ A A = A {t} pentru fiecare a T execut

B = -inchidere(mutare(t,a)) stari_AFD = stari_AFD {B} tranz_AFD[t,a] = B

Fie automatul nedeterminist :


---------------+

/ | / +-+ +-+ | / | |a | | | / / >|2|->|3|\ | / / | | | | \ | +-+ +-+ / +-+ +-+ +-+ +-+ +-+ +-+ +--+ | | | |/ | | | |a | |b | |b |--| > |0|->|1| |6|->|7|->|8|->|9|->|10| | | | |\ /| | | | | | | | |--| +-+ +-+ \ +-+ +-+ / +-+ +-+ +-+ +-+ +--+ \ \ | |b | | / /\ \ > |4|->|5|/ / \ | | | | / \ +-+ +-+ / \ / --------------------

Se observ c -inchidere(0) = {0, 1, 2, 4, 7}, -inchidere(mutare({0,1,2,4,7}),a)) = -inchidere({3,8}) =

{1,2,3,4,6,7,8}. Dac q1 = {0,1,2,4,7}, q2 = {1,2,3,4,6,7,8} atunci tran_AFD(q1,a) = q2. Continund se obine urmtoarea tabel de tranziie :

stare | intrare | multime corespunzatoare AFN | a | b | -----------+----+----+--------------------------------------

q1 | q2 | q3 | {0,1,2,4,7} -inchidere({0}) -----------+----+----+--------------------------------------

q2 | q2 | q4 | {1,2,3,4,6,7,8} -inchidere({3,8}) -----------+----+----+--------------------------------------

q3 | q2 | q3 | {1,2,4,5,6,7} -inchidere({5}) -----------+----+----+--------------------------------------

q4 | q2 | q5 | {1,2,4,5,6,7,9} -inchidere({5,9}) -----------+----+----+--------------------------------------

q5 | q2 | q3 | {1,2,4,5,6,7,10} -inchidere({5,10}) ------------------------------------------------------------

Graful automatului finit determinist care a rezultat este:


b ---

\ / +---+

| | b b >| q3|| q1| a \/| | b | | b |+----+| | |---> | q2|------>| q4|----->|| q5 || +---+ | | | | |+----+| +---+ +---+ +------+

/\ || a | | -- |+-

/ \ / \ . # / \ / \ 6 . b / \ / \ 5 . b / \ / \ 4 * a | / \ 3 / \ a b

1 2 Vom ataa fiecrei frunze un cod unic, de exemplu acest cod poate s fie reprezentat de poziia

simbolului respectiv n expresia regulat. Fie C mulimea codurilor ataate fiecrei frunze i N mulimea nodurilor arborelui. Fie c funcia de

codificare i c-1 funcia invers (c : N C). Definim patru funcii: nullable : N {adevrat, fals} firstpos : N P(C) lastpos : N P(C) followpos : C P(C) Funcia nullable este o funcie logic care are valoarea adevrat dac i numai dac subarborele

corespunztor nodului respectiv reprezint o expresie regulat care poate s genereze irul vid. Astfel funcia nullable aplicat subarborelui:

| / \ a b are valoarea fals n schimb aplicat asupra subarborelui: * | a are valoarea adevrat. Funcia firstpos aplicat unui subarbore are ca valoare mulimea codurilor frunzelor corespunztoare

poziiilor de nceput pentru subirurile care pot s fie generate de ctre expresia regulat corespunztoare subarborelui respectiv. De exemplu pentru nodul rdcin al subarborelui:


x (a | b)* a . 1 2 3 / \ / \ * a firstpos(x) = {1,2,3} | / \ 3 lastpos(x) = {3} / \ a b 1 2 Funcia lastpos aplicat unui subarbore are ca valoare setul codurilor frunzelor corespunztoare

poziiei de sfrit pentru subirurile care pot s fie generate de ctre expresia regulat corespunztoare subarborelui respectiv.

Funcia followpos este definit asupra mulimii codurilor frunzelor. Dac i este un cod i i este asociat simbolului x, (i = c-1(x)) atunci followpos(i) este mulimea codurilor j (j = c-1(z)) care satisfac urmtoarea condiie: xy (etichetate cu i i respectiv j ) pot s apar ntr-un ir generat din rdcin.

Altfel spus dac se consider irurile obinute din cuvintele din L(r) (limbajul generat de expresia regulat) prin nlocuirea simbolilor din T cu codurile asociate frunzelor din graf care le genereaz, followpos(i) conine toate codurile care pot s apar imediat dup i n aceste iruri. De exemplu followpos(1) = {1,2,3}. Pentru a calcula funcia followpos trebuie s se calculeze funciile firstpos i lastpos care la rndul lor necesit calculul funciei nullable. Regulile pentru calculul funciilor nullable, firstpos i lastpos sunt urmtoarele :

forma nod n nullable(n) firstpos(n) lastpos(n)

n este o frunz cu eticheta

adevrat

n este o frunz cu eticheta avnd codul i

fals {i} {i}

n | / \ / \ c1 c2

nullable(c1) sau

nullable(c2)

firstpos(c1)

firstpos(c2)

lastpos(c1)

lastpos(c2)

n . / \ / \ c1 c2

nullable(c1) si

nullable(c2)

dac nullable(c1) firstpos(c1) firstpos(c2) altfel firstpos(c1)

dac nullable(c2) lastpos(c1) lastpos(c2) altfel lastpos(c2)

n * | c

adevrat firstpos(c) lastpos(c)

Pentru a calcula followpos(i) care indic ce coduri pot s urmeze dup[ codul i conform arborelui se utilizeaz dou reguli :

1. dac n este un nod corespunztor operatorului de concatenare cu subarborii c1 i c2 (respectiv stnga

dreapta) atunci dac i este un cod din lastpos(c1) toate codurile din firstpos(c2) sunt n mulimea followpos(i).


2. dac n este un nod corespunztor operatorului *, i i este un cod din lastpos(n) atunci toate codurile din firstpos(n) sunt n mulimea followpos(i). Pentru arborele anterior valorile funciilor firstpos i lastpos sunt reprezentate n stnga respectiv

dreapta fiecrui nod.

{1,2,3} .{6} / \ / \ / \ {1,2,3} .{5} {6}#{6} / \ 6 / \ / \ {1,2,3} .{4} {5}b{5} / \ 5 / \ / \ {1,2,3} .{3} {4}b{4} / \ 4 / \ / \ {1,2} *{1,2} {3}a{3} | 3 {1,2} | {1,2} / \ / \ / \ {1} a{1} {2}b{2} 1 2 Singurul nod pentru care funcia nullable are valoarea adevrat este nodul etichetat cu *. Pe baza

acestor valori s calculm followpos(1). n followpos(1) vor apare codurile din firstpos pentru nodul etichetat cu * i codurile din firstpos pentru subarborele dreapta corespunztor operatorului de concatenare (followpos(1) = followpos(2) = {1,2,3}. Rezult urmtoarele valori :

nod followpos

1 {1,2,3} 2 {1,2,3} 3 {4} 4 {5} 5 {6} 6 -

Pornind de la aceste valori se poate construi un graf n care fiecare nod reprezint un cod iar ntre

dou noduri corespunztoare codurilor i i j exist un arc dac j followpos(i).


---

\ / +---+

+- | | | | 1 |\ +---+ +---+ +---+ +-----+ | +-| | \| | | | | | |+---+| | | +---+ | 3 |- | 4 |- | 5 |- || 6 || | | +---+ | | | | | | |+---+| | | | | /+---+ +---+ +---+ +-----+ | +>| 2 |/ +----| | +---+

/\ --

Pe baza unui astfel de graf se poate obine un automat finit nedeterminist fr -tranziii, etichetnd arcele n modul urmtor. Dac ntre nodul i i nodul j exist un arc acesta va fi etichetat cu simbolul care are codul j. Fiecare stare a automatului corespunde unui nod din graf. Automatul are ca stri iniiale strile din firstpos pentru nodul rdcin. Strile finale sunt strile asociate cu simbolul #. Automatul care a rezultat, avnd mai multe stri iniiale nu se ncadreaz de fapt n definiia pe care am dat-o pentru un automat finit. Dac ns mai adugm o stare suplimentar care s reprezinte unica stare iniial din care pe baza unor -tranziii ajungem ntr-una dintre strile automatului obinut, se vede c ne ncadrm n definiia considerat

a ---

\ / +---+

+-> | | a | | 1 |\ +---+ +---+ +---+ +-----+ | +-| | \| | b | | b | | # |+---+| a |b | +---+ | 3 |-> | 4 |->| 5 |->|| 6 || | | +---+ | | | | | | |+---+| | | | | /+---+ +---+ +---+ +-----+ | +>| 2 |/ a +----| | +---+

/\ --

b Mai interesant ns este faptul c funcia followpos poate s fie utilizat pentru construirea unui

automat determinist utiliznd un algoritm similar celui pentru construirea submulimilor.


stari_AFD = { first_pos(radacina) } // multime de multimi de coduri A = ct timp stari_AFD \ A execut

fie t stari_AFD \ A // mulime de coduri A = A {t} pentru fiecare a T execut

X = { followpos(p) | c-1(p) = a} p t

daca X stari_AFD = stari_AFD {X} tranz_AFD(t,a) = X

n algoritm firstpos(rdcin) este valoarea funciei firstpos aplicat nodului rdcin. Se observ c firstpos(rdcina) corespunde cu -inchidere(s0) iar followpos(p) reprezint -

nchidere(mutare(...)). Aplicnd acest algoritm i rezultatele anterioare se obine automatul finit determinist reprezentat de

urmtorul graf : b b -- -------- | 2,| a | 2,| b | 2,| b ||1,2,|| | 3 |----->| 3,|---- | 3,|----||3,6 || +---+ | 4 | | 5 | |+----+| +---+ +---+ +------+

/\ || a | | -- |+-

2.3.1.4 Simularea unui automat finit determinist

Construim un algoritm care urmeaz s rspund la ntrebarea - dndu-se un automat finit determinist D i un ir, este irul acceptat de ctre automat ?

Algoritmul utilizeaz funciile mutare (care determin starea urmtoare pentru o stare i un simbol de intrare dat) i caracterul_urmtor (care obine caracterul urmtor din irul de intrare).

s = s0 c = caracterul_urmtor cat timp c eof executa s = mutare(s,c) c = caracterul_urmtor daca s F atunci rezultat "DA" altfel rezultat "NU" Dac aplicm acest algoritm pentru automatul : b --------------

b / \ --- / \ \ / V \ +---+ +---+ +---+ +---+

start | | a | | b | | b |+-+| ------> | 0 |>| 1 |> | 2 |> ||3|| | | | | | | |+-+| +---+ +---+ +---+ +---+

/\ | | -- | | | | a | +-----+ | | a | +---------------+

a

care accepta limbajul (a | b)* abb, pentru irul ababb, se observ c va parcurge secvena de stri

012123.


2.3.1.5 Simularea unui automat finit nedeterminist Prezentm n continuare un algoritm pentru simularea unui automat finit nedeterminist. Algoritmul

citete un ir de intrare i verific dac automatul l accepta sau nu. Se consider c automatul a fost construit direct pornind de la expresia regulat. n consecin automatul va satisface urmtoarele proprieti:

1. are cel mult de dou ori mai multe stri fa de numrul de simboli i operatori care apar n expresia

regulat; 2. are o singur stare de start i o singur stare de acceptare. Dintr-o stare de acceptare nu pleac nici o

tranziie; 3. din fiecare stare pleac fie o tranziie pentru un simbol din alfabetul de intrare T, fie o -tranziie sau

doua -tranziii. Se consider c exist un mecanism prin care se poate stabilii faptul c s-a ajuns la sfritul irului de

intrare (test de tip eof). Algoritmul de simulare se aseamn cu cel utilizat pentru construcia unui automat finit determinist echivalent cu automatul N, diferenele constau n faptul c pentru fiecare mulime de stri Q n care poate s ajung automatul pentru un prefix al irului x se consider pentru construirea mulimii Q' de stri urmtoare numai simbolul curent din irul x. n momentul n care s-a ajuns la sfritul irului (s-a ajuns la eof) dac n setul strilor curente este inclus i o stare de acceptare (final), atunci rspunsul este "DA" altfel rspunsul este "NU".

S = -inchidere({s0}) # -inchidere(S) = {s' Q | s S, s' m(s,)} S a = caracterul_urmtor ct timp a eof execut

S = -inchidere(mutare(S,a)) # mutare(S,a) = m(s',a) s' S

a = caracterul_urmtor

daca S F atunci rezultat "DA" altfel rezultat "NU"

Algoritmul poate s fie implementat eficient utiliznd dou liste i un vector indexat cu strile

automatului finit nedeterminist. ntr-o list se pstreaz mulimea strilor curente ale automatului, n cealalt mulimea strilor urmtoare. Utiliznd algoritmul de calcul al strilor urmtoar

Limbaje Formale Si Automate 1

Documents

Transcript of Limbaje Formale Si Automate 1