Clin Aurel Munteanu Simona Iuliana Caramihai Mihnea Alexandru Moisescu Ioan tefan Sacal Sisteme Dinamice cu Evenimente Discrete 2 CUPRINS Conceptul de Sistem cu Evenimente Discrete ............................................. 5 Breviar..................................................................................................... 5 Problem rezolvat.................................................................................. 7 Probleme propuse.................................................................................. 14 Limbaje Formale i Automate.................................................................... 16 Breviar................................................................................................... 16 Probleme rezolvate................................................................................ 39 Probleme propuse.................................................................................. 59 Reele Petri ................................................................................................. 74 Breviar................................................................................................... 74 Probleme rezolvate................................................................................ 85 Probleme propuse.................................................................................. 95 Bibliografie............................................................................................... 127 4 5 CAPITOLUL ICONCEPTUL DE SISTEM CU EVENIMENTE DISCRETE Breviar Unsistemcuevenimentediscrete(SED)esteunsistemdinamic caracterizatprintr-unspaiudiscretalstriloriprintraiectoriidestare continue pe poriuni. Modificrile de stare se numesc tranziii i survin ca urmare a apariiei evenimentelor, n mod asincron.Evenimenteleauduratnul.nafardecazulncareaparalte specificaii, se consider c la un moment dat are loc un singur eveniment (deoareceprobabilitateacadouaevenimenteindependentesaaibaloc simultan este aproape nul). Un eveniment poate fi identificat ca : aciune specific (ex: lansare operaie); modificare necontrolabil n cadrul unui proces (ex: defectarea unei resurse dintr-un motiv oarecare); rezultatul satisfacerii simultane a mai multor condiii.Evenimentelesunt,deregul,etichetate.Mulimeaevenimentelorlegate defuncionareaunuiprocesoarecareformeazunalfabet(mulimefinit desimboluri),astfelncteleipstreazsemnificaiadefenomen calitativ dependent de specificul aplicaiei.Din punct de vedere formal, un sistem cu evenimente discrete se mai poate defini i astfel: Definiie:UnSEDesteunsistemcareevolueazgenerndspontanevenimentei poate fi definit ca un quadruplu: ) , , , (0q Q G = unde: Q = mulimea strilor sistemului; = alfabetul evenimentelor pe care le poate genera sistemul;q0 = starea iniial;

= funcia de tranziie de stare, cu : Q Q. Sisteme cu evenimente discrete 6 Observaii 1.n funcie de dimensiunea lui Q, SED se mpart n sisteme cu numr finit de stri i respectiv sisteme cu numr infinit de stri; indiferent de dimensiune, Q este numrabil; 2.Funciadetranziienuestentotdeaunacompletdefinit,ceeace nseamncnuesteobligatoriucadinfiecarestareasistemuluis poatfigeneratetoateevenimenteledin;deregula,numarulde evenimente care poate fi generat din fiecare stare este determinat de caracteristicile fizice ale sistemului modelat; 3.Alfabetul are ntotdeauna un numr finit de evenimente. nconcluzie,modelareaunuiprocesrealcaSEDinclude,indiferentde formalismul utilizat, urmtoarele etape: 1.Definireavariabilelordestare,respectivaformatuluielementelorq Q; dac mulimea Q este finit, atunci se poate defini n ntregime prin enumerare; 2.Stabilirea strii iniiale q0 Q; 3.Definireatuturorevenimentelordin-caaciunicaremodific valoarea a cel puin o variabil de stare; 4.Definireafuncieidetranziie,ceeacerevinedefaptladescrierea explicit a modelului. nfunciedecomplexitateaprocesuluimodelat,etapele3i4potfi completate simultan.Dac se ia n considerare modul n care trateaz timpul, modelele SED pot fi mprite n urmtoarele categorii: modeleautonomesaulogiceutilizatepentruanalizacalitativa funcionriisistemelor;ncazulacestormodelenuesteluatn consideraredectordineancareaparevenimentele,iartimpul(ca momentprecisalaparitieiunuievenimentsaucaintervaluldintre dou evenimente succesive) nu apare n mod explicit;Sisteme cu evenimente discrete 7 modeletemporizateutilizateattpentruanalizacalitativcti, maiales,pentruanalizaperformanelorsistemelorintervalulde timp dintre apariiile a dou evenimente succesive este specificat n mod determinist; modelestochasticesauprobabilisticencaresuccesiunea evenimentelorestemodelataprinintermediulunordistribuiide probabilitate. Problem rezolvat 1)S se modeleze ca SED procesul format dintr-un server i o coad de ateptare.Capacitateaserveruluiesteunu(poatedeservinumaiun clientlaunmomentdat),iarcapacitateacoziiestepresupusafi nelimitat.Atuncicndunclientintrnsistem,elintrncoadade ateptare.Dendatceserverulesteliber,preiacteunclientdin coad, n ordinea sosirii acestora. Intrarea clienilor n sistem, precum i durata serviciului, sunt aleatoare. Se presupune c intervalul de timp dintre iesirea unui client de la server si intrarea unuia nou, n cazul n carecoadaestenevid,estezero(nesemnificativpentruproblema). Iniial, serverul este liber. Rezolvare: ProcesulpropusvafimodelatcaSEDautonom,ntructnuexistanicio indicaie temporal. DefinireaQ:nmodevident,sistemulvaaveaunnumrinfinitdestri, deoarece capacitatea cozii de ateptare nu este limitat. n acest caz, se va defini structura strilor sistemului prin specificarea variabilelor de stare, i anume: s starea serverului i l lungimea cozii de ateptare. ntructserverulnupoatefidectlibersauocupat,sepoateconsideraca s {0, 1}, astfel: s = 0 semnifica server liber, iar s = 1 server ocupat.Q = {(s, l)s {0, 1}, l } Sisteme cu evenimente discrete 8 Datoritfaptului c(din specificaiileproblemei) nuexist situaii n care serverul s fie liber i coada de ateptare s conin clieni, spaiul strilor poate fi rafinat sub forma: Q = {(0, 0)} U {(1, l)l } Definireastriiiniiale:q0=(0,0)serverlibericoadadeateptare vid. Definirea alfabetului de evenimente :Alfabetul de evenimente va conine dou elemente, i anume: e1 intrarea unui client n sistem;e2 ieirea unui client din sistem.Definirea funciei de tranziie: ) 0 , 1 ( ) ), 0 , 0 ((1= e ) 1 , 1 ( ) ), , 1 ((1+ = l e l respectiv intrarea unui client n sistemtrece serverul n starea de ocupat, dac acesta era liber sau incrementeaz lungimea cozii, dac la momentul intrrii serverul era ocupat. ) ), 0 , 0 ((2e = -(nusedefinete;fizicnuesteposibilca un client s ias dintr-un sistem fr clieni)) = =0 ) 0 , 0 (1 ) 1 , 1 () ), , 1 ((2l dacal daca le l respectiv ieirea unui client din sistemnu se definete (dac sistemul nu are nici un client) saudecrementeazlungimeacozii,dacaceastaeranevidsau elibereaz serverul, n caz contrar. Modelulautonompoatefimodificatnvedereaanalizeiperformanelor sistemuluincazulncareinformaiadespreprocesestecompletatcu informaii temporale. De exemplu, se presupun cunoscute duratele de timp dintredousosirisuccesiveideasemeneatimpuldeservireaferent fiecrui client.Sisteme cu evenimente discrete 9 ngeneral,performaneleunuisistemsuntevaluatefieprinmetode analitice, fie prin simulare.nceleceurmeaz,seurmreteconstruireaunuimodelnvederea analizei prin simulare. Simularea unui proces poate fi dependent de timp - sencheiedupexpirareauneiperioadeprecizatedetimp-saupoatefi dependentdeevenimentesencheienmomentulnregistrriiunui numr precizat de evenimente. Pentruprocesulndiscuiesealegesimulareadependentdeevenimente, considerndcsimulareasencheienmomentulncarecelde-aln-lea client sosit n coada de ateptare intr pe server.Mrimiledeinteres,alecrorvaloritrebuiesrezultenurmasimulrii procesului, sunt: durata medie de ateptare a clienilor n coad nDn dnii ==1) ( unde: Di reprezint durata de ateptare a fiecrui client n coad (este calculat ca diferena dintre momentul la care clientul i-1 a prsit sistemul i momentul la care clientul i a sosit n coad),n este numrul de clieni tratai de ctre server.Conformdefiniiei,duratatotaldeateptarepentrufiecare client,respectivduratamediedeateptarepotficalculate/ actualizatedoarnmomentulintrriiclientuluilaserviciu,ceeace echivaleaz cu momentul nregistrrii unui eveniment de tip e2.lungimea medie a cozii de ateptareValoarea estimat, rezultat din simulare este iip i n q ) ( 0= =, Sisteme cu evenimente discrete 10 unde ) (n TTpii=, ) () ( 0n TT in qii == cu urmtoarea semnificaie a parametrilor: Ti - suma intervalelor de timp n care coada are lungimea i T(n)duratatotaldesimulare(intervalulmsuratntre momentulnceperiisimulriiimomentullacareclientulna intrat pe server) pi- procentul din timpul total de simulare T(n) n care coada are lungimeai,Q(t)=i(undeQ(t)reprezintlungimeacoziila momentul t)Termenul =0 iiT ireprezintchiarariadesubgraficulluiQ(t) calculatntremomenteledenceputirespectivdesfritale simulrii, prin urmare) () () ( ) (0n Tdt t Qn qn T= gradul de utilizare a server-ului ) () ( n TTn ui= undeTisumaintervalelordetimpncareserver-ulesteocupat (B(t) =1 ) B(t)reprezintgraduldeocupareaserveruluilamomentulti este definit ca B(t) =, server ocupat la momentul t , server liber la momentul t 01Sisteme cu evenimente discrete 11 Caincazulprecedent,sumaintervalelordetimpncare severul este ocupat poate fi vzuta ca aria de sub curba B(t).Deci ) () () ( ) (0n Tdt t Bn un T= Spre deosebire de primul parametru, pentru a crui estimare se utilizeaz o medierenraportcunumruldeclienin,fiindomrimestatistic discret,ultimiidoiparametrisuntestimainraportcuduratasimulrii T(n), fiind mrimi statistice continue. nproceselecareimplicresursedetipserver(deexemplu,roboin sistemeledefabricaie,calculatoarenoperaiiledeprocesareadatelor) evaluarea acestor performane este util n scopul detectrii blocajelor sau a capacitii n exces (utilizare sczut). Pentru elaborarea unuimodel, care sapermita estimareacelor treimrimi deinteresspecificatemaisus,suntutileurmtoarelevariabile(de simulare): starea serverului; numrul de clieni din coad; o list care ine evidena evenimentelor de sosire n coad; momentul apariiei ultimului eveniment; o variabil ceas care se actualizeaz la apariia fiecrui eveniment; o list de evenimente care nregistreaz evenimentele de sosire i de plecare imediat urmtoare evenimentului n curs de tratare;nvedereaobineriivalorilormrimilordeperformanstabiliteanterior este necesar actualizarea urmtorilor parametri: numrul clientului aflat n serviciu; ntrzierea total a clienilor n coad; aria de sub curba Q(t) aria de sub curba B(t) Sisteme cu evenimente discrete 12 Se consider urmtorul studiu de caz, n care se specific intervalele dintre sosirileclienilor(Ai)idurateledeprocesarepeserverpentrufiecare client(Si).Seprecizeazcsimulareasencheienmomentulncare clientul cu numrul n = 6 ajunge la server.A1 = 0,4; A2 = 1,2; A3 = 0,5; A4 = 1,7; A5=0,2;A6=1,6; A7 = 0,2; A8 = 1,4;S1 = 2,0; S2 = 0,7; S3 = 0,2; S4 = 1,1; S5 = 3,7; S6 = 0,6;Rezultatele obinute n urma simulrii sunt: d(6) = 5.7/6 = 0.95 q(6) = 9.9/8.6 = 1.15 u(6) = 7.7/8.6 = 0.9 Valorile lui q si u pot fi verificate pe baza graficelor de mai jos. 0 123456789 e1 = 0,4 e2 = 1,6 e3 = 2,1 e4 = 2,4 e6 = 3,3 e5 = 3,1 e8 = 4,0 e7 = 3,8 e13 = 8,6 = T(6) e12 = 7,2 e11 = 5,8 e10 = 5,6 e9 = 4,9 1 2 3 Q(t) t Sosiri Plecri Figura I.1.Evoluia n timp a numrului de clieni din coada de ateptare. Sisteme cu evenimente discrete 13 0 123456789 e1 = 0,4 e2 = 1,6 e3 = 2,1 e4 = 2,4 e6 = 3,3 e5 = 3,1 e8 = 4,0 e7 = 3,8 e13 = 8,6 = T(6) e12 = 7,2 e11 = 5,8 e10 = 5,6 e9 = 4,9 1 B(t) t Sosiri Plecri Figura I.2.Evoluia n timp a ocuprii serverului. Sisteme cu evenimente discrete 14 Probleme propuse 2)FieunsistemdecalculcudouprocesoareP1iP2,carelucreazn paralel. Modul n caretaskurile sosesc spre procesare poate fidescris n raport cu momentul de timp discret al apariiei lor prin intermediul uneifunciibinarea(t),t,astfel:a(t)=1daclamomentult sosete un task i a(t)= 0 n caz contrar. Se presupune c nu pot sosi simultan dou sau mai multe task-uri. Presupunem c pentru un interval de timp t = 0,1,..,10 funcia a(t) are valorile {1,1,1,0,1,0,1,1,0,0,1}.Lasosireaunuitasksistemuldecalculaplicurmtoarearegulde alocareaacestuia:celedouprocesoarelucreazalternativ,primul fiindP1.SepresupunecdacuntaskestetrimislaPi,i=1,2iacel procesoresteocupat,atuncitaskulvaateptantr-ocoadde capacitateinfinit.DuratadeprocesareaunuitasklaprocesorulP1 alterneaz ntre 4 uniti de timp i o unitate de timp (ncepnd cu 4), iar durata de procesare pe P2 este de 2 uniti de timp. Fie y(t) numrul totaldeclienicareprsescsistemullamomentult,iarx1(t),x2(t) lungimile cozilor de ateptare la procesoarele P1 respectiv P2.a)desenaiodiagramadetimpt-0,1,...,10indicndsosirilei plecrile. Iniial x1(0) = x2(0) = y(0) =0; b)construiiuntabelcuvalorilex1(t),x2(t),iy(t)pentrutoit= 0,1,, 10; c)presupunemcselucreazntimpcontinuu.Sosirileaulocla momentele0,1;0,7;2,2;5,2;9,9.DurateledeprocesarepeP1 alterneaz ntre 4,2 i 1,1 iar pe P2 este fixat la 2 uniti de timp. FieunmodelcondusdeevenimentecusetuldeevenimenteE= {a,d1,d2},undeasemnificasosireaiardiplecareadepe procesorul Pi. Construii un tabel cu valorile x1(k), x2(k) , y(k), t(k) unde:x1(k),x2(k)suntlungimilecozilordeateptare;y(k)este numrul cumulativ de plecri dup evenimentul k. (k = 1,2,), iar t(k)momentuldetimplacareapareevenimentulk.Dacdou evenimenteaparsimultanpresupunemcoplecareapare ntotdeauna naintea unei sosiri. Comparai numrul de actualizri n acest model cu un model n timp cu eantioane la 0,1 uniti de timp.Sisteme cu evenimente discrete 15 3)Rezolvatiproblemaprecedentacuurmtoareleregulidealocarea taskurilor(dacdouevenimenteaparsimultanseconsiderc plecarea este prioritar fa de sosire):a)trimitetaskulprocesoruluiP1cttimplungimeacoziiestecel mult 2, altfel trimite ctre procesorul P2.b)trimitetaskulctreprocesorul cu coada cea mai scurt.n caz de egalitate trimite ctre procesorul P2. 4)Un proces de fabricaie simplu este compus din dou maini M1 i M2 i un robot care descarc piesele prelucrate de pe M1 i le transport pe M2. Nuexiststocurilaceledoumaini,decidacopieseste furnizatluiM1ntimpceaceastafuncioneazatuncipiesaeste rejectat.Dac robotul transport piesa lui M2 n timp ce aceasta este ocupatatuncielateaptacolopncndM2seelibereaz.Se consider c timpul de revenire a robotului de la maina M2 (dup ce a depuspiesa)npoziiainiialaestediferitdezero,deciM1poatefi foratocazionalspstrezepiesaprelucrat(isnuacceptealtele) pncndrobotuldevinedisponibil.Fiex1ix2strileluiM1 respectivM2,iarx3starearobotului.Presupunemctimpiide procesarepeM1iM2sunt:0,5peM1i1,5peM2,iartimpiide transport de la M1 la M2 de 0,2 sec iar de la M2 n poziia iniiala (M1) de0,1sec.PresupunemcpieselesosesclaM1dupurmtoarea schem: 0,10,71,11,62,5 sec a)identificai toate valorile posibile pentru x1 , x2 i x3; b)definii un set minimal de evenimente E pentru acest sistem; c)pentru intervalul [0,0, 0,3] construii un tabel cu valorile lui x1(k), x2(k), x3(k) i t(k) unde x1, x2, x3 sunt strile mainilor i robotului dupalk-leaevenimentiart(k)estemomentulapariieial evenimentului k. Dac dou evenimente apar simultan considerm c terminarea procesrii apare ntotdeauna naintea sosirii unei noi piese; d)identificai toate strile pentru care M1 este forat s atepte pn cnd braul robotului preia piesa finit (prelucrat) (de pe M1).16 CAPITOLUL II LIMBAJE FORMALE I AUTOMATE Breviar Definiii Un alfabet este o mulime finit de simboluri. Un cuvnt este o secven finit de simboluri ale aceluiai alfabet. Unlimbajesteomulimedecuvintecusimbolurialeaceluiai alfabet. Notaii: Lungimea unui cuvnt w:Cuvntul vid: (corespunde evenimentului nul sau, mai precis, unui eveniment neobservabil) Limbaj vid: EvoluiaoricruiSEDpoatefireprezentatcompletprintr-operechede limbaje (L, Lm) cu urmtoarele proprieti: L , Lm sunt definite pe alfabetul de intrareL reprezint toate evoluiile posibile ale SED si se numeste limbaj generat Lm reprezint toate evoluiile dorite ale SED si se numeste limbaj marcatLm L Operaii pe limbaje Fie L, L1, L2, limbaje definite peste alfabetul . Cele mai utilizate operatii pe limbaje sunt: Reuniunea L = L1 L2 ={ v| v L1 sau (i) v L2 } Concatenarea L = L1 L2 = {v | v = s t unde s L1 i t L2} Limbaje formale i automate 17 nchiderea iterativ (sau operatorul Kleene) L = L* L* = U=0 i Li , Lk+1 = Lk L L0 = {} Obs.Operatiadeinchidereiterativasepoateextindesilaunalfabet (consideratcaunlimbajcucuvintedelungime1):*estemulimea tuturor cuvintelor care pot fi formate cu simbolurile lui . nchiderea prefixatpr (L) =L= {s * | t L a.. sw = t} InterseciaL = L1 L2 = {v | v L1 i v L2} Proiecia lui L peste o submulime de evenimente ^ L^= {s^ | s L} cu , dac ^() , ^ = , altfel (s) , dac ^() s *, , s ^ = s^ , altfel Proprietate: LimbajulgeneratdectreunSEDestentotdeaunaegalcunchidereasa prefixat (L = pr(L)). Definiie Fie un alfabet; atunci o expresie regulat (ER) se definete astfel: esteoERcaremodeleazlimbajulceconinedoarevenimentul nul; este o ER care modeleaz limbajul vid; () a , a este o ER care modeleaz limbajul reprezentat de {a} dac a, b sunt ER, atunci (ab), (a + b), a*, b* sunt ER Limbaje formale i automate 18 Proprietate: Dac este ER, atunci : * = + *Definiie: Un automat finit determinist AFD se definete ca un quintuplu : G = (Q, , q0 , , Qm) unde: Q = mulimea (finit) a strilor = alfabetul de evenimente q0 = starea iniial = funcia de tranziie ; : Q Q () q Q si a, w *, (q, ) = q i (q, wa) = ( (q, w), a) = q Q Qm = mulimea strilor marcate Notaii:stare; starea iniial (unic !) stare marcat tranziia sub evenimentul a Observaii: 1.Dac Qm , atunci automatul se numete acceptor. 2.DouautomateG1siG2suntechivalentedaclimbajelelor generate si respectiv cele marcate, sunt egale. G1 echivalent cu G2 L(G1) = L(G2) si Lm(G1) = Lm(G2) Limbaje formale i automate 19 Definiie: Un automat finit nedeterminist AFN se definete ca un quintuplu G = (Q, , , q0, QF)undesinguradiferenfadeAFDestedatdemoduldedefinirea funciei de tranziie, respectiv : : Q 2Q cu 2Q mulimea tuturor submulimilor lui Q(q, ) = q i (q, a) = {p| pQ},ceeacenseamnc,dinstareaq,prinevenimentula,sepoateajunge ntr-o mulime de stri (evoluia nu este unic). Uncuvntdeintrarew*esteacceptatdeunAFNdacmcaruna dintre evoluiile (q0, w) Qm. PentruoriceAFNGsepoateconstruiunAFDechivalentG,numit observatorul lui G. G = (Q, , , q0, QF), Definiie: Un AFN cu tranziii (AFN-) se definete ca un quintuplu: G = (Q, { }, q0 , , Qm). Diferenafadeclaseledeautomateprezentateanteriorestedatde modul de definire al lui . PentruadefinifunciadetranziieaAFN-seintroducenoiuneade nchidere a unei stri q a automatului G (*G (q)), astfel:*G (q) = (q, *) = mulimea tuturor strilor n care se ajunge pornind din q sub o secven (orict de mare) de . Atunci funcia de tranziie a unui AFN-se definete astfel: : Q ( { })2Q ; (q, ) = *G(q) Limbaje formale i automate 20 Pentru un cuvnt de intrare s ( { })* i ,( )( ) ( )U Us q q q qG Gq s q s q, ' , ' ' '* *" )] ), , ( ( [ ) , ( ((

= = CaincazulAFN,pentruoriceAFN-sepoateconstruiunobservator determinist. Algoritmul de construcie a unui observator determinist Gobs pentru un automat nedeterminist general Gnd Considernd c automatul determinist este definit ca:Gobs = (Qobs, , obs, q0,obs, Qm,obs) iar automatul nedeterminist ca: Gnd = (Qnd, nd, nd, q0,nd, Qm,nd), n care = - AFN unavem daca}, {AFN un avem daca ,ndi folosind (pentru a putea rezolva cu algoritmul construcia observatorului att pentru AFN ct i pentru AFN-) urmtoarea funcie: UR: 2Qnd nd 2Qnd Cu definiia: = - AFN este G daca x), ( AFN este G dacax,UR(x)nd*Gnd algoritmul de construcie a observatorului pentru un automat nedeterminist este urmtorul: Pas 1q0,obs=UR(q0,nd)iseintroduceq0,obsnlistastrilorneexplorate (LSN). Pas 2Atta timp ct exist stri n LSN: Pas 2.1Extragere a unei stri q din LSN. Limbaje formale i automate 21 Pas 2.2IncludereastriiqnmulimeaQobs.Dacqndqobsa. qndQm,nd atunci se adaug qobs n Qm,obs. Pas 2.3Pentru fiecare eveniment end

Pas 2.3.1Evaluare a strii qobs n care evolueaz qobs la apariia evenimentului e: qobs =obs(qobs,e)=UR(nd(qobs,e))=UR(obs ndq q Und(qnd,e)) Pas 2.3.2Dac qobsQobs Introducere a lui qobs n LSN. Pas 2.4ntoarcere la Pas 2. Oriceexpresieregulata(ER)poatefireprezentataprintr-unAFN-,pe baza definiiei ER i utiliznd urmtoarele operaii: Fie r1 i r2 ER care pot fi exprimate prin AFN- , respectiv M1 = (Q1, 1, q1, 1, {f1}) M2 = (Q2, 2 , q2, 2, {f2}) Atunci:1. AFN- M corespunzator concatenarii r = r1 r2este M1 M2 f1 f2q1q2 M= (Q1 Q2 , 1 2 , , q1 , {f2}) (q, a) = 1 (q , a)dac q Q1 \ {f1} si a 1

(f1 , ) = {q2} (q , a) = 2 (q , a)dac qQ2 i a 2

Limbaje formale i automate 22 2. AFN- M corespunztor reuniunii r = r1 + r2este f0 M1 M2 f0 f1 f2 q0 q1 q2 M = (Q1 Q2 {q0 , f0 }, 1 2 , , q0 , {f0} ) (q0 , ) = {q1 , q2 } (q, a) = 1 (q1, a) dac q Q1 \{ f1 }i a 1 { } (q, a) = 2 (q, a) dac q Q2 \{f2 } i a 2 { } (f1, ) = (f2, ) = {f0} 3. AFN- M corespunzator operatorului Kleene r = r1* este: f0f1 q0q1 M=(Q1 {q0 , f0} , 1 {} , , q0 , {f0}) (q0 , ) = {q1 , f0} (q , a) = 1 (q, a) pentru q Q1 \ {f1} i a 1 (f1 , ) = {q1 , f0} Limbaje formale i automate 23 {a | (qi , a)=qj }daci j {a + | (qi , a) = qj {}}daci = j Teorem DacLesteunlimbajacceptatdeunautomatfinitdeterminist,atunciL poate fi scris ca expresie regulat. ExpresiaRegulat(ER)alimbajuluiacceptatdectreautomatesteo reuniune Um kQ qtoatenk 1R atuturortraiectoriilorcareconducdelastareainiialactreostare marcat. Ipoteza de lucru i notaii Sepresupunecautomatulavutnvederearennoduri,numerotatestrict cresctor de la 1 (starea iniial) la n.Aceasta ipotez nu are alt rol dect de a permite construcia algoritmic a expresiei regulate. Cuaceastaipoteza,nijRreprezinttoatetraiectoriiledelaqilaqjfrs treac printr-o stare cu un indice mai mare dect n. U1 kij1 kkj* 1 kkk1 kikkijR R ) R ( R R = =0ijR Operaii pe Automate Operaii unare: Componenta accesibil Fiind dat un automat G = (Q , , , q0, Qm), Limbaje formale i automate 24 sedefinetecomponentaaccesibilcafiindautomatulceconineacea parte din automatul iniial ce conine strile n care se poate ajunge pornind de la starea iniial (strile accesibile din starea iniial): Acc(G)=Gacc= (Qacc, , acc , q0, Qm acc), n care: Qacc = {qQ/ s* a.. (q0, s)=q}, Qmacc = Qacc Qm acc: Qacc acc Qacc, =altfelQ q si Q q daca qqacc accacc) , ( ) , () , ( Componenta coaccesibil Fiind dat un automat G =(Q , , , q0, Qm), sedefinetecomponentacoaccesibilcafiindautomatulceconineacea parte din automatul iniial ce conine strile de la care se poate ajunge la o stare marcat: CoAcc(G)=Gco= (Qco, , co , q0co , Qm), n care: Qco = {qQ/ s* a.. (q, s)Qm}, =altfelQ q daca qqcoco0 00co: Qco Qco, =altfelQ q si Q q daca qqco coco) , ( ) , () , ( Automatul trim Fiind dat un automat G = (Q , , , q0, Qm), sedefineteautomatultrimcafiindautomatulceconineaceapartedin automatul iniialce conine toatestrilela care se poate ajunge din starea Limbaje formale i automate 25 iniialicarepoateajungelaostaremarcat.Automatultrimseobine prinaplicareasuccesivacelordouoperaii:componentaaccesibili componenta coaccesibile (indiferent de ordine): Trim(G) = CoAcc(Acc(G))=Acc(CoAcc(G))=Gtrim Gtrim= (Qtrim, , trim , q0trim ,Qmtrim), n care: Qtrim = {qQ/ s* i w* a.. (q0,s)=q i (q, w)Qm}, =altfelQ q daca qqtrimtrim0 00 trim: Qtrim Qtrim, =altfelQ q si Q q daca qqtrim trimtrim) , ( ) , () , ( Complementul unui automat Fiind dat un automat G = (Q , , , q0, Qm), sedefinetecomplementulscafiindautomatulcaregenereaztoate cuvintele ce se pot genera utiliznd simboluri din i care marcheaz toate cuvintelecenusuntmarcatedeautomatuliniial.Obinerea complementului unui automat const n trei pai: Pentruaaflacuvintelemarcatedeautomatuliniialseconstruiete automatul trim corespunztor automatului iniial. Pentruageneratoatecuvinteleposibile(*)secompleteaz automatultrimcuostarenou(nemarcat)qdctrecareevolueaz orice stare a automatului care nu are o evoluie complet definit. qd vaevoluaneansipetoateevenimentelealfabetuluide evenimente. nfinal,pentruamarcatoatecuvintelecenusuntmarcatede automatul iniial se va inversa fiecare stare a automatului obinut la pasulanterior:oricestarenemarcataautomatuluidelapasulde maisusvadevenistaremarcatacomplementului,oricestare marcataautomatuluidelapasulanteriorvafistarenemarcat pentru complement. Limbaje formale i automate 26 Exemplu de aplicare a operaiilor unare pe automate Vom aplica cele patru tipuri de operaii unare pentru automatul din Figura II.1 Figura II.1.Automatul iniial a)Componenta accesibil (automatul ce conine strile n care se poate ajungedelastareainiial)nuconinestrileq4iq5deoarecenu satisfac cerina i va fi (Figura II.2): Figura II.2.Componenta accesibil. Limbaje formale i automate 27 b) Componentacoaccesibil(automatulceconinestriledincarese poate ajunge n stri marcate) a automatului iniial (Figura II.1) nu va conine strile q6 i q7, ele nesatisfcnd cerina. Figura II.3.Componenta coaccesibil. c)Automatul trim se va obine prin aplicarea celor dou operaii de mai sus.Aplicareanordineacomponentaccesibilurmatde componentcoaccesibilvaaveacaefecteliminareaprimadata strilor q4 i q5 (n urma aplicrii componentei accesibile) urmat de eliminareastrilorq6iq7(dincomponentacoaccesibil). Automatul trim va fi atunci: Figura II.4.Automatul trim. Limbaje formale i automate 28 d) Complementul.Pasul1constnobinereaautomatuluitrim, automat prezentat n Figura II.4. Pasul Figura II.5.Introducerea strii complementare qd. Figura II.6.Complementul automatului iniial. Limbaje formale i automate 29 Operaii binare: Compunerea sincron Definiie Fie dou Automate Finite (Deterministe) G1 = (Q1 , 1 , 1, q01, Qm1) G2 = (Q2 , 2 , 2, q02, Qm2) Se numete compunere sincron a automatelor G1 i G2 notat G1 || G2 un automat G care are strile G =(Q , , , q0, Qm) astfel: Q =Q1 Q2

= 1 2 q0 = (q01 , q02)Qm = Qm1 Qm2 Definirea funciei de tranziie: () q = (q1 , q2) Q i ( 1(q1, ) , 2(q2, ) )dac 1 2 i 1 (q1, )i 2(q2, ) (1(q1, ) , q2 ) dac 1 \2 i 1 (q1, ) ( q1, 2(q2, ) )dac 2 \1 i 2 (q2, ) Nu se definetepentru orice caz care nu corespunde celor definite mai sus (q,) = Observaie Dac1=2atunciLm(G1||G2)=Lm(G1)Lm(G2)iL(G1||G2)= L(G1)L (G2). Limbaje formale i automate 30 Compunerea total sincron Definiie Fie dou Automate Finite (Deterministe) G1 =( Q1 , 1 , 1 , q01 ,Qm1) G2 =( Q2 , 2 , 2 , q02 ,Qm2) Se numete compunere total sincron a automatelor G1 i G2 notat G1G2 un automat G care are strile G =(Q , , , q0, Qm) astfel: Q =Q1 Q2

= 1 2 q0 = (q01 , q02)Qm = Qm1 Qm2 Definirea funciei de tranziie : () q = (q1 , q2) Q i Lm (G1 || G2) = { s* / s 1 Lm (G1) i s 2 Lm (G2) } L (G1 || G2) = { s* / s 1 L (G1) i s 2 L (G2) } ( 1(q1, ) , 2(q2, ) )dac 1 2 i 1 (q1, )i 2(q2, ) Nu se definetepentru orice alt caz (q,) = Limbaje formale i automate 31 Automate cu ieiri Automatelestudiatepnacumpotficonsideratecamainidestarecu ieiribinare:fadeuncuvntdeintraredatwsepoatespecificanumai dac acesta este sau nu acceptat (respectiv daca (q0, w)Qm). n anumite situaii este de dorit s se diferenieze strile marcate, respectiv nemarcate, ntre ele. Pentru aceasta se folosesc aa-numitele maini de stare cu ieiri : Moore i Mealy. Definiie Maina Moore se definete ca un sextupluMo = (Q , , , , , q0)unde: Q = mulimea (finit) a strilor = alfabetul de evenimente (finit i el) = alfabetul ieirilor q0 = starea iniial = funcia de tranziie definit astfel: : Q Q = funcie de asociere a ieirilor: : Q Conformdefiniiei,oricemainMooredunrspuns(q0)asociatunei intrri nule (). Exemplu: S seproiecteze maina Moore carecalculeazrestul modulo 3pentru un irbinardeintrare(carearesemnificaiaunuinumrntregnformat binar) Evident, exista doar trei ieiri posibile: = {0, 1, 2}, ceea ce nseamn c numrul maxim de stri este tot trei. Limbaje formale i automate 32 Pentru intrarea nul (echivalent cu numrul 0), ieirea generat trebuie s fie 0. Rezult, prin definiie, c (q0) = 0. ncontinuare,sefoloseteurmtorulraionament:dacunirdeintrare binar w corespunde numrului natural n, atunci w0 i corespunde lui 2n i w1 lui (2n+1). Rezult urmtoarea structura pentru maina Moore dorit: Figura II.7.Maina Moore. Definiie O main Mealy este definit ca un sextupluMe = (Q, , , , , q0) unde : Q = mulimea (finit) a strilor = alfabetul de evenimente (finit i el) = alfabetul ieirilor q0 = starea iniial = funcia de tranziie definit astfel: : Q Q = funcie de asociere a ieirilor: : Q Conformdefiniiei,pentruointrarenul()omainMealygenereazo ieire nul (). Dinpunctuldevederealputeriidemodelare,mainileMooreiMealy suntechivalente;dinpunctuldevedereallungimiicuvntuluideieire, mainaMealyvadaunrspunsdelungimecu1maimicdectmaina Moore pentru aceeai lungime a cuvntului de intrare.Pentruunirdedatea1,a2,,anomainMealygenereazoieire (q0 , a1) , , (qn-1 , an) cu presupunerea c (qi-1 , ai)=qi Limbaje formale i automate 33 n acest mod, este evident c pentru iruri de intrare de aceeai lungime |w| rspunsulgeneratdeomainMoore(WMo)irspunsulgeneratdeo main Mealy(WMe) sunt n relaia: | WMo |=|WMe |+1 WMo =b WMe n care b = Mo (q0) Exemplu FielimbajulL=(a+b)*(aa+bb)peste={a,b}(cuvintelecaresetermin cu dou caractere identice). SseproiectezemainaMealycaregenereazoricecuvntcesepoate forma cu simbolurile lui i d la ieire "y" pentru cuvintele care aparin lui L i "n" pentru cuvintele care nu aparin lui L. Maina Mealy care ndeplinete aceste condiii are trei stri (Figura II.8): Figura II.8.Main Mealy. AFD echivalent cu maina Mealy din (Figura II.8) este prezentat n (Figura II.9): Figura II.9.AFD corespunztor mainii Mealy. Limbaje formale i automate 34 AFN pentru maina Mealy din (Figura II.8) ar putea fi (Figura II.10): Figura II.10. AFN corespunztor mainii Mealy. Echivalena ntre maina Moore i maina Mealy Transformarea unei maini Moore n main Mealy Teorem: Dac M1 este o main Moore definit prin M1 =(Q, , , , , q0)atunci () o main MealyM2 =(Q, , , , , q0)echivalent cu M1 unde (q, a) = ( (q, a)) MealyMoore Observaie: Echivalenaesteprivitnsensulcpentruacelaiirdeintrarese genereaz acelaiir de ieire. Oricum afirmaia trebuie privit n limitele toleranei formulei|WMo|=|WMe |+1 (adic irul generat de maina Mooreva fi cu 1 mai mare dect irul generat de maina Mealy).De asemenea se va lua n considerare c (q0) = b neglijabil. Observaie: Maina Mealy este mai compact. Limbaje formale i automate 35 Transformarea unei maini Mealy n main Moore Teorema: Dac M1 este o main Mealy definit prin M1 = (Q, , , , , q0) atunci () M2 o main Moore definit prin M2 = (Q , , , , , q0)echivalent cu M1. Construcie:q0=[q0 ,b],bales"arbitrar"(defaptsededucedin contextul problemei) ([q, b]) = [ (q, a), (q,a)]MooreMealy ([q,b]) = b (funcia care asociaz ieirile) Exemplu: Transformarea n main Moore a mainii Mealy din Figura II.8. ={y, n}; ={a,b}; Q={ q0 , q1 , q2 } Q= {[q0 , y], [q0 ,n], [q1 , y], [q1 , n], [q2 , y], [q2 , n]} Observaie: nmodnormalamputeaalegedreptstareiniialperechea[q0,y]sau [q0, n],dar[q0,y]argeneraieireaypentrucuvntulnul,ceeaceeste incorect.Deci,vomalegecastareiniialperechea[q0,n]ivomobine maina din figura Figura II.11 n care se observ c n starea [q0, y] nu se ajunge niciodat i astfel ea nu va aprea n automat.Limbaje formale i automate 36 Figura II.11. Maina Moore echivalent. Minimizarea automatelor: Fie x, y L. AtunciRL este o relaie de echivalen asociata limbajului L (sau x RL y)dac i numai dac pentru() z *,1.fie xz L i yz L2.fie xz L iyz L. Relaia RL mparte limbajul L n clase de echivalen. Numrul de clase de echivalen se numete index. Se poate demonstra c indexul unui limbaj regulat este finit. FieM=(Q,,,q0,Qm)unAFD.SedefineterelaiadeechivalenRM asociata automatului M astfel: pentru x , y *, x RM ydac i numai dac (q0, x) = (q0, y). n plus, dac x RM y,pentru () z *avemxz RMyz. (Ceea ce revine la (q0 , xz) = ((q0 , x), z) = ((q0 , y), z) = (q0 ,yz)) O relaie de echivalen de acest tip se numete invariant la dreapta (fa de operaia de concatenare). Limbaje formale i automate 37 Teorem (criteriul Myhill-Nerode): Urmtoareleafirmaiisunt echivalente: 1.Limbajul L * este acceptat de un automat finit; 2.Lestereuniuneaunorclasedeechivalendeterminatedeo relaie de echivalen invariant la dreapta cu index finit; 3.Fie relaia de echivalen definit pe limbajul L astfel: () x, y L , xRL y dac i numai dac () z * ,xz Lnumai n cazuln care i yz L . Ca o consecin a teoremei de mai sus, o stare p este echivalent cu o stare q a automatului M dac i numai dac pentru orice ir de intrare x,(p, x) este stare marcat numai atunci cnd(q, x) este o stare marcat. Algoritmul de minimizare a unui automat Start Pas 1:pentrufiecarepQmiqQ\Qmbifeazntabellocaia corespunztoare (strile marcate nu sunt echivalente din punct de vedere al obiectivului cu cele nemarcate); Pas 2:pentrufiecareperechedestridistincte(p,q)QmQmsau (p, q) (Q/Qm)(Q/Qm)Pas 2.1dac () a ,((p, a), (q, a)) este bifat n tabel: atuncibifeaz (p, q); bifeazsuccesivtoateperechiledinlistadeechivalenea perechii (p,q). altfelpentrutoi a introducere a perechii (p, q) n lista de echivalene a perechii((p,a), (q,a))nafaracazuluincare (p,a) = (q, a). Stop Limbaje formale i automate 38 Algoritmul de minimizare a automatelor a fost elaborat pe baza criteriului Myhill Nerode. Acest algoritm urmrete gsirea perechilor de stri care suntechivalente(auaceeaievoluie).Acestlucruserealizeazprin eliminareastrilorcarenusuntechivalente.Algoritmulverifictoate perechile distincte de stri. FieautomatulG=(Q,,,q0,Qm).Seconstruieteuntabelcares conin toate perechile de stri distincte. Din matricea care are pe linii i pe coloanetoatestrilesepstreazdoarelementeledesubdiagonala principal a matricei. nacestfel,toateperechile(p,q)rmasenemarcatereprezintdoucte dou stri echivalente. Limbaje formale i automate 39 Probleme rezolvate 5)SseproiectezeunAFDpestealfabetul={a,b}careaccept cuvintele care nu conin 3a consecutiv. Rezolvare.Sepoateobservadincerinaproblemeicceaceestedeintereslaacest automatestenumruldesimboluriaconsecutivencareseterminun cuvnt(prefix).nmomentulncareacestnumrdepetevaloarea2, cuvintelecarencepcurespectivulprefixnupotsatisfacecerina problemei.nconformitatecuaceastlogic,semnificaiastrilorautomatuluidin Figura II.12 este urmtoarea (funcie de semnificaia cuvintelor care duc n respectivele stri): q0 cuvinte care nu se termin n a i nu conin subirul aaa; q1 cuvinte care se termin ntr-un a i nu conin subirul aaa; q2 cuvinte care se termin n subirul aa i nu conin subirul aaa; q3 cuvinte care conin subirul aaa; Figura II.12. Automatul corespunztor prolemei 5). 6)Sseproiectezeautomatulfinitdeterministcarepealfabetul = {a, b}acceptirurilecunumrpardesimboluriaicarenu conin subirul bb. Limbaje formale i automate 40 Rezolvare. Exist dou posibiliti: a)sconsideram0cafiindnumrpardeapariiialeluia,cazn carestareainiialestemarcatdeoarecesatisfaceambele condiii. b)sconsidermcpentruunnumrpardeapariiialeluiaeste evoie de cel puin dou apariii ale acestui sibol, caz n care starea iniial nu va mai fi marcat.Pentru fiecare dintre aceste situaii vom avea cte un automat. Cazul a) Semnificaia strilor: q0cuvintececoninunnumrpardeainuseterminn b q1 cuvinte ce conin un numr impar de a i nu se termin n b. q2 cuvinte ceconin un numr impar de a i se termin doar ntr-un b; q3cuvintececoninunnumrpardeaisetermindoar ntr-un b q4 cuvinte ce conin subirul bb; Limbaje formale i automate 41 Cazul b) Semnificaia strilor: q0 irul vid q1cuvintececoninunnumrpardeainuseterminn b; q2cuvintececoninunnumrpardeainuseterminn b; q3 sirul b; q4 cuvinte ceconin un numr impar de a i se termin doar ntr-un b; q5cuvintececoninunnumrpardeaisetermindoar ntr-un b; q6 cuvinte ce conin subirul bb. 7)SseproiectezeAFDpestealfabetul={a,b}careacceptirurile a, bb i aba. Rezolvare. Automatul trebuie s accepte cele trei cuvinte din enun i doar pe acelea.Limbaje formale i automate 42 Figura II.13. Rezolvarea problemei 7). 8)Sseproiectezeautomatulfinitdeterministcarepealfabetul = {a, b} care accept cuvintele n care perechea aa este urmat de subirul bab. Rezolvare. Semnificaia strilor acestui automat este urmtoarea: 1: cuvinte ce se termin n b i nu conin subirul aa; 2: cuvinte ce se termin n a dar nu n aa; 3: cuvinte ce se termina n aa; 4: cuvinte ce se termin n b, nu n bab i conin aa; 5: cuvinte ce se termina n ba i conin aa; 6: cuvinte ce se termina n bab i contin aa (stare marcat). Limbaje formale i automate 43 9)SseproiectezeAFDcareacceptpestealfabetul={a,b,c} cuvinte cu numr par de a, par de b i impar de c. Rezolvare. Utiliznd urmtoarele notaii: P = numr par de a, b sau c I = numr impar de a, b sau c, starea unui automat se va scrie ca o pereche de trei elemente (X, Y, Z) n care: X se refer la numrul de a-uri din cuvnt; Y se refer la numrul de b-uri din cuvnt; Z se refer la numrul de c-uri din cuvnt; Considerndczeroestenumrpardeapariiialeunuisimbol,starea iniial a automatului va fi q0 = (P P P). Starea marcat va fi (P P I). Pentruomaiuoarnelegerealegturilordintrestrivomreprezenta funcia de tranziie sub form tabelar. 10)S se proiecteze AFD care pe alfabetul = {a, b, c} accept cuvintele ceconincelpuin2simboluria(nuneapratconsecutive)inu conin subirul bb. semnificatieq1 P P P I P P P I P P P Iq2 I P P P P P I I P I P Iq3 P I P I I P P P P P I Iq4 P P I I P I P I I P P Pq5 I I P P I P I P P I I Iq6 I P I P P I I I I I P Pq7 P I I I I I P P I P I Pq8 I I I P I I I P I I I PStarea Q a b cLimbaje formale i automate 44 Rezolvare. Semnificaia strilor 1 = irul vid; 2 = cuvantul b; 3 = cuvintele ce contin subirul bb; 4 = cuvintele ce contin un singur a i se termina n a; 5 = cuvintele ce conin un singur a i se termin n b. 6 = cuvintele ce contin cel putin 2 a i se termina n a; 7 = cuvintele ce conin cel puin 2 a i se termin n b; 11)S se proiecteze AFD care peste alfabetul = {a, b}accept cuvintele ce conin subirul aba i nu conin subirul bb: Rezolvare. Figura II.14. Solua problemei 11). Limbaje formale i automate 45 q0 - cuvntul vid q1 cuvintele ce se termina n a, nu conin aba sau bb q2 - cuvintele ce se termina n ab, nu contine aba sau bb q3 - cuvintele ce conin aba, nu conin bb ise termin n a q4 - cuvintele ce contine bb q5 - cuvintele ce conin aba, nu contine bb i se termin n b q6 - cuvntul b 12)SseconstruiascAFDpestealfabetul={1,2,3}careaccept cuvintele n care suma ultimelor dou simboluri este 4. Rezolvare. Construim automatul cu 7 stri dup cum urmeaz: starea iniial; 3 stri dup cum urmeaz: starea 1 pentru cuvintele care se termin n 1 i pentru care suma ultimelor 2 evenimente nu e 4; starea 2 pentru cuvintele care se termin n 2 i pentru care suma ultimelor 2 evenimente nu e 4; starea 3 pentru cuvintele care se termin n 3 i pentru care suma ultimelor 2 evenimente nu e 4; 3 stri marcate dup cum urmeaz: starea 1+3 pentru cuvintele care se termina n 13 starea 2+2 pentru cuvintele care se termina n 22 starea 3+1 pentru cuvintele care se termina n 31 Cu aceast semnificaie a strilor, soluia problemei este: Limbaje formale i automate 46 Figura II.15. Soluia problemei 12). 13)SseproiectezeAFDcarepealfabetul={1,2,3}accepttoate cuvintele care se termin n subirul 123.Rezolvare. Cu urmtoarea semnificaie a strilor: 0 starea iniial; cuvintele care nu se termin n 1, 12 sau 123 (prefixele cerinei problemei); 1 cuvintele care se termin n 1; 2 cuvintele care se termina n subirul 12; 3 cuvintele acceptate (care se termina cu subsirul 123), forma tabelar de reprezentare a automatului este: iar forma grafic este: 123 q0 q1q0q0 q1q1q2q0 q2q1q0q3 q3q1q0q0 Limbaje formale i automate 47 Figura II.16. Soluia problemei 13). 14)SseconstruiascAFDcareacceptsetultuturorirurilordin alfabetul = {0, 1} cu numr egal de 0 i 1 astfel nct fiecare prefix are cel mult nc un 0 n plus fata de numrul de 1 i nc cel mult un 1 n plus fa de numrul de zerouri.Rezolvare. Figura II.17. Soluia problemei 14). Semnificaia strilor: q0 numr egal de 0 i de 1 q1 numrul de 0 este cu 1 mai mare dect numarul de 1 q2 numrul de 1 este cu 1 mai mare dect numrul de 0 q3prefixularecelpuindousimboluri0nplusfade numruldesimboluri1saucelpuindousimboluri1nplus fa de numrul de simboluri 0 Limbaje formale i automate 48 15)Ce iruri accept automatul: Rezolvare. Automatulnumrapariiileevenimentuluiaifiindmarcateprimele2 stri,irurileacceptatesuntcelecareconinmaximun"a".Expresia regulat pentru aceste cuvinte este: ER: b*(a + )b* 16)S se construiasc AFD echivalent cu urmtorul AFN: Rezolvare. Stare AFDab x0 = {q1}x1 = {q2, q4}x2 = {q4} x1 = {q2,q4}x3 = {q2,q3}x3 = {q2,q3} x2 = {q4}---x4 = {q3} x3 = {q2,q3}x3 = {q2,q3}x3 = { q2,q3} x4 = {q3}x4 = {q3}x4 = {q3} Qm = {x3,x4} (deoarece conin starea marcat din AFN q3) Cu aceste notaii, observatorul (AFD) echivalent cu automatul din enunul problemei este: Limbaje formale i automate 49 17)Se d automatul G definit astfel : G = {{p, q, r, s,}, {0,1}, , p, {q,s}}, unde este definit prin tabelul de mai jos.Se cere AFD echivalent. 01 Pq,sq Qrq, r Rsp S-p Modul de interpretare a informaiilor furnizate de definirea automatului G = {{p, q, r, s,}, {0,1}, , p, {q,s}} este urmtorul: {p, q, r, s} spaiul strilor - Q {0, 1} alfabetul evenimentelor - p starea iniial q0 {q,s} mulimea strilor marcate - Qm Q 01 AFDAFN x0 ={p} {q, s} {q} x1 ={q, s} * {r} {p, q, r} x2 ={q} *{r} {q, r} x3 ={r} {s}{p}x4 ={p, q, r} * {q, r, s,} {p, q, r} x5 ={q, r} *{r, s} {p, q, r}x6 ={s} *-{p}x7 ={q, r, s} *{r, s} {p, q, r} x8 ={r, s} *{s} {p} Limbaje formale i automate 50 18)S se minimizeze automatul Rezolvare: 14 256 3123 012 Pas1 al algoritmului de minimizare: bifrile de la 1 la 3 din tabelul de mai sus corespund perechilor de tip (stare marcat, stare nemarcat). Pas2: (0,1) (1,1) (2,3) stari neechivalente bifarea 4 din tabel (0,2) (1,0) stari neechivalente 5 (1,2) (1,0) stari neechivalente 6 Neexistndstriechivalentededucemcautomatuliniialestedejan forma minimal. a b a a Limbaje formale i automate 51 19)S se minimizeze automatul: Rezolvare: q1 8 q2 9 q3 567 q4 1234 q0q1q2q3 Orice pereche compus dintr-o stare nemarcat i o stare marcat formeaz o pereche de stri neechivalente. (bifrile 1, 2, 3 i 4 din tabel) Vomaplicancontinuareovariantmodificataalgoritmuluide minimizare.Modificareaconstncutareaperechilordestricaresigur nu sunt echivalente dup urmtoarea regul: (X, q3) 3(Y, q4), 4, q Y Q Q Xm =>orice pereche de forma (X, q3) care ndeplineste aceast conditie este o pereche de stri neechivalente. (bifrile 5, 6 i 7 din tabel). (q0,q1) 2 (q2,q3) NU sunt echivalente (bifarea 8 din tabel) (q2,q1) 2 (q2,q3) NU sunt echivalente (bifarea 8 din tabel) (q2,q0)(q1,q1)=> q2 si q0 sunt stri echivalente (q2,q2) (q2,q2) 1 2 3 Limbaje formale i automate 52 Automatul minimal va fi: 20)S se minimizeze automatul : Q ab 106 007 257 353 408 508 606 723 843 n care q0 = 1 i Qm = {2, 4}. Rezolvare. Folosind algoritmul de minimizare, eliminm iniial perechile de stri care nupotfiechivalente(staremarcatcustarenemarcat),apoiverificm celelalteperechidestrirmase.Toateacesteasecompleteazntabelul urmtor. Limbaje formale i automate 53 015 221 3173 49810 52042711 62951226 72830618132516 82223721142419 10234567 Figura II.18. Tabelul corespunztor tuturor perechilor de stri. Din tabel rezulta ca perechile de stari echivalente sunt :(1, 3) (2, 4) (0, 5)(1, 6)(3, 6)(7, 8) Strile componente ale automatului minimal sunt :(1, 3, 6)(2, 4)(0, 5)(7, 8) Automatul minimal rezultat este reprezentat nFigura II.19: Limbaje formale i automate 54 Figura II.19. Automatul minimal pentru problema 20). 21)Fieautomatuldemaijos.Careesteexpresiaregulatcaredescrie limbajul acceptat de acest automat? Rezolvare. Numerotam starile :q0 1 q1 2 q2 3 Se obine un automat cu 3 stri n care starea 3 e marcat. Folosind formula :ER = UQmqiniR1rezulta:ER = 313R

Pentrucalcule,sefolosescformuleleurmtoareitabeluldemaijosn care trecem valorile lui Rkijpentru diveri i, j i k: Rkij= R1 kij+ R1 kik (R1 kkk)*R1 kkj Limbaje formale i automate 55 k = 0k = 1k = 2 k11Rb + b* k12Rab*a k13R-- b*a( + bb*a)*a k21Rbbb* k22R+ bb*a k23Raa k31R-- k32R-- k33Ra + b + a + b + a + b + Calculm 313Ri obinem : R313 = = ( +) = De unde rezult c nu trebuie calculate dect 2 valori pentru k=2 :R213i R233

Restul valorilor pentru k=2 nu le-am calculat. Calculm nti pentru k=0, tiind c R013 nseamn de fapt drumul direct de la starea 1 la starea 3, dac acesta exist. Limbaje formale i automate 56 Pentruacalcularestulvalorilornecesarevomfolosiformulele suplimentare : a + - = a, a a* - = - , a (a + )*= a*, a + a a* = a*, a pe care le considerm cunoscute. Vom obine pentru k=1:

b a R R ) (R R R RR ) (R R R RR ) (R R R Ra R ) (R R R Ra bb a ) b b( R ) (R R R Rbb ) b ( b ) (R R R ) (R R R RR ) (R R R Ra b a b a a ) b ( a R ) (R R R Rb b ) (b ) (b ) b ( ) (b R ) (R R R R033013011031033133012011031032132011011031031131013011021023123* * 012011021022122* * 011021011011021021121013011011013113* * * 012011011012112* * * 011011011011111+ + = = + = = + = = + == + =+ = + + = + == + = = + = = + == + = + + = + == + = + + + + = + = Pentru k=2 : a ) a a(bb b a ) a bb a( b R ) (R R R R123122112113213 = + = + = b a R ) (R R R R123122132133233 + + = + = Iar, n final vom obine expresia regulat cutat: ER = b*a(bb*a)*a(a + b + ) * =b*a(bb*a)*a(a + b) * Limbaje formale i automate 57 22)SseconstruiascautomatulAFN-caremarcheazlimbajuldefinit de expresia regulat : (a + g)(ba)* + a(ba)*a*, ={a, b, g} R= (a + g)(ba)* + a(ba)*a* = r1.r2 + r3.r4.r5

r1=a + g = r6 + r7 r6=a=> r7=g => r1=a + g => r2= (ba)* = r8* r8= ba = r9 . r10 r9= b => r10= a => r8= ba=> r2 = r8* => r1.r2 =>Limbaje formale i automate 58 r3=a => r4= (ba)* = r11* r11= ba = r12 . r13 => r4 = r11* => r5= a* = r12*r12= a =>r5 => r3.r4.r5 => R= (a + g)(ba)* + a(ba)*a* = r1.r2 + r3.r4.r5 => Limbaje formale i automate 59 Probleme propuse 23)SseproiectezeunAFDpestealfabetul={a,b}careaccept cuvintele ce conin minim 3a i nu se termina cu b. 24)SseproiectezeAFDcareacceptpestealfabetul={a,b,c} cuvinte care conin minim 2 c (nu neaprat consecutivi) i nu conin secvena aca.25)SseproiectezeunAFDcareaccepttoateirurilepestealfabetul ={a, b} care conin cel puin 3 a i cel mult 2 b. 26)SseconstruiascunAFDpestealfabetul={a,b}careaccept cuvinte ce conin numr par de a i nu conin subirul abb .27)SseconstruiascunAFDpestealfabetul={a,b,c}careaccept irurile ce conin o singur dat subirul cab. 28)S se proiecteze AFD care, peste alfabetul de intrare {a, b, c}, accept irurilecareconinosingurdatsubirulcabinuseterminn subirul ab. 29)S se proiecteze AFD peste alfabetul = {1, 2, 3}, care accept toate cuvintele care se termin cu subirul 123.30)Careesteautomatulcarepestealfabetul={a,b,c}recunoate cuvintele ce conin numr par de a i numr impar de c? 31)Careesteautomatulcarepestealfabetul={a,b}recunoate cuvintelececoninnumrimpardebicarenuconinsubirul bba? 32)Fieunlactelectronicprevzutcudoubutoaneetichetatecuai respectivb.Lactulsedeschidedacseapaspebutoanen combinaia aba.Din poziiadeschisel poate finchis numaiprin apsareabutonuluib.Ssemodelezefuncionarealactuluiprintr-un automat finit determinist.Limbaje formale i automate 60 33)S se construiasc AFD aferent unui sistem de parolare peste alfabetul = {a, b, c, d} care funcioneaz dup urmtoarele reguli: parolaaretreicaracteredintrecaredoutrebuiesafieidenticedar neconsecutive; caracterul d nu trebuie s fac parte din parol dacda, atunci se ajunge ntr-o stare de blocaj;parola corect conduce ntr-o stare marcata n automat. 34)Ce iruri accepta automatul: ? 35)S se construiasc observatorul urmtorului automat: ab 012, 3 11, 23 241 313 420 n care: q0 = 0 i Qm = {2}. 36)Construii automatul finit determinist echivalent cu : Limbaje formale i automate 61 37)S se calculeze observatorul pentru automatul de mai jos: 38)S se construiasc observatorul urmtorului automat: ab 01, 20 131 220 3-2 n care: q0 = 0 i Qm = {1}. 39)S se construiasc AFD echivalent pentru urmtorul AFN-. baaaq0q1q3q2q4, bab Limbaje formale i automate 62 40)S se proiecteze AFD echivalent cu urmtorul automat AFN-: ba,bq0aq1q3abq2aq4q5b 41)S se construiasc AFN - pentru expresia regulata : (ab)* + (a + bab)* 42)SseconstruiascautomatulAFDcarerecunoatecuvintelece descriulimbajul a(ba)*a* 43)SecereAFDcorespunztorexpresieiregulatepestealfabetul = {0,1}: 01 + (0+11)0*1 44)S se gseasc expresia regulata pentru automatul : q1q0abab Limbaje formale i automate 63 45)S se determine expresia regulat pentru AFD din figura: b ab abaq0q1q2 46)S se calculeze expresia regulat acceptat de automatul: bbaaaq0q1q2 47)Care este expresia regulat pentru automatul de mai jos ? a,b aa bbq0q1q2 48)S se determine expresia regulat pentru automatul : 000 111CBA Limbaje formale i automate 64 49)S se gseasc ER pentru automatul de mai jos: 0q0 01110q1q3 50)S se gseasc ER pentru automatul de mai jos:10q001001q1q2q3 51)S se minimizeze automatul: ab 015 112 232 334 433 516 616 n care: q0 = 0; Qm = {2, 3, 4, 6}. Limbaje formale i automate 65 52)S se minimizeze automatul: 53)S se minimizeze automatul: Limbaje formale i automate 66 54)S se minimizeze automatul: ab 010 137 210 382 460 584 657 767 896 962 n care:q0 = 0 i Qm = {2, 4, 9}. 55)S se minimizeze automatul: ab 060 147 218 360 492 542 658 720 828 998 n care:q0 = 0 i Qm = {3, 7, 9}. Limbaje formale i automate 67 56)S se minimizeze automatul: ab 010 138 268 395 448 510 697 720 828 942 n care:q0 = 0 i Qm = {4, 5, 7}. 57)S se minimizeze automatul: ab 050 150 248 391 497 538 668 720 828 962 n care:q0 = 0 i Qm = {1, 6, 7}. Limbaje formale i automate 68 58)S se minimizeze automatul: ab 014 117 217 335 418 598 634 726 834 935 n care: q0 = 0; Qm = {2, 9}. 59)Un procesor este precedat de o coada de capacitate 1 astfel ca ntregul sistem format din procesor i coada are capacitatea total de 2 job-uri. Existadoutipuridiferitedejob-uriJ1iJ2carefaccererectre procesor,J1fiindmaiprioritardectJ2.Deaceea,daclasosirea job-uluiJ1elgseteprocesorulocupatcujob-ulJ2atuncilnltur. Job-ulJ2 serentoarcencoadaiarjob-ulJ1 primeteserviciul.Orice jobnousositcaregsetesistemulplinesterejectatipierdut. Construii un automat care s descrie funcionarea acestui sistem. 60)FiedouprocesoareP1iP2careopereaznparalel.Capacitatea totalaluiP1(coadaplusprocesor)estek1=1iarcapacitateatotalaa luiP2estek2=2.Sistemulprimetedoutipuridejob-urij1ij2care trebuieprocesatepeprocesorulP1respectivpeprocesorulP2.Dup procesare job-urile prsesc sistemul. Daca un job gsete coada plin la sosire atunci el este rejectat. Construii AFD-ul sistemului. Limbaje formale i automate 69 61)Se consider un lact electronic cu urmtoarele caracteristici: are n componen 3 butoane (A, B i C); iniial lactul este nchis; parola pentru deschidere satisface simultan condiiile: oconine 3 simbolurionu conine simbolul C osimbolurile identice sunt consecutiveonu exist mai mult de dou simboluri identice n parol dinstarealactdeschisoricetastacionatvanchidelactul, pentruredeschiderefiindnecesarintroducereauneiparole corecte; introducereanparolasimboluluiCducelablocarea lactului; deblocarealactuluiserealizeaznurmasecveneiCCA tastat din starea de blocaj; o parol care are 3 simboluri dar nu blocheaz lactul i nici nu-l deschide va necesita pentru deschiderea lactului introducerea uneisecvenede3simboluricaressatisfaccerineleparolei corecte. Modelai prin intermediul automatelor evoluia lactului. 62)Seconsiderunprocesorcaremparteunjobndoutaskuri.Primul seexecutataskul1,dupaceeataskul2momentncarejobul prsetesistemul(lasfritultaskului1).Sepresupunecsistemul arecapacitateadetreijoburi.Procesorultrebuiestermineambele taskurialeunuijobnaintesnceapprocesareaurmtoruluijob. Existunmecanismdetime-outpentrufiecarejob,careopereaz astfel: cnd un job intra n sistem , taskului 1 i se acord o unitate de timppentruexecuie;dacjobulstnsistemounitatedetimpi taskul1alsunus-aexecutat,atuncijobulesteterminatforati urmtoruljobdincoada,dacexistvafiprocesat.Seconsider sistemuliniialgol.Presupunemurmtoareascardetimppentru sosirilejoburilor (0;0,2; 0,9; 1,6; 2) i pentru fiecare sedtimpul de execuiepentrufiecaretask:I(0,8;0,7);II(0,9;0,7);III(0,3;0,6); Limbaje formale i automate 70 IV(0,9;0,5)iV(0,1;1,2).Construiiodiagramdetimpincluznd timpiideapariieaevenimenteloritipulevenimentelor.Pebaza acesteidiagramedeterminaicarejobsetermincorecticarese termin forat (time out). Construii o diagram de stri- tranziii. 63)UnsistemdefabricaiesimpluconinedoumainiM1iM2iun bufferBpoziionatntremaini.IntrareapieselorpemainaM1este nelimitat.CndopiesesteprocesatpemainaM1esteplasatn bufferul B care are capacitatea de o pies. Piesa este apoi procesat pe mainaM2.Fiecaremainareposibilitateadeasedefecta.Iniial mainilesuntlibere.Comportamentulntreguluisistemtrebuies satisfac urmtoarele cerine: M1 poate ncepe procesarea doar dac bufferul B este gol; M2 poate ncepe procesarea doar dac bufferul B este plin; M1 nu poate ncepe procesarea daca M2 este defect; DacambelemainisuntdefecteatunciM2trebuiereparat prima. Construiiautomatulcaredescriecomportamentuladmisibilal sistemului.64)Un sistem conine 3 servere ca n figura urmtoare. Clienii care intr nsistemajungmaintincoadadelaserverul1idupcesuntprocesai pe serverul 1 ei sunt rutaipe serverele 2 sau 3. Politica de rutare este trimiterea clientului ntotdeauna ctre serverul cu coada cea mai mic. n cazul n care cele dou cozi sunt egale , clientul este rutat ctre serverul 2. Dup procesarea pe serverul 2 sau 3 clienii prsesc sistemul.Unclientcaresosetedinexterioresteacceptatnsistem atttimpctnumrultotaldeclienidinsistemestemaxim2,altfel clieniisuntrejectai.Sseconstruiascautomatulcaredescrie funcionarea sistemului. 123 Limbaje formale i automate 71 65)OceluladefabricaieestealctuitdindoumainiM1iM2iun AGV. Automatele celor trei componente sunt : readyat1loadat101M1 giveto2loadat201M2 loadat2giveout021giveto2loadat1AGV a)S se construiasc G = M1|| M2 ||AGV b)Este G blocant? 66)Un sistem de fabricaie conine 2mainiM1 i M2i un robotR care preiaopiesprelucratdepemainaM1iodepunepemainaM2. Nuexistaniciunbufferpentruceledoumaini.Dacopieseste furnizatluiM1ntimpceaceastaesteocupatatuncipiesaeste rejectat.DacrobotultransportpiesactreM2ntimpceaceasta esteocupatelateaptpncndM2opoateaccepta.Dupce robotul a depus piesa pe M2 el revine n poziia iniial, de unde poate lua o noua piesa de pe M1.S se construiasc AFD care descrie funcionarea procesului.67)Fieuntronsondecaleferatcarearatcanfigur.Fiealfabetul={i1,s1, i2, s2, i3, s3} unde ikreprezint intrarea unui tren pe tronsonul de cale ferat k, iar sk = ieirea trenului de pe tronsonul k. Se noteaz cuqivariabiladestareasociattrenuluiicarereprezintprezena trenuluipeaceltronson.Astfeldacqi=1atuncitrenulseaflpe Limbaje formale i automate 72 tronson, altfel qi = 0. Starea ntregului sistem este q=(q1, q2, q3). S se construiascmainaMoorecaremodeleazacestsistemigenereaz n fiecare stare valoarea lui q. Care este limbajul L care nu conduce n starea de blocaj reprezentat pe figur?i3i1i2s1s2s3 68)Fiedoumainicudoustriposibile:liberiocupatisetulde evenimente={s1,f1,s2,f2},undesireprezintaciuneadestart funcionarepentrumainai,iarfisemnificaciuneadesfrit funcionarepentrumainai.PentrufiecaremainMi,trecereadin starealibernstareaocupatsefacenconcordancuapariia evenimentului si, iar trecerea din starea ocupat n starea liber se face la apariia evenimentului fi.a)S se construiasc automatele ce descriu funcionarea mainilor i automatul ce descrie funcionarea ntregului sistem. b)Seintroduce o specificaie de funcionare: ntrecele doumaini exist un buffer X de capacitate 1 , care poate avea dou stri: x0 buffergolix1-bufferplin.Secereautomatulcaredescrie funcionarea stocului precizndu-se evenimentele interzise i cele acceptate de fiecare stare.M1M2X 69)Doifilosofistaulaomaspecaresegsescdoufarfurii,fiecaren faacteunuifilosofidoufurculiesituatedeoparteidealtaa filosofilor.Comportamentulfiecruifilosofesteurmtorul:fiecare filosofpoategndisaupoatemnca.Pentruatrecedinstarea Limbaje formale i automate 73 gndetenstareamnncfilosofultrebuiesridiceambele furculiedepemas,pernd,noriceordine.Dupcefilosoful terminademncat,eldepuneambelefurculiepemasirevinen stareagndete.Alegndunsetdeevenimentectmai reprezentativ,construiiattautomateleaferenteentitilorsistemului ct i automatul care descrie funcionarea ntregului sistem.70)Douprocesoarepartajeazomemoriecomun.Partajareaeste exclusiv. Fiecare procesor este liber pn cnd trebuie s execute un task, dup care trece n starea de cerere acces memorie. Atunci cnd memoriaesteliber,procesoruloaloc,executtaskuliapoio elibereaz.nacestmomentprocesoruldevineliber.Sse construiascautomatelecaredescriufuncionareasubsistemelor componente i automatul corespunztor funcionrii ntregului sistem. 74 CAPITOLUL III REELE PETRI Breviar Definiie Reelele Petri (RP) sunt grafuri orientate cu dou tipuri de noduri: poziii i tranziii.Formal,oRPordinariautonompoatefidefinitprintr-un cvintuplu: RP = {P, T, Pre, Post, M0} unde: Pestemulimeapoziiilor,simbolizateprincercuri;poziiile modeleaz variabile de stare sau condiii; T este mulimea tranziiilor, simbolizate prin bare sau dreptunghiuri; tranziiile modeleaz evenimente sau aciuni; Mulimile P i T sunt disjuncteP T = Pre: PxT -> {0, 1} reprezint arcele care duc de la poziii la tranziii; Post:PxT->{0,1}reprezintarcelecareducdelatranziiila poziii. ntr-oRP,ntotdeaunaunarcunetedounoduridetipuri diferite (o poziie i o tranziie). MP N : este vectorul de marcaj, definit pe mulimea poziiilor reelei,cuvalori nmulimeanumerelor naturale;un elementm(Pi) alvectoruluiindicnumruldejetoanedemarcajdinpoziiaPia reelei la un moment dat.Dacseconsiderpoziiilereeleicavariabiledestareale sistemuluiastfelmodelat,atuncimarcajul(vectoruldemarcaj) reprezint starea sistemului.M0 este marcajul iniial la lansarea sistemului (starea iniial). Starea unei RP se modific prin execuia tranziiilor. Reele Petri 75 Reguli pentru execuia tranziiilor: 1.Otranziieseexecutnumaidacestevalid.OtranziieTjeste validnumaidactoatepoziiilesaledeintrare(adictoate poziiile Pi pentru care Pre(Pi,Tj)=1) sunt marcate (m(Pi)1). 2.ntr-oRPordinarautonomseexecutosingurtranziielaun momentdat(indiferentctetranziiisuntvalide).Aceastregul are la baz dou ipoteze: Dou evenimente independente nu pot s aib loc simultan, Fiecare tranziie reprezint un eveniment distinct. 3.Execuia unei tranziii Tj se face n doi pai: Din fiecare poziie de intrare a lui Tj se retrage cte un jeton de marcaj, n fiecare poziie de ieire a lui Tj se pune un jeton de marcaj. 4.Execuia unei tranziii are durat nul. Din punctul de vedere al nivelelor de reprezentare SED, exist urmtoarele clase de RP:reele Petri autonome la nivel logic, reelePetritemporizate,sincronizateiinterpretatelanivel temporal (determinist), reele Petri stochastice la nivel stochastic. n afar de aceste clase distincte, a cror putere de modelare este diferit n funciedemoduldeintegrarealtimpuluinmodel,existoseriede extensii ale modelelor RP, extensii care se pot aplica fiecrei clase, fr a le modifica nici proprietile i nici puterea de modelare. Rolul extensiilor este de a realiza modele mai compacte. Dintre acestea, cele mai cunoscute sunt: RPgeneralizate:seasociazponderi(numerenaturale)arcelor.n mod implicit ponderea unui arc este 1. Se mai numesc i RP cu arce ponderate. Pre: PxT N i Post: PxT N Reele Petri 76 Pentruaceastclasdereelereguliledeexecuieatranziiilorse modific astfel: dac arcul Pi Tj are ponderea q , Tj este valid dac Pi conine cel puin q jetoane.prin executarea lui Tj se retrag q jetoane din Pi ; dacarculTjPkarepondeream,prinexecutarealuiTjse adaug m jetoane n poziia Pk. RPcucapaciti:seasociazcapaciti(numerenaturale) poziiilor.nmodimplicit,capacitateauneipoziiiesteinfinit. Reguliledeexecuiealetranziiilorsemodificastfel:otranziie este executabil dac i numai dac prin execuia ei nu se depete capacitatea vreuneia dintre poziiile sale de ieire. Tranziii speciale: tranziiesurs este otranziiecare nu are nicio poziiedeintrare. O astfel de tranziie este n permanen valid; tranziie capcan este o tranziie care nu are nici o poziie de ieire. Notaii: *M = mulimea marcajelor accesibile plecnd de la marcajul M; S = secven de execuie = succesiune de tranziii ce se pot executa n aceast ordine; M0(SM2:executareasecveneiSporninddelamarcajulM0 conduce la marcajul M2. Marcaj superior: M1 M2 m1 (Pi ) m2 (Pi ), Pi ; Marcaj strict superior: M1 > M2 M1 M2 i Pi a.. m1 (Pi ) > m2 (Pi ). Reele Petri 77 Proprietile reelelor Petri. Proprietatea 1: Mrginire 1.OpoziiePiestemrginitpentruunmarcajiniialM0dac M*M0 ,existaunnumrnaturalmastfelnct,oricarearfi evoluia reelei, m(Pi) 0} Tj= {PiP | Post(pi, tj) > 0} Pi = {TjT | Post(pi, tj) > 0} Pi= {TjT | Pre(pi, tj) > 0} W=Post-Pre=[wij]matriceadeincidenareelei(este independent de marcaj) Ecuaia fundamental : Mk = Mi + W S, pentruosecvendeexecutiiSa..M i(SMk,undeSestevectorul caracteristicalsecveneiS(vectordedimensiunemncaresjcorespunde num rului de validri ale tranziiei Tj n secvena S. Reele Petri 79 Investigarea proprietilor RP cu ajutorul grafului de marcaje sau al arborelui de acoperire. Algoritmul de construcie a arborelui de acoperire Pas 1.Plecndde la marcajul iniial M0se indictoate tranziiile valide imarcajelesuccesivecorespunztoare.Dacunuldinaceste marcajeestestrictsuperiorluiM0,sepunepentrufiecare component superioar componentei corespunztoare din M0 . Pas 2.PentrufiecarenoumarcajMialarboreluisefacefiePas2.1.fie Pas 2.2. Pas 2.1.DacexistunmarcajMj=Micareafostexploratdeja, atunci Mi nu are succesor. Pas 2.2.Dac nu exist un marcajMj = Mi pe calea de la M0 la Mi atunci seprelungete arborele adugndu-setoisuccesorii lui Mi . Pentru fiecare succesor Mk al lui Mi : 1)o component a lui Mi rmne o component a lui Mk ; 2)dacexistunmarcajMjpecaleadelaM0laMka.. Mk > Mj , atunci se pune pentru fiecare component aluiMksuperioarcomponenteicorespunztoaredin Mj . Observaie Graful de acoperire (sau de marcaje accesibile) se obine din arborele de acoperire,princoncatenareamarcajelorcareserepet.Seobinnacest fel bucle n graful de acoperire, care n arbore nu apreau. Reele Petri 80 Reele Petri sincronizate 1.O RP sincronizat este un triplet unde: R - este o RP marcat; E - este o mulime de evenimente externe; Sinc:TE{e},TfiindmulimeatranziiilordinRiare evenimentul sigur (ntotdeauna activ). 2.O RP este total sincronizat dac Sinc: T E. Executarea unei tranziii se face dac tranziia este valid; atunci cnd se produce evenimentul asociat. Notaie T(x,M)mulimeatranziiilorreceptivelaevenimentulxE{e}pentru marcajul M. Definiii 1.Sk se numete secven de simulare complet (SSC) n raport cu evenimentul x, pentru marcajul M, dac: Skesteo secvendeexecuiidin marcajul M,compusnumai din tranziii aparinnd lui T(x,M); toate tranziiile din T(x,M) apar cel mult odat n Sk ; toate secvenele Sh obinute permutnd tranziiile lui Sk sunt de asemenea secvene de execuie plecnd de la M; nuexistsecvendeexecuiidelungimemaimarecares conintoatetranziiileluiSkicaresndeplineascprimele trei condiii. 2.Se numete execuie iterativ la apariia evenimentului extern ei osecvencompusdinexecutareauneiSSCsubapariialuiei, urmateventualdeexecutareatuturorSSCposibilesubapariia lui e. Dac pentru un marcaj M nu este posibil execuia nici unei SSCsube,atunciMestenumitmarcajstabil.ncazcontrar,M se numete instabil. Reele Petri 81 Algoritmul de interpretare a unei RP sincronizate pas1.Iniializri:1)marcajul,2)mulimeamomentelorlacareauloc evenimentele externe 3) evenimentul curent x. Fie x = e. Salt la pas3. pas2.Se consider primul moment t la care are loc un eveniment extern ei . Fie x = ei . pas3.Sedeterminmulimeadetranziiiexecutabilesubapariia evenimentuluix.Dacaceastmulimeestevid,sesuprimtdin mulimeamomentelorlacareaulocevenimenteexterne.Saltla pas2. pas4.Se efectueaz o SSC. Se face x = e. Salt la pas3. Proprieti suplimentare ale reelelor Petri sincronizate. ORPsincronizatestepromptdacpentrutoatemarcajeleaccesibile stabileipentrutoateevenimenteleei,execuiaiterativsubapariia evenimentului extern ei conine un numr finit de SSC. DacexistunnumrnaturalkastfelnctnumruldeSSCk,atunci spunem c reeaua este k-prompt. Proprietate O RP sincronizat este prompt dac ndeplinete urmtoarele condiii: toatetranziiilesurs(frniciopoziienamonte)auasociate evenimente externe; pentrutoateciclurileP1T1P2T2...PqTqa..avemarcelePiTi,Ti Pi+1 si Tq P1 exist cel puin o tranziie care s fie sincronizat pe un eveniment extern. Observaie ProprietileRPautonomenuseconservatuncicndreeauaeste sincronizat.Reele Petri 82 Reele Petri temporizate RetelelePetritemporizatesuntaceletipuridereelencaretimpul influeneazexplicitevoluiareelei.Acestereelesempartn: P-temporizate i T-temporizate. RP P-temporizate: se asociaz fiecrei poziii Pi o temporizare di. n mod implicit, temporizarea asociata unei poziii este nul. O RP P-temporizat este un dublet unde: R este o RP marcat; Temp:PQ+,undeQ+reprezintmulimeadenumereraionale pozitive a.. Temp(pi )= di . Seconsidercunjetondepusntr-opoziiePinmomentulteste indisponibil pe durata temporizrii [t, t+di], dup care devine disponibil. n acestfel,launmomentdetimpoarecaremarcajulMalreeleiaredou componente: marcajul disponibil i marcajul indisponibil. (M = Md + Ml). Validareauneitranziiiestefcutdoardecomponentadisponibila poziiilor sale de intrare. Ipotez de lucru La momentul iniial marcajul M0 este disponibil. nvedereaanalizeiRPtemporizateseconsidercotranziieseexecut dendatcedevinevalid.Acestregimdefuncionaresenumete funcionare la vitez maximal. Se poate demonstra c pentru o RP temporizat mrginit i cu temporizri cu valori raionale, funcionarea la viteza maximal conduce dup un timp la un regim repetitiv numit regim staionar. ncadrulregimuluistaionarsefaceanalizacantitativ(evaluarea performanelor) sistemului. Pentru aceasta se definesc urmtoarele mrimi: 1.Frecvenadeexecuiefj,auneitranziiiTjcafiindnumrul mediu de execuii ale lui Tj pe unitatea de timp.2.Numrulmediudemarcajentr-opoziiePicafiindegalcu produsulntresumafrecvenelordeexecuiealetranziiilorde intrare n poziia Pi i durata sa asociat di. Reele Petri 83 Un alt regim de funcionare este cel la vitez optimal: o RP P-temporizat funcioneazlavitezoptimaldacniciunjetonnurmnentr-o poziieunintervaldetimpmaimaredectduratasadeindisponibilitate. Unmodelcarearefuncionarelavitezoptimalesteconsideratafiun model fr ntrzieri (nici un jeton nu ateapt s fie utilizat). ReelePetriT-temporizate:seasociazfiecreitranziiiTjoduratde execuie dj. Implicit, durata de execuie a unei tranziii este nul. Definiie: O RP T-temporizat este un dublet unde: R este o RP marcat; Temp:TQ+,cuQ+omulimedenumereraionalepozitivea.. Temp(Ti )= di

Pentruaceastclasdereelevomfacedistincientremomentuldetimp la care o tranziie devine valid (care este momentul de timp n care avem nfiecarepoziiedeintrarentranziieunnumrsuficientdejetoane)i momentuldetimplacaretranziiaesteexecutabil(carevafiegalcu momentuldetimplacaretranziiaafostvalidatlacaresevaaduga temporizareaasociattranziiei).ngeneralotranziiesevaexecutadin momentulncaredevinevaliddupcetrecetemporizareaasociat. Excepiaestereprezentatdesitaiiledeconflictstructuralcaresunt rezolvateprinexecutareaprimeitranziiicedevineexecutabil(nuvom aveaconflicteefectivepentrureeleleT-temprozatedectdacdou tranziii ale unui conflict structural devin simultan executabile i nu exist suficiente jetoane pentru a le executa pe ambele). Noiuniledefuncionarelavitezamaximal,funcionarelavitezaproprie i frecven de execuie se pot extinde i la reele T-temporizate. Reprezentare grafic: bar ( ) pentru o tranziie a crei temporizare este nul; dreptunghi ( ) pentru o tranziie a crei temporizare este nenul; Reele Petri 84 Observaie OricereeaPetriT-temporizatpoatefitransformatntr-oreeaPetri P-temporizat i invers. d d T-temporizareP-temporizare dd P-temporizareT-temporizare Reele Petri 85 Probleme rezolvate 71)Ssestudiezeproprietiledemrginire,blocaje,viabilitatei reiniializabilitatepentru reelele Petri ilustrate n figura urmtoare: -a--b- P1P12 (3)T4 T4T3T3 T1 T1P3P3P2 P2T2T2 Figura III.1. Reele Petri autonome. Rezolvare.Graful de marcaje al reelei din figura a) este prezentat n Figura III.2: Figura III.2. Graful de marcaje pentru cazul -a-. Se observ pe acest graf de acoperire c n acest caz reeaua este mrginit, nu are blocaje i de asemenea nu este viabil. Despre aceast reea se poate spunecestecvasiviabildeoarecetranzitiileT3iT4sepotexecutao singur dat, dup care se ajunge la o stare asemntoare celei iniiale care are ns doar un jeton n P1 i pentru care tranziia T3 (i deci i T4) nu se mai poate executa niciodat. Proprietateadereiniializabilitatenuestendeplinitdeoarecenuexisto secven de tranziii care s conduc din marcajul M3 n marcajul iniial.Pentrureeauadinfigurab)avemdouposibilitidevaloripentruarcul de la T4 la P1: valoare de 2 i valoare mai mare de 2. PentrucazulncarepondereaarculuiT4P1 egalcu2,grafulde marcajeaccesibileesteilustratnFiguraIII.3.Dingrafsededucec reeaua estemrginitifr blocaje cacea dinainte, n plus, prin buclele care s-au format n graf, reeaua este viabil, pentru oricare marcaj din graf Reele Petri 86 ioricaretranziieputndu-segsiosecvenporninddelaacestmarcaj care s conin tranziia respectiv. T4T3T2T2020|\

||||110|\

||||200|\

||||001|\

||||T1 T1M0 = Figura III.3. Graful de marcaje pentru cazul -b- i pondere 2. Peacestexemplusemaipoatefaceoobservaie.Prinbuclelecares-au formatpegraf sepot identifica secvenele repetitive(secvenedetranziii care,porninddelaM0,conduclaM0).Acesteasunt:S1=T1T2,S2 = T1T3T4,S3 = T1T1T2T2, S3 = T1T1T2T3T4. Se poate vedea uor c din toatemarcajeleaccesibiledepeacestgrafsepoateajungenmarcajul iniial, deci reeaua este reiniializabil. S consideram un ultim caz n care ponderea arcului T4 P1 este 3 (vezi Figura III.1 -b-). n acest caz se obine urmtorul graf de acoperire: T4||||

\|002M0=T1T2 ||||

\|011M1=||||

\|020M2=T1T2T3||||

\|100M3=||||

\|00M4=T1||||

\|0M5=T3||||

\|M6=T1, T2T1, T2, T3, T4 Figura III.4. Graful de marcaje pentru cazul -b- i pondere 3. Seobservcpeacestgrafs-asubstituit,conformalgoritmuluide construcieaarboreluideacoperire,valoarea3cares-arfiobinutdup primaexecutarealuiT4cu.ncontinuaresepoateobservacreeaua Petri aretoatepoziiilenemrginite;nacest fel sededucec reeaua este nemrginit. Se pstreaz ns proprietile de viabilitate i de fr blocaje. Reele Petri 87 72)Sseconstruiascgrafuldemarcajeissediscuteproprietile reeleisincronizatedinFiguraIII.5.Ssecompareacesteproprieti cu cele ale reelei nesincronizate.P1e1T2e1T1P3 P2e2T3P5P4e3T4e3T5 Figura III.5. Reea Petri sincronizat. Rezolvare.ReeauaPetrisincronizatestemrginit,frblocaje,viabil, conservativ(existuninvariantdemarcajceconinetoatepoziiile reelei)ireiniializabilaacumsepoatevedeaimediatdingrafulde marcaje accesibile. {T1, T2}/e1T3/e2{T4, T5}/e3M0 =20000

(((((((M1 =(((((((

00110M2 =(((((((

11000 Figura III.6. Graful de marcaje pentru reeaua sincronizat. Invariantul de marcaj este: m(P1) + m(P2) + m(P3) + m(P4) + m(P5) = 2 Dacnsconsidermaceeaireeadarnesincronizatsepoatevedea, construind din nou graful de marcaje, c aceasta nu mai este viabil i c, prinexecutareadedouorilarndatranziieiT1sauatranziieiT2 pornind de la marcajul iniial, se ajunge la blocaj; de la aceste marcaje nici Reele Petri 88 otranziienuvamaiputeafiexecutat.SecveneleT1T1iT2T2nusunt posibile pentru reeaua sincronizat. Figura III.7. Graful de marcaje pentru reeaua autonom. M0=(((((((

00002 M1=(((((((

00011 M2=(((((((

00101 M3=(((((((

00020 M4=(((((((

00110 M5=(((((((

00200 M6=(((((((

11000 M7=(((((((

10001 M8=(((((((

01001 M9=(((((((

10010 M10=(((((((

10100 M11=(((((((

01010 M12=(((((((

01100 T1 T2 T1 T1 T1 T1 T2 T2 T2 T2 T3 T4 T4 T4 T4 TT5 T5 Reele Petri 89 73)Construiigrafuldemarcajeiprecizaiproprietileurmtoarei Reele Petri: Rezolvare. Graful de marcaje pentru reeauatemporizat demaisusesteprezentatn figura urmtoare. M0=(((((((((

000001M1=(((((((((

000) 2 ( 1) 1 ( 10M2=(((((((((

00) 2 ( 1) 1 ( 100 M3 = (((((((((

0) 1 ( 1) 1 ( 1000M4 = (((((((((

) 1 ( 100000 T2 d = 1 T1 d = 0 T4 d = 1 T5 d = 1 T1 d = 1 M5=(((((((((

00000) 1 ( 1 T7 d = 1 Marcajuliniialestecaracterizat(princonvenie)defaptulctoate jetoanele sunt disponibile. Acest lucru permite ca tranziia T1 s fie valid Reele Petri 90 lamomentuliniial(d=0).Prinexecuiasasedepunecteunjetonde marcajnP2iP3.Valoareadurateideindisponibilitatepentrujetoanele nou depuse n poziii va fi egal cu temporizarea asociat acestora.Din marcajul M1 vor putea fi validate tranziiile T2 (dup o unitate de timp) i T4 (dup dou uniti de timp). Datorit faptului c sistemul este analizat la funcionare la vitez maximal, prima se va executa tranziia T2.nmarcajulM2sepoateobservacduratadeindisponibilitateajetonului din poziia P3 a fost micorat (cu timpul scurs pn la executarea tranziiei T2). Este de remarcat i faptul c marcajul M6 difer de marcajul M0. Pentru ca dou marcaje ale unei reele P-temporizate s fie identice trebuie ca ele s conin pentru fiecare poziie: -acelai numr de jetoane disponibile; -acelai numr de jetoane indispnibile; -aceleaiduratedeindisponibilitateasociatejetoanelor indisponibile. Dinpunctdevederealproprietilor,reeauaestemrginit,nuexist blocaje,nuesteviabilinicimcarcvasiviabil(deoarecepegrafulde marcajenuseregsesctoatetranziiiledinreeaT3sauT6),nuprezint secvenerepetitiveinicinuestereiniializabil(datoritconvenieicare spune c n marcajul iniial toate jetoanele sunt disponibile) Reele Petri 91 74)Se consider celula de fabricaie din figura de mai jos care include: dou maini cu funcionare similar M1 i M2;

o band rulant (un conveior) de intrare CONV1 ca surs infinit de repere; un conveior de ieire ca depozit infinit. M1M2CONV1CONV2p2p1 Celulapoateproducedoutipuridepiese:p1ip2,fiecaredintreele trebuind procesat pe ambele maini. Duratele de procesare respective sunt: p1p2 M13 uniti de timp2 uniti de timp M21 unitate de timp4 uniti de timp ncrcareapieselordepeCONV1peoricaredintremainiaredurata de1unitatedetimp.Dendatceoperaiadencrcareafost ncheiat, procesarea piesei ncepe fr ntrziere, iar descrcarea face parte din procesare. Piesa de tip p1 este prelucrat nti pe maina M2 i apoi pe maina M1, iar piesa de tip p2 este prelucrat nti pe maina M1iapoipemainaM2.Fiecaremainposedunbufferdeintrare cu o poziie, pentru transferul pieselor procesate pe jumtate.Secere construireareeleiPetriP-temporizatcemodeleazaceast celul de fabricaie. Reele Petri 92 Rezolvare: ProiectareautilizndreelePetripresupuneidentificareapoziiilori tranziiilor ce caracterizeaz sistemul respectiv.Dinpunctdevederealsemnificaiei,poziiileuneireelePetrimodeleaz variabiledestare(strialecomponentelorsistemului)saucondiiiiar tranziiile modeleaz aciuni ce schimb starea componentelor.Pentruaputeamodelasistemultrebuiesidentificmdinenunul problemeicomponentelesistemului,strilencareacesteasepotaflai aciunile care produc modificarea acestor stri. Sistemuldescrismaisusestealctuitdinasecomponente:doumaini, dou benzi transportoare i dou buffere. Fiecaredintremaini(avndcapacitateunuiputndprocesadoutipuri de piese) se poate afla ntr-una din urmtoarele stri: - liber; - ocupat cu p1; - ocupat cu p1; - ncrcndpiesadelaCONV1 (reeaua fiind P-temporizatncrcarea va fi o stare a sistemului caracteruizat de o anumit durat); nconsecinfiecaremainvafimodelatprinpatrupoziii(cteuna pentru fiecare stare). Conveioarelefiinddecapacitatenelimitatvorfimodelatedoarprin numruldepiesedeunanumittipprezentepeconveior,pentrufiecare avnddoupoziii:unacorespunztoarenumruluidepiesedetipp1 prezenteialtacorespunztoarenumruluidepiesedetipp2depe conveior. Bufferele n care sunt depozitate piesele ce urmeaz a fi trecute pe cealalt main (avnd capacitate unu i putnd conine doar un singur tip de piese) sevormodelaprindoupoziiicuurmtoarelesemnificaii:numrulde piese ce pot intra n buffer i numrul de piese existente n buffer. n total vom avea un numr de 16 poziii. n ceea ce privete aciunile care pot avea loc se pt identifica pentru fiecare fluxdeprocesareaunuitipdepiesunnumrde5aciunirealizaten cadrul celulei i de nc dou prin care celula preia piese din exterior i le Reele Petri 93 depunenexterior.Aciunilerealizatencadrulceluleisunt:nceput ncrcare,sfritncrcare(cecoincidecunceputulprocesrii),depunere nbuffer(eliberareprimamain),depunerepece-ade-adouamaini depunere pe CONV2.Cu aceste informaii stabilite i ncercnd s aranjm nodurile reelei n aa felnctsurmrimceledoufluxurideprelucrare,reeauaPetricare modeleaz sistemul este: iar semnificaia nodurilor reelei este: P1 numrul de piese de tip p1 de pe CONV1; P2 maina 1 ncarc pies p1; P3 maina 1 proceseaz pies p1; P4 maina 1 liber; Reele Petri 94 P5 bufferul de intrare al mainii 2 ocupat; P6 bufferul de intrare al mainii 2 liber; P7 maina 2 proceseaz pies p1; P8 maina 2 liber; P9 numrul de piese de tip p1 de pe CONV2; P10 numrul de piese de tip p2 de pe CONV1; P11 maina 2 ncarc pies p2; P12 maina 2 proceseaz pies p2; P13 bufferul de intrare al mainii 1 ocupat; P14 bufferul de intrare al mainii 1 liber; P15 maina 1 proceseaz pies p2; P16 numrul de piese de tip p2 de pe CONV2; T1 nceput ncrcare main 1 cu pies p1; T2 sfrit ncrcare main 1; T3 depunere n bufferul mainii 2; T4 nceputul procesrii pe maina 2; T5 depunere a piesei p1 pe CONV2; T6 nceput ncrcare main 2 cu pies p2; T7 sfrit ncrcare main 2; T8 depunere n bufferul mainii 1; T9 nceputul procesrii pe maina 1; T10 depunere a piesei p2 pe CONV2; T11 depunere din exterior pe CONV1 a unei piese p1; T12 depunere din exterior pe CONV1 a unei piese p2; T13 scoatere n exterior de pe CONV2 a unei piese p1; T14 scoatere n exterior de pe CONV2 a unei piese p2. Reele Petri 95 Probleme propuse 75)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri: P1P2 P3P4P5P6T1T2 T3T4T5T6T7 76)SedreeauaPetridinfigurademaijos.Secerestudierea proprietilor(mrginire,viabilitate,conflicte,conservativitate, invariani) pe baza grafului de marcaje, pentru marcajul iniial M0= [1 0 k 0].P11P21P31P41T21T11T41T31kk Reele Petri 96 77)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri: 2P1P2P3P4P5P6T1T2T3T4T5T6 78)Fie reeaua din figura de mai jos: P2P1P4P3 P5P6T1T2T3T4 Se cer: a)proprietiledemrginire,viabilitate,conflicte,siguran, puritate; b)invarianii de marcaj; c)limbajul generat de RP. Reele Petri 97 79)Se consider RP din figura de mai jos. S se construiasc arborele de acoperireissestudiezeproprietiledemrginire,viabilitate reversibilitate i conservativitate. Care sunt invarianii de marcaj i de execuie?T3T1P1P2P3P4T2 80)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri: P1 P2P4P3P5T1T2T3 T4 Reele Petri 98 81)SsestudiezeproprietilereeleiPetridinfigurademaijos.Sse precizeze invarianii de execuie i limbajul reelei. P3P5P4P1P2T2T1T3T4 82)Sserealizezegrafuldemarcajeisseprecizezeproprietile (mrginire,viabilitate,blocaje,conflicte,invarianidemarcaj, invarianideexecuie,conservativitate)pentrureeauadinfigurade mai jos. P1P2P3 P4P5 T1T2 T3T4 Reele Petri 99 83)SsedetermineproprietileReeleiPetridinfigurademaijos utiliznd graful de marcaje. 84)Fie reeaua Petri generalizat din figura de mai jos. a)Care sunt tranziiile valide din M0 ? b)Dupexecuiaadoutranziiireeauaseblocheaz.Caresunt tranziiile i care este marcajul de blocaj?c)Este reeaua mrginit? Justificai rspunsul. Reeaua este viabil?d)DemonstraicsecvenaT3T1sepoateexecutamaximdedou ori.2P1P4P2T111T2T4T3P3 85)S se discute proprietile RP din figura de mai jos.Reele Petri 100 P2P4P3P5T1T2T4T3T5P6T6T7P1 86)Construii arborele de acoperire i graful de marcaje accesibile pentru reeaua Petri din figura de mai jos. Studiai proprietile de mrginire, viabilitate fr blocaje i conservativitate.T2T1T3P1P2P3 Reele Petri 101 87)Determinaisecvenadesimularecompleta(SSC)nraportcu evenimentulapentrumarcajeleiniialepentrureeauaPetri sincronizata din figura de mai jos: a)M0= [2 1 1 0 0 1] b)M0 = [2 2 2 0 0 2] Precizai care din SSC sunt maximale i explicai rspunsul.P1P2P4P3P5P6T1T2T4T3T5baaaT6ba 88)S seconstruiascgrafuldemarcaje pentru reeaua din figura demai josattncazulsincronizatctincazulautonom.Ssediscute proprietile reelei n ambele situaii. P1e2T1e1T2P2e3T5e2T3T4e1P3 Reele Petri 102 89)PentrureeauaPetrisincronizatdinfigurademaijossse construiasc graful de marcaje i s se precizeze proprietile. e1T1P2P1 e1T4T2eT3 e2 e2T5P4P3 90)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri: P1P2P4P3P5T1T2T3T4T5eeee1e1 Reele Petri 103 91)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri att pentru cazul sincronizat ct i pentru cazul autonom: P1 P2P4P3P5T1T2T3 T4eee1e1 92)Sseconstruiascgrafuldemarcajeisseprecizezeproprietile urmtoarei reele Petri att pentru cazul sincronizat ct i pentru cazul autonom: P1P2P4P3P5 T1T2T3T4eee1e1T5e1 Reele Petri 104 93)S se construiasc graful de marcaje al RP din figur i pe baza lui : a)s se determineproprietile; b)ssecompareproprietiledelapunctula)cucelealereelei autonome. P1P2P4P3P5P6T1T2 T4T3T5e1ee2e1e 94)Fie reeaua P temporizat i generalizat din figura,unde di reprezint durata asociat poziiei Pi. Pentru marcajul iniial reprezentat n figura de mai jos se cer: a)graful de marcaje accesibile;b)proprietile reelei. T1T2 3 3d3=1P3d2=1d1=1P2P1 Reele Petri 105 95)Construiigrafuldemarcajeiprecizaiproprietileurmtoarei Reele Petri: 96)Construiigrafuldemarcajeiprecizaiproprietileurmtoarei Reele Petri: P3 d3= 2 P4 d4= 2 P6 d6= 1 P2 d2= 1 P1 d1= 1 T1 T2T3 P5 d5= 1 T5T4 T6 Reele Petri 106 97)Sistemuldinfigurademaijosprelucreazdoutipuridepiese:A respectivB,preluatedindoudepozitedeintrarecucapacitate infinit.RobotulR1ncarcpieseledetipApemainaM1ipiesele detipBpemainaM2.DupprelucrareapemainaM1,respectivpe maina M2, piesele de tip A sunt transferate automat n bufferul B1 de capacitate 4, iar piesele de tip B sunt transferate automat n bufferul B2 de capacitate 6. Robotul R2 preia piese din bufferele B1 i B2 i ncarc maina M3 nti cu o pies de tip A i dup aceea cu dou piese de tip B (pe rnd).Astfel maina M3 realizeaz operaia de asamblare a unei piese A i a dou piese B n ordinea A+B+B. Dup asamblare piesele prsesc sistemul.Sepresupunecmainilepotprelucraosingurpieslaunmoment dat; de asemenea capacitatea de transfer a roboilor este de o pies. Se cunosc timpii de prelucrare pe cele trei maini: durata de prelucrare a uneipiesedetipApemainaM1ested1=3unitidetimp; prelucrarea unei piese de tip B pe maina M2 se face n d2 = 2 uniti detimp;iardurataoperaieideasamblarepemainaM3estedas=2 uniti de timp. Ssemodelezesistemuldeproducieastfelnctreeauasfie mrginit. S se identifice invarianii de marcaj.M1d1=3M2 d2=2R1ABB1 (4)B2(6)R2M31A+ 2Bd_as = 2Iesire din sistem Reele Petri 107 98)ConsidermexecuiadetipRound-Robinamaimultortaskuri. Aceastapresupune transferulcontrolului succesiv fiecruitask pentru execuiauneipriasa.Taskurilenexecuiepartajeazoaceeai unitatecentral,iarlafiecarecontrolfiecaretaskpoateexecutauna saumaimulteinstruciuni.SseconstruiascRPcaremodeleaz acest protocol, n urmtoarele cazuri : a)Seconsider4taskuri,fiecaretaskexecutndcteosingur instruciune cnd primete controlul; b)Seconsider2taskuri,taskul1executnd3instruciuni,iar taskul 2 executnd 5 instruciuni la primirea controlului.Indicaii:a)Pentru fiecare task se vor considera urmtoarele poziii:poziie ai care marcata semnifica taskul n ateptare;poziieexicaremarcatsemnificfaptulctaskuliesten execuie pentru o instruciune; poziiepicaredacestemarcatsemnificfaptulcs-adat controlul taskului i. b)Se utilizeaz o reea Petri generalizat. 99)Se consider un proces de producie simplu, coninnd un consumator i un productor cefolosesc mpreun un acelai stoc, acesta avnd o capacitatelimitatla3uniti.Productorulpoateproduceosingur pieslaunmomentdat,elputnddepunepiesanstocimediatcea terminat-odacstoculpermitedepunerea.Imediatdupdepunerea pieseiproductorulrencepeprocesuldeproducie.Consumatorulla rndulsu,imediatceaterminatdeconsumatopies(unasingur la un moment dat) ia o noua pies din stoc dac acesta nu este vid.S se modeleze cu RP funcionarea acestui proces. depunere retragereproduc tor stoc consumator Reele Petri 108 100)Fieunsistemdeproduciecareprelucreazunsingurtipdepiese conform fluxului tehnologic descris n figura de mai jos. La intrare n sistem,pieselesuntncrcatepepaletelepreluatedintr-unstocde capacitate3.RobotulR1ncarcpieselealternativpemainileM1i M2, M1 fiind ncrcat prima.Bufferele B1 (de capacitate 4) i B2 (de capacitate3)suntncrcateautomatcupiesedepemainileM1 respectivM2dendatceacesteaterminaoperaiadeprelucrare. Robotul R2ncarcmainaM3 prelundpieseattdin bufferulB1 ct idinbufferulB2.DupprelucrareapemainaM3pieseleprsesc sistemuliarpaletelesuntreciclatelaintrareasistemuluiidepusen stoculdepalete.tiindcfiecaremainpoateprelucraosingur pies la un moment dat (capacitate 1), s se construiasc reeaua Petri care modeleaz acest sistem de producie.R1M1 (1)B1 B2R2M2 (1)M3 (1)Stoc palete 101)Seconsiderunstoccepoateconineunnumrinfinitdepiese. Funcionareasaestesincronizatpedouevenimenteexterne: evenimentule1,sosireauneipieseievenimentule2,sosireaunei cereridepies.Ocereredepiesestesatisfcutimediatdacexist piese n stoc.Reele Petri 109 Modelai comportamentul stocului de piese printr-o reea Petri sincronizat i construii graful de marcaje accesibile pentru urmtoarele dou situaii: a)sepresupunecaocereredepiesnesatisfcut(nefiindpiesan stoc)estepierdut(utilizatorultrebuies-irennoiasc cererea); b)se presupune c o cerere de pies nesatisfcut estememorat, i satisfcut atunci cnd o nou pies sosete n stoc. stocsosirea uneicereri de piesasosirea uneipieseplecareapieselorsosireapieselore2e1 102)Patrufilosofi,f1f4,staunjuruluneimese,ntreeifiinddispuse bagheteleb1b4.Unfilosofsepoategsintr-unadinurmtoarele dou stri: poate gndi sau poate mnca. Pentru a manca un filosof are nevoiedeceledoubagheteaflatedeoparteidecealaltasa.n starea iniial toi filosofii gndesc i baghetele se afla pe mas. a)Descrieiprintr-oreeaPetriurmtorulprotocol:cndunfilosof dorete s mnnce el ia mai nti bagheta din dreapta sa, apoi pe ceadinstngasaincepesmnnce.Cndtermindemncat eldepunepemasmaintibaghetadinmanadreapt,apoipe ceadinmanastngitreceastfelnstareancaregndete. Indicaiinvarianiiminimalipentrureeauaconstruit.Este aceastareeaviabil?Dacexistunblocajgsiisecvenade validricareconducelaacestaidaioexplicaieaacestui blocaj. b)Definii un protocol astfel nct s nu mai poat aprea situaie de blocaj, i construii reeaua Petri corespunztoare. 103)Se consider dou bile de biliard, A i B, (figura de mai jos) care se deplaseazpeoaceeaidreapt,paralelcuunadinmargini.Fiecare bilaretreistri:deplasareladreapta,deplasarelastngasau ateptare(bilaoprit).Seceremodelareacomportamentuluicelor dou bile printr-o reea Petri, presupunnd c: a) atunci cnd lovete o Reele Petri 110 margineobilpornetensensinverscuaceeaiviteza;b)daccele doubileseciocnesc,ambelefiindnmicarecuaceeaivitez,ele repornescnsensinvers;c)dacobilopritestelovitdecealalt, primasepunenmicareiadouaseoprete.Presupunemcbilele realizeazomicareideal,frncetiniredatoratfrecrii.Sse studieze,nfunciedemarcajuliniialposibil,proprietilereelei construite, pe baza grafului de marcaje. AB 104)Seconsider6taskuriacrorexecutareestecondiionatde urmtoarelereguli:iniialtaskul1esteexecutabil;taskurile2i3nu potfiexecutatedectduptaskul1(nensemnndnscvorncepe simultan sau imediat dup terminarea taskului 1). Taskul 4 nu poate fi executat dect dup taskul 3, taskul 5 dup taskurile 2 i 4, iar taskul 6 duptaskurile4i5.Taskul1nupoatefireexecutatdectdup terminareataskului2,iartaskul3duptaskurile1i6.Considernd c execuia fiecrui task are o durata di s se modeleze prin reele Petri P - temporizate acest sistem. Care este momentul la care ncepe prima execuie a taskului 5 ? Indicaie.Pentrufiecaretaskseintroducdoupoziii:una corespunztoareexecuieitaskuluiiunacareasigurndeplinirea condiiei de execuie a taskului respectiv.105)Se consider o linie de asamblare cuprinznd dou maini fiecare cu cte un stoc n intrare, aacum se vede n figura de mai jos. Stocurile auocapacitatenelimitat.Sistemulprelucreazdoutipuridepiese, p1 i p2, care sosesc ntr-o ordine aleatoare n stocul 1 dar prelucrarea lor pe main fcndu-se prin alternana. Se presupune c mainile pot prelucra o singur piesa la un moment dat.Fie evenimentul ei sosirea unei piese de tip pi. O piesa de tipul 1 necesit oprelucrarede8unitidetimppemaina1ide3unitidetimppe maina2iaropiesadetipul2necesitcte5unitidetimppefiecare main.Reele Petri 111 a)Ssemodelezeacestsistemprintr-oreeasincronizati T-temporizat n condiiile enunate anterior; b)Cum se modific reeaua n ipoteza c stocul 1 conine permanent cel puin cte o pies de fiecare tip ?sosirepiesep1, p2stoc 2 stoc 1masina 2masina 1plecarepiesep1, p2 106) SsemodelezeprinintermediulreelelorPetricomportamentul uneipisiciialunuioarecenurmtorullabirint,tiindcmicrile pisicii sunt modelate de sgeile P iar cele ale oarecelui de sgeileS. S2S1P3P6S4PisicaSoarece42513P2P7 P4P5S3P1S6P8S5 107)Sserezolveproblemaculupul,capraivarzautilizndmodelul reelelor Petri. 108)Seconsiderunfluxdefabricaiecompusdindoumaini,fiecare avnd un stoc de piese n intrare. n sistem exist dou palete, piesele trecndntremainipurtatepepalete.Acestepaletesuntreciclabile, adic ele se ntorc n stocul 1 dup ce piesele pe care le-au purtat sunt terminatepemaina2.Maina1poatetrataosingurpieslaun momentdat, timpuldeservire fiindd1 = 2 uniti de timp, n timpce Reele Petri 112 maina2poatetratadoupiese,pentrufiecarefiindnecesared2 =3 uniti de timp.a)S se construiasc RP P-temporizat pentru acest sistem; b)S se construiasc graful de marcaje pentru reeaua P-temporizat considernd funcionarea cu vitez maxim. Care este durata unui ciclu de fabricaie? stoc 2d2=3d1=2 stoc 1masina 2masina 1 109)Fieunsistemdefabricaieflexibilcareprelucreazdoutipuride pieseAiB.Pieselesuntncrcatensistemdindoudepozitede intraredecapacitateinfinitDIA,DIBisuntprelucrateconform fluxurilordefabricaiedinfigurademaijoscuurmtoarele specificaii: PieseledetipAsuntprelucratepemainileM1,M2iM4,iar piesele de tip B pe mainile M1, M3 i M5;ncrcarea mainii M1 se face automat; Robotul R1 ncrca maina M2 cu piese de tip A i maina M3 cu piese de tip B; TransferulpieselordetipAdelamainaM2nstoculA(de capacitate 8) se face automat; piesele de tip B sunt transferate de asemen