UNIVERSITATEA VALAHIA DIN TRGOVITE FACULTATEA DE INGINERIE ELECTRIC SPECIALIZAREA: AUTOMATIC AVANSAT, PRODUCTIC cI INFORMATIC INDUSTRIAL AUTOMATE FINITE NON-DETERMINISTE(AFND) COORDONATOR : MASTERAND : Introducere Unautomatfinit(AF)sauo"maincuunnumrfinitdestri"esteunmodelde comportamentcompusdinstri,tranziiiiaciuni.Ostarestocheazinformaiidespre trecut, adic reflect schimbrile intrrii de la iniializarea sistemului pn n momentul de fa. Otranziieindicoschimbaredestareiestedescrisdeocondiiecareestenevoiesfie ndeplinit pentru a declana tranziia. O aciune este o descriere a unei activiti ce urmeaz a fi executat la un anumitmoment i este de maimulte tipuri (de intrare, de ieire, de intrare date, de tranziie). Un automat finit poate fi prezentat printr-o diagram de stare, numit uneori ireea de tranziie. O astfel de diagram este un graf direcionat, n carenodurilesunt strile automatului iarcelesunttranziii.Nodurilesuntetichetateculiteraqurmatdeindici,iararcelepotfi etichetatecusimboluridintr-unalfabetdat,,numitalfabetdeintrare.Mulimeastrilorunui automat finit este notat cu Q. Un automat finit are o stare iniial unic, indicat printr-o sgeat neetichetat, i n stri finale (n 0). O stare final este reprezentat prin dou cercuri concentrice. Automatul finit poate fi determinist sau non-determinist. Din orice stare a unui automat finit determinist (AFD), A, pleac o unic tranziie pentru fiecare simbol din alfabet i A nu poate trece de la o stare la alta fr s citeasc un simbol. Prin renunarealaacesterestriciiseobineoclasmailargdeautomatefinite,numiteautomate finite non-deterministe (AFND). Automate finite non - deterministe (AFND) Funcia de tranziie a unui automat finit determinist este: : S S aceasta avnd proprietatea c |(s, a)| 1, ()(s, a) S . nceleceurmeazvomconsideraschimbareaacesteicondiiipentruapermitenon-determinismul n funcia de tranziie . Acest lucru nseamn c (s,a) poate s nu fie unic. 1.Interpretare SchimbareadelaSlaP(S),caicodomeniupentruare,nmodclar,implicaiifoarte mari asupra modului de definire a prelungirii funciei de tranziie i, implicit, asupra modului de definire a termenului limbaj acceptat de un automat finit non-determinist. naintensdeaconsideraacestenoiuni,vomdescrieointerpretarefizicamodului n care este privit non-determinismul n acest context. S considerm tranziia ( , 0 ) = { , }, pentru maina urmtoare: Vom privi aceast tranziie ca modelnd afirmaia: Dac se citete 0 cnd suntem n starea atunci sau starea sau starea pot aprea ca fiind starea urmtoare. Este important s ne amintim c: a)Exact una dintre aceste stri este aleas. b)Nu se poate prezice care dintre ele este aleas. Astfel, dac (s, a) = R S, aflat n starea s i citind a, urmtoarea stare a automatului va fi o stare (necunoscut) din R. Non-determinismul (n sensul utilizat aici) nu trebuie gndit ca un proces aleator.Chiardacmetodelealeatoaresauprobabilistedefinescuntipparticulardenon-determinism, conceptul de alegere non-determinist pe care dorim s-l utilizmexclude orice posibilitatedemodelareprinprocesestohastice(smenionm,totui,cexisticonceptulde automat probabilistic sau stohastic, intens studiat, ns n afara scopului pe care l avemnacest moment). Revenindlaexemplulsimplupecarel-amdatmainainte,stareainiial,,poate tranzita la strile i , n ambele cazuri tranziiile fiind etichetate cu 0. n mod analog, are tranziii etichetate cu 1 i la starea i la starea . 1.1.Definiie Se numete automat finit non-determinist (AFN) un 5uplu A=(S, , , , F) unde : y S este o mulime nevid finit, mulimea strilor automatului; y este o mulime nevid finit, alfabetul de intrare; y s S 0 este un element distins din S numit stare iniial; yF S este mulimea strilor finale; y: S P (S) este funcia de tranziie (non-determinist). Pentru exemplul dat anterior, funcia de tranziie, descris tabelar, este: 01 {, } {}{} {,} S ne reamintim c, atunci cnd am vorbit despre limbajul recunoscut de un automat finit determinist,amavutnevoiedeprelungireafuncieidetranziielacuvintepestealfabetulde intrare, pe care am notat-o cu aceeai liter, ns :S * S. ntr-unautomatdeterministcomplet,porninddinstareainiial,oricecuvntw*, poate fi gndit ca traversnd o secven (drum) unic de stri ale automatului. ntr-unautomatnon-determinist,aceastsecvenpoatesnumaifieunic:potexista mai multe iruri de stri care s corespund unui singur cuvnt w. 1.2.Exemplu Considerm automatul non-determinist avnd urmtorul graf de tranziie: Pentrucuvntulw=010pestealfabetuldeintrare{0,1},arboreledescrieurmtoarele calcule posibile: y5 drumuri posibile indexate cu w; y3 drumuri care accept cuvntul w (se termin ntr-o stare final q2); y2 drumuri care resping cuvntul w (ntruct se termin ntr-o stare ne-final q1); i atunci apare ntrebarea: Este 010 acceptat sau nu? Dinpunctdevedereinformal,faptulcw*esteacceptatdeautomatulfinit nondeterministAsepoatedescrieastfel:westeacceptatdeAdacexistmcarundrumn graful de tranziie al lui A care s fie etichetat cu w i sa se termine ntr-o stare final q F. 1.3.Definiia limbajului recunoscut de un AFNDFieA=(S, , , , F) un automat finitnon-determinist. Definim limbajul acceptat de A, notat prin L(A), este limbajul L( A ) = { w * | (, w) F }. nceleceurmeazvomncercasdemonstrmc,dinpunctdevedereallimbajului acceptat, nu se ctig nimic (n sensul c nu exist limbaje acceptate de un AFN care s nu fie acceptate de un AFD). 1.4.Teorem Pentruoriceautomatfinitnon-deterministA=(S,,, ,F),existunautomatfinit determinist A=(S, , , , F) astfel nct L(A) = L(A). S ilustrm ideea din spatele demonstraiei printr-un exemplu. Considerm graful de tranziie al AFN-ului descris n exemplul de mai sus. Putem grupa strile dup arcele care intr i ies din ele n modul urmtor: Obinem astfel un automat care este determinist i este echivalent cu cel non-determinist (adic accept acelai limbaj). S indicm cteva etape ale demonstraiei teoremei: Fie =(,, , , )unautomatnon-deterministcareacceptlimbajul L()*.Vomconstruiunautomatfinitdeterminist =(,, , , )astfelnct L() = L(). Ideea este de a asocia unei singure stri din Sd o anumit submulime de stri din Snd. Mai precis,dacR,ivompunencorespondenostare dacexistw*astfel nct (, w) = R. Odat ce am definit toate strile din n acest mod, definim funcia de tranziie : astfel: pentru orice stare avem corespunztor o submulime i . Atuncivompune (,a)= unde icorespundelui prinprocedeulindicat mai nainte. Singurullucrucarearmaitrebuidemonstratarfic()w*, (,w)= T= w . Demonstraia se obine uor, utiliznd inducia dup lungimea cuvntului w. 2. Expresii regulate n seciunile precedente, am definit limbaje care sunt recunoscute (acceptate) de automate finite(non-)deterministeiamconstatatcAFN-urileauaceeaiputeredeacceptarecua AFD-urilor. Acestelimbajesuntuordeimplementatnprogramepecalculator.Totui,nueste (ntotdeauna)convenabilslespecificmcasecvene(drumuri)ngrafuldetranziiealunui automatfinit.Deexemplu,cndvremsgsimdrumul(ruta)pecareafostacceptatuncuvnt dinlimbajsau atunci cnd declarmsimboluri pentru anumiiidentificatori, este prea complex definirea unui automat finit n acest scop. Atunci,estemaibinesalegemoexpresienformsecvenial,definitsuccintiuor deneles.Astfeldeinstrumentesenumescexpresiiregulateiaufostintrodusepentruprima datdeKleene*.npractic,expresiileregulatesuntfoartedesutilizatecainterfeeutilizator pentruaspecificalimbajeleregulate.nschimb,automatelefinitesefolosescmaiuorca reprezentri interne pe calculator pentru stocarea limbajelor regulate. 2.1.Teorem OexpresieregulatepesteunalfabetilimbajulLgeneratdeaceastasedefinesc inductiv prin: (1)e = este o expresie regulat care genereaz L = . (2)e = este o expresie regulat care genereaz L = {}. (3)e = a, cu a , este o expresie regulat care genereaz L = {a}. Fie i expresiiregulate,iar i.,respectiv,limbajelegeneratedeacestea. Atunci: (4) e = ( + ) este o expresie regulat care genereaz L = + . (5) e = () este o expresie regulat care genereaz L = .. (6) e = este o expresie regulat care genereaz L = (L())*. Presupunem c operaia * are ntietate fa de i +, iarare ntietate fa de +. Perechiledeparantezesepotomiteatuncicndnucreazconfuzie.Deasemenea, omitem, de obicei, simboluln expresiile regulate. Exemple: 1. Fie = {a,b,c} i L* mulimea cuvintelor care conin abcc ca subcuvnt. Atunci L poate fi generat de expresia regulat (a+ b+ c)*abcc(a+ b+ c)*. 2.FieL{0,1}*mulimeatuturorcuvintelorcarenuconindousimboluri1 consecutive. Atunci L este generat de (10 + 0)*(1 + ). Spunemcdouexpresiiregulatesuntechivalente(notm =)pestedac genereaz acelai limbaj. Dinmoduldedefinireallimbajelorgeneratedeexpresiileregulate,esteevidentc familialimbajelorgeneratedeexpresiileregulatecoincidecufamiliaReg()alimbajelor regulatepestealfabetul(veziiCap.I,3).S.C.Kleeneademonstratnlucrareasacaceast familieesteegalcufamilialimbajeloracceptatedeAFD,adicexpresiileregulatesunt echivalentecuautomatelefinite,nceeaceprivetelimbajele.Existnumeroialgoritmide transformare a expresiilor regulate n automate finite i invers. Exist treimetodemajoredetransformareauneiexpresiiregulatentr-unautomatfinit. PrimadintreeleafostelaboratdeThompsoniconstntransformareauneiexpresiiregulate ntr-unAFNcutranziiivide(tranziiietichetatecu,numiteitranziiispontane,adic automatul poate trece dintr-o stare n alta (aparent) fr a introduce un simbol de intrare); metoda estesimpliintuitiv,darpoategeneramulte-tranziiiiarautomatulrezultatpoatedeveni mult prea complex. n acest caz transformarea lui ntr-un AFD poate lua mult timp. AdouametodafostcreatdeBerryiSethiitransformoexpresieregulatntr-un AFNfr-tranziii;algoritmulsebazeazpeteorialuiBrzozowskiasupraderivariloripe algoritmul de marcare al lui McNaughton i Yamada. Aceast a doua metod a fost mbuntit apoideBrggemannKlein.Atreiametodesteaceeadetransformareaexpresieiregulate direct ntr-un AFD echivalent ; algoritmul const n: (1) transformarea unei expresii regulate ntr-un AFN cu metodele de mai sus i (2) transformarea AFN n AFD. ncontinuare,vomdaodescrieresuccintamoduluidetransformareauneiexpresii regulate ntr-un AFN, urmnd-o pe aceea dat de A.Brggemann-Klein i D.Wood. Fie e o expresie regulat peste . Inductiv, definim un AFN Me dup cum urmeaz: (0)= ({s},,,s,), unde (s,a) = , pentru toi a . (1) M = ({s},,,s,{s}), unde (s,a) = , pentru toi a . (2) Pentru a, Ma =({s,f},,,s,{f}), unde (s,a) = {f} este singura tranziie. (3) Presupunem c =(, , , , ),=(, , , , ) i = . = (S, , , , F), unde S= ( s), i vor reprezenta aceeai stare; F= uac s F s altfel

Pentru s S i a , (s,a)= s s s

y=(S, , , , F). unde s yse face o copie a lui s, iar strile din vor fi intrri pentru automatul nou format; F= s F F suac s F

Pentru s S i a , (s,a)= s s s s

y =(S, , , , F), unde , F= F s, Pentru s S i a , (s,a)= s s s

AcesteAFN-urisenumescautomateleluiGlushkov,dupcelcarele-adefinitiniial.O proprietate mai deosebit a acestora este c nu exist tranziii care s se ntoarc la starea iniial. Observaie: O expresie regulat e se numete determinist dac Me este un AFD. Teorem: Dac e este o expresie regulat peste , atunci L(e) = L().