Curs Compilatoare - Irina Athanasiu

Irina Athanasiu

10/4/2003

Limbaje formale si translatoare

1

INTRODUCERE - ORGANIZAREA UNUI COMPILATORAnaliza lexicala Analiza sintactic Analiza semantic Generarea de cod intermediar Optimizarea codului intermediar Generarea codului obiect Optimizarea codului obiect Gestiunea tabelei de simboli Detectarea erorilor

34 4 5 5 6 6 6 6 6

1. ELEMENTE DE TEORIA LIMBAJELOR FORMALE1.1. Gramatici Ierarhia Chomsky. Exerciii 1.1.1. Verificarea limbajului generat de ctre o gramatic 1.1.2. Transformri asupra gramaticilor independente de context a. Eliminarea ambiguitii b. Eliminarea - produciilor c. Eliminarea recursivitatii stnga d. Factorizare stnga e. Eliminarea simbolilor neterminali neutilizai g. Substituia de nceputuri(corner substitution) 1.1.3. Construcii dependente de context Exerciii 1.1.4. Propieti ale limbajelor independente de context 1.2. Mulimi regulate, expresii regulate.

78 9 10 11 12 13 16 17 19 20 21 23 24 25 26

1.3. Acceptoare 29 1.3.1. Automate finite 30 1.3.1.1. Construcia unui automat finit nedeterminist care accept limbajul descris de o expresie regulat dat 32 1.3.1.2. Conversia unui automat finit nedeterminist (AFN) ntr-un automat finit determinist(AFD)36 1.3.1.3. Construcia unui automat finit determinist care accept limbajul descris de o expresie regulat dat 39 1.3.1.4. Simularea unui automat finit determinist 45 1.3.1.5. Simularea unui automat finit nedeterminist 46 1.3.1.6. Probleme de implementare pentru automatele finite deterministe i nedeterministe 47 1.3.1.7. Minimizarea numrului de stari pentru AFD 48 1.3.2. Automate cu stiv(pushdown) 51 1.3.3 Maina Turing 60 1.3.3.1. Compunerea mainilor Turing 66 1.3.3.2. Extensii pentru maina Turing 70 1.3.3.3. Automate liniar mrginite 75 1.3.3.4. Relaia ntre maina Turing i gramatici 76 1.3.3.5. Elemente de calculabilitate 80 Maina Turing Universal 80 1.3.3.6. Maina Turing cu limit de timp 84

2. ANALIZA LEXICAL

871

Irina Athanasiu2.1. Interfaa analizorului lexical

10/4/2003


290 92

2.2. Un exemplu elementar de analizor lexical

3. ANALIZA SINTACTIC3.1. Analiza sintactica top - down 3.1.1. Analiza sintactica predictiva (descendent recursiva) 3.1.1.2. Gramatici LL(1) 3.1.1.3. Tratarea erorilor n analiza predictiv 3.1.2. Analiza sintactica bottom-up 3.1.2.1. Analiza sintactica de tip deplaseaza i reduce

101105 106 110 115 117 117

2

Irina Athanasiu

10/4/2003


3

Introducere - organizarea unui compilatorUn compilator este un program complex care realizeaz traducerea unui program surs ntr-un program obiect. De obicei programul surs este scris ntr-un limbaj de nivel superior celui n care este scris programul obiect. Structura general pentru un compilator este:program sursa | +-----------------+ | preprocesor | pas 1 +-----------------+ | pas 2 - - - - - - - | - - - - - - - - - - - - - - - - - - - - - - + | | | | +------------------+ +--------------------+ | | analiza lexicala |--------->| analiza sintactica | | | | 1, m > 1}. Acest limbaj realizeaz abstractizarea corespondenei ca numr ntre numrul de parametrii cu care au fost declarate procedurile i numrul de parametrii cu care se utilizeaz acestea. Nici acest limbaj nu pot fi descris de o gramatic independent de context. Pe de alt parte limbajul L2' = {anbn | n > 1}, poate s fie descris de gramatica : S a S b | a b. Deci i aici dup o prim recunoatere fcut n analiza sintactic, partea de dependen de context va fi rezolvat de ctre faza de analiz semantic. Observaie n general o gramatic independent de context poate s "numere" doi termeni dar nu trei sau mai muli. Dac pentru recunoaterea unui ir din limbaj se poate utiliza un algoritm care utilizeaz o singur stiv (sau un singur contor) atunci limbajul poate s fie descris de o gramatic independent de context. O gramatica regulata nu poate s "numere" dect pn la o limit finit.

Exerciii1. Fie gramatica:A BC | a. B CA | Ab, C AB | cC | b

S se construiasca gramatica echivalenta nerecursiva stnga 2. S se elimine simbolii neutilizai pentru gramatica:S A | B, A aB | bS | b, B AB | BA, C AS|b

3.

S se construiasc gramatica echivalenta fr -producii pentru gramatica: S ABC, A BB | , B CC | , C AA | b

4.

S se construiasc un algoritm care verific dac pentru o gramatic dat G, L(G) este mulimea vid. S se demonstreze c algoritmul este corect

24

Irina Athanasiu

10/4/2003


25

1.1.4. Propieti ale limbajelor independente de contextLimbajele formale sunt mulimi - putem s aplicm asupra lor operaii caracteristice mulimilor : reuniune, intersecie, diferen dar i operaii specifice cum este de exemplu concatenarea. Dac L1 i L2 sunt dou limbaje, concatenarea lor este un limbaj L = L1L2 astfel nct: L = { w | w = xy, x L1, y L2} O alt operaie specific ce se poate aplica asupra unui limbaj formal L este "Kleen star". Notaia utilizat pentru rezultat este L* i reprezint mulimea irurilor obinute prin concatenarea a zero sau mai multe iruri din L (concatenarea a zero iruri este irul vid, concatenarea unui singur ir este el nsui, etc). Se va utiliza i notaia L+ pentru LL*. Dac aplicnd o operaie asupra orcror doua limbaje independente de context obinem un limbaj independent de context vom spune c mulimea limbajlor independente de context este nchis sub operaia respectiv. Se poate demonstra c mulimea limbajelor independente de context este nchis sub operaiile: reuniune, concatenare i star. S demonstrm de exemplu nchiderea sub operaia de reuniune. Fie doua gramatici G1 = (N1, T1, P1, S1), G2 = (N2, T2, P2, S2). Putem ntotdeauna s presupunem c N1 N2 = eventual prin redenumirea simbolilor neterminali din una dintre gramatici). Gramatica corespunztoare limbajului reuniune a limbajelor generate de ctre cele doua gramatici se poate construi n modul urmtor:G = (N, T, P, S), N = N1 N2 {S}, T = T1 T2, P = P1 P2 {S S1 | S2}

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

Clasa limbajelor independente de context nu este inchis la operaiile de intersecie i complementare. S considerm de exemplu limbajele L1 = {anbncm | n,m 0}, L2 = {ambncn | n,m 0}. Limbajul L = L1 L2 este "cunoscut" ca find un limbaj dependent de context. S presupunem acum c pentru un limbaj independent de context generat de ctre gramatica G = (N, T, P, S), limbajul complementar, adica T* - L(G) este ntotdeauna independent de context. n acest caz, fie L un limbaj obinut prin intersecia a dou limbaje independente de context: L1 i L2. Se poate scrie: L = L1 L2 = T* - ((T* - L1) (T* - L2)). Dac mulimea limbajelor independente de context este nchis la operaia de complementare atunci (T* - L1) i (T* - L2) sunt limbaje independente de context i la fel este i reuniunea lor

25

Irina Athanasiu

10/4/2003


26

i la fel va fi i complementarea limbajului obinut prin reuniune. Adic ar rezulta c L1 L2 este un limbaj independent de context ceea ce deja tim c nu este adevarat. Dup cum s-a constatat acelai limbaj poate s fie descris de mai multe gramatici, eventual de tipuri diferite. Este util gsirea unui criteriu prin care s se indice tipul restrictiv al gramaticilor care pot s descrie un limbaj dat. De exemplu s considerm limbajul: { an * n| n > 1 } Se pune problema dac exist o gramatica independent de context care s-l genereze. Urmatorul rezultat ne d un criteriu cu ajutorul cruia putem s demonstrm c o gramatic nu este independent de context. Lema de pompare Fie L un limbaj independent de context. Atunci, exist o constanta k care este caracteristic limbajului astfel nct dac z L i |z| k, atunci z poate s fie scris sub forma z = uvwxy cu vx , |vwx| k , |w| 1 i pentru orice i, uviwxiy L. S utilizm rezultatul anterior pentru a studia limbajul: L= { an * n| n > 1 }

s presupunem c L este independent de context. Inseamn c exist un numr k (asociat limbajului) astfel nct dac n * n k atunci an x n = uvwxy astfel nct v i x nu sunt amndou iruri vide i |vwx| k. S presupunem ca n este chiar k ( k * k > k). Rezult ca uv2wx2yL. Deoarece |vwx| k rezult 1 |vx| < k deci lungimea irului iniial k x k < |uv2wx2y| < k x k + k. Dupa k x k urmtorul ptrat perfect este (k + 1) x (k + 1) care este mai mare deci k x k + k, adic |uv2wx2y| nu poate s fie un ptrat perfect, deci L nu poate s fie generat de o gramatic independent de context. Exerciii 1. S se arate c limbajul { anbncn | n > 1 } nu este independent de context 2. S se arate c limbajul { anbncj | n > 1, j < n } nu este independent de context

1.2. Mulimi regulate, expresii regulate.Fie T un alfabet finit. Se numete mulime regulat asupra alfabetului T mulimea construit recursiv n modul urmtor: 1. este o mulime regulat asupra alfabetului T; 2. Dac a T atunci {a} este o mulime regulat asupra alfabetului T; 3. Dac P i Q sunt mulimi regulate atunci PQ, PQ, P* sunt mulimi regulate asupra alfabetului T. 4. Nimic altceva nu este o mulime regulat. Se observ deci c o submulime a mulimii T* este o mulime regulat asupra alfabetului T dac i numai dac este mulimea vida, este o mulime care conine un singur simbol din T sau poate s fie obinut din aceste dou tipuri de mulimi utiliznd operaiile de reuniune (P Q), concatenare (PQ) sau nchidere P*. Descrierea mulimiilor regulate se poate face cu ajutorul expresiilor regulate. O expresie regulat este la rndul ei definit recursiv n modul urmtor (prin analogie cu definiia mulimiilor regulate) :

26

Irina Athanasiu

10/4/2003


27

1. este o expresie regulata care descrie mulimea ; 2. a T este o expresie regulat care descrie mulimea {a}; 3. dac p,q sunt expresii regulate care descriu mulimile P i Q atunci : a. (p + q) sau (p | q) este o expresie regulat care descrie mulimea P Q; b. (pq) este o expresie regulat care descrie mulimea PQ; c. (p)* este o expresie regulat care descrie mulimea P*. 4. nimic altceva nu este o expresie regulat. De exemplu expresia (0 | 1)* reprezint mulimea {0,1}*, expresia regulat : (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)* reprezint mulimea care conine toate irurile formate din 0 i 1 i care conin un numr par din fiecare simbol. n particular pp* este notat cu p+. ntre operatorii utilizai n descrierea mulimilor regulate exist o serie de relaii de preceden. Cea mai prioritar operaie este operaia de nchidere (notat cu *), urmeaz operaia de concatenare, cel mai puin prioritar este operaia + (|). De exemplu, expresia regulat (0 | (1(0)*)) poate s fie scrisa i sub forma 0 | 10*. Expresiile regulate au o serie de proprietai. Fie , , , expresii regulate. Spunem ca = dac i numai dac i descriu aceleai mulimi regulate. Sunt adevrate urmtoarele proprieti : 1. | = | 3. () = () 5. ( | ) = | 7. * = | * 9. | = 2. | ( |) = ( | ) | 4. ( |) = | 6. ? = ? = 8. (*)* = *

Utiliznd expresii regulate se pot construi i rezolva ecuaii avnd ca soluii expresii regulate. S considerm de exemplu ecuaia:X = aX + b

unde a,b i X sunt expresii regulate. Se poate verifica uor c X = a*b este o soluie a acestei ecuaii. Dac a este o expresie regulat care poate s genereze irul vid atunci soluia prezentat anterior nu este unic. S nlocuim n ecuaie pe X cu expresia regulat:a*(b + t)

Se obine:a*(b + t) = a[a*(b + t)] + b = = a+ b + a+ t + b = = (a+ + )b + a+t = a*b + a*t = a*(b + t)

Se numete punct fix al unei ecuaii cea mai mic soluie a ecuaiei respective. Propoziie Dac G este o gramatic regulat atunci L(G) este o mulime regulata. Demonstraia acestei teoreme se face prin construcie. Nu vom face demonstraia dar vom considera nite exemple, de construcii. Fie gramatica G = ({A, B, C}, {0,1}, P,A) cu P = {A

27

Irina Athanasiu

10/4/2003


28

1A | 0B, B 0B | 1C, C 0B| 1A| }. Se cere s se construiasc expresia regulat care genereaz acelai limbaj ca i G. Se pot scrie urmtoarele ecuaii: A = 1A + 0B B = 0B + 1C C = 0B + 1A + Din prima ecuaie se obine: A = 1*0B Din a doua ecuaie se obine: B = 0*1C Inlocuind n A se obine: A = 1*00*1C = 1*0+1C Inlocuind n a treia ecuaie se obine : C = 0+1C + 1+0+1C + C = ( + 1+)0+1C + = 1*0+1C C = (1*0+1)* Rezult: A = 1*0+1 (1*0+1)* A = (1*0+1)+ Mulimea regulat descrie irurile de 0 i 1 care se termin cu subirul 01. Evident o expresie mai simpl pentru descrierea aceluiai limbaj este: (0 | 1)*01 Se observ c se poate considera c limbajul se obine prin concatenarea a doua limbaje unul descris de expresia (0 | 1)* i cellalt descris de expresia 01. Rezult urmtoarea gramatic: S AB A 0A | 1A | B 01 Se observ c gramatica obinut nu este regulat. S transformm aceast gramatic prin substituie de nceputuri: S 0AB | 1AB | B A 0A | 1A | B 01 Se obine:

28

Irina Athanasiu

10/4/2003


29

S 0S | 1S |01 Utiliznd factorizarea: S 0X | 1S X S | 1 Din nou prin nlocuire de nceputuri se obine: X 0X | 1S |1 Aplicnd factorizarea: X 0X | 1Y YS| Rezult gramatica descris de produciile: S 0X | 1S X 0X | 1Y Y 0X | 1S | . Se observ c s-a ajuns la aceai gramatic cu cea iniial ( desigur dac redenumim neterminalele). Expresiile regulate reprezint o metod alternativ generativ pentru definirea limbajelor regulate. Limbajele definite de gramatici regulate sunt utilizate la nivelul analizei lexicale, n majoritatea limbajelor de programare modul de scriere al numelor i al identificatorilor pot s fie descrise de gramatici respectiv de expresii regulate. Construirea expresiilor regulate corespunztoare atomilor lexicali reprezint prima etapa n proiectarea unui analizor lexical.

1.3. AcceptoareUn acceptor este un dispozitiv format dintr-o band de intrare, o unitate de control i o memorie auxiliar.+--------------|a0|a1|...|an| +--------------\ cap de citire \ +---------+ | unitate | | de | | control | +---------+ | +-----------+ | memorie | | auxiliara | +-----------+

29

Irina Athanasiu

10/4/2003


30

Banda de intrare este formata din elemente n care se inscriu simbolii din irul de intrare. La un moment dat capul de citire este fixat pe un simbol. Funcionarea dispozitivului este dat de aciunile acestuia. ntr-o aciune capul de citire se poate deplasa la stnga sau la dreapta sau poate s rmn nemicat. n cadrul unei aciuni unitatea de control are acces la informaia din memoria auxiliar pe care o poate modifica. Se observ ca acest model este foarte general. Utiliznd diferite restricii asupra benzii de intrare, organizrii i accesului la memoria auxiliar se obin diferite cazuri particulare de acceptoare. O aciune a acceptorului este formata din : deplasarea capului de citire la stnga sau la dreapta sau meninerea capului de citire pe aceeai poziie i / sau; memorarea unei informaii n memoria auxiliar i / sau; modificarea strii unitaii de control.

Comportarea unui acceptor poate s fie descris n funcie de configuraiile acestuia. O configuraie este format din urmtoarele informaii : starea unitii de control; coninutul benzii de intrare i poziia capului de citire; coninutul memoriei.

Rezult c o aciune a acceptorului poate s fie precizat prin configuraia iniial (nainte de aciune) i cea final (dup execuia aciunii). Dac pentru o configuraie dat sunt posibile mai multe aciuni atunci spunem c acceptorul este nedeterminist altfel este determinist. Un acceptor are o configuraie iniial n care unitatea de control este ntr-o stare iniial, capul de citire este fixat pe simbolul cel mai din stnga al irului de intrare iar memoria are un coninut iniial specific. Acceptorul are o configuraie final pentru care capul de citire este situat pe simbolul cel mai din dreapta de pe banda de intrare. Se spune c dispozitivul a acceptat un ir de intrare w dac pornind din configuraia iniial ajunge n configuraia finala. Eventual, notiunea de acceptare poate s fie condiionata i de ajungerea ntr-o anumit stare a unitii de control sau de un anumit coninut al memoriei auxiliare. Evident dac acceptorul este nedeterminist dintr-o configuraie iniial pot avea loc mai multe evoluii. Dac exist ntre acestea una pentru care se ajunge la o configuraie final atunci se spune c dispozitivul a acceptat irul de intrare. Limbajul definit de ctre un acceptor este format din mulimea irurilor acceptate de ctre acesta. Pentru fiecare tip de gramatica din ierarhia Chomsky exist o clasa de acceptoare care definesc aceai clas de limbaje. Dintre acestea cele mai cunoscute (utilizate pentru implementarea compilatoarelor) sunt automatele finite care sunt acceptoare pentru limbaje regulate i automatele cu stiv (push-down), care sunt acceptoare pentru limbajele independente de context. Automatele finite sunt acceptoare fr memorie auxiliar iar automatele cu stiv sunt acceptoare pentru care accesul la memoria auxiliar se face conform unui mecanism de tip stiv.

1.3.1. Automate finiteUn automat finit este un obiect matematic AF = (Q, T, m, s0, F) unde :

30

Irina Athanasiu

10/4/2003


31

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

Dac pentru q Q, a T m(q,a) este definit, atunci m(q,a) se numete tranziie, dac a = atunci m(q,a) se numeste -tranziie. Se observ ca pentru o combinaie stare(q Q), intrare(a T) pot s corespund mai multe stri urmtoare, deci aa cum a fost definit, automatul este nedeterminist (AFN). Pentru reprezentarea unui automat finit se pot utiliza dou moduri de reprezentare, printr-o tabela de tranziie sau printr-un graf. S considerm de exemplu automatul care accepta limbajul definit de expresia (a | b)* abb. Poate s fie descris sub forma urmtoarei tabele : simbol de intrare stare 0 1 2 3 a {0, 1} b {0} {2} {3} +

Se observ c n fiecare intrare este specificat mulimea strilor urmtoare n care se trece pentru starea i simbolul corespunztor intrrii respective. Acelai automat finit poate s fie descris de urmtorul graf de tranziie :a --\/ +---+ +---+ +---+ +---+ start | | a | | b | | b |+-+| -------->| 0 |-->| 1 |-->| 2 |-->||3|| | | | | | | |+-+| +---+ +---+ +---+ +---+ /\ --b

Se observ c pentru fiecare stare exist cte un nod, ntre dou noduri exist un arc etichetat cu un simbol de intrare dac i numai dac se poate trece din starea reprezentat de primul nod n starea reprezentat de al doilea nod la aplicarea la intrare a simbolului cu care este etichetat arcul. De remarcat modul n care a fost specificat starea final. Se spune c un automat finit accept un ir de intrare dac exist o cale n graful de tranziie ntre nodul care reprezint starea de start i un nod care reprezint o stare final, astfel nct irul simbolilor care eticheteaza arcele care formeaz aceast cale este irul de intrare. De exemplu irul aabb este acceptat de automatul descris anterior, care va executa urmtoarele micri: a a b b 0 0 1 2 3 Se observa c pentru acelai ir de intrare exist i alte secvene de intrri care ns nu duc ntr-o stare de acceptare:

31

Irina Athanasiu

10/4/2003


32

a a b b 00000 Un caz particular al automatelor finite este dat de automatele finite deterministe (AFD). n cazul automatelor finite deterministe definiia funciei strii urmtoare se modific: m : S x T S.

Se observ c sunt satisfcute urmtoarele restricii: 1. nu exist -tranzitii; 2. pentru (q, a) Q x T este definit cel mult o tranziie. Se observ ca n acest caz, pentru un ir de intrare dat, n graful de tranziie exist cel mult o cale care pornete din starea de start i duce ntr-o stare de acceptare.

1.3.1.1. Construcia unui automat finit nedeterminist care accept limbajul descris de o expresie regulat datAlgoritmul pe care l vom prezenta utilizeaz direct structurile din definiia expresiilor regulate. Intrare O expresie regulat r asupra unui alfabet T Iesire Un automat finit nedeterminist (N) care accept limbajul L(r). Pentru construirea automatului se identific n structura expresiei r structurile care n mod recursiv compun expresia i se construiesc automatele finite nedeterministe (AFN) elementare corespunztoare. 1. Pentru expresia , automatul care accept limbajul+---+ +-----+ start | | |+---+| ------| i |------>|| f || | | |+---+| +---+ +-----+

corespunztor este :

2. Pentru expresia a, automatul care accept limbajul+---+ +-----+ start | | a |+---+| -------->| i |---->|| f || | | |+---+| +---+ +-----+

corespunztor este :

3. Fie dou expresii regulate r,t pentru care s-au construit automatele finite nedeterministe corespunztoare N(r) i N(t). a. pentru expresia regulat r|t limbajul corespunztor este acceptat de :

32

Irina Athanasiu

10/4/2003


33

33

Irina Athanasiu

10/4/2003


34

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

b. pentru expresia regulat rt limbajul corespunztor este acceptat de :---------------------------| | --------------+----------| | +---+ | +---+ | +-----+ | | | | N(r) | | | | N(t)|+---+| | --------->| i |--- -+> | |---- >|| f ||---| | | | | | | |+---+| | | +---+ | +---+ | +-----+ | | | | | --------------+----------| | | ----------------------------

Se observ ca n acest caz starea final a automatului corespunztor expresiei r coincide cu starea iniial a automatului corespunztor expresiei t. c. pentru expresia regulata r* limbajul corespunztor este acceptat de : +-| i |---------> | |--- --> | |------>|| f || | | | | | | | | |+---+| +---+ | +---+ +---+ | +-----+ | | | /\ | -------------------------| | | +---------------------------------------------+

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

34

Irina Athanasiu

10/4/2003


35

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

pentru fiecare b din expresie :+---+ +-----+ | | b |+---+| ------> | i |----> || f || | | |+---+| +---+ +-----+

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

n final se obine :

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

35

Irina Athanasiu

10/4/2003


36

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

1.3.1.2. Conversia unui automat finit nedeterminist (AFN) ntr-un automat finit determinist(AFD)Din exemplele anterioare s-a observat c un acelai limbaj reprezentat de expresia regulat (a | b)* abb poate s fie recunoscut de dou automate diferite - unul nedeterminist i unul determinist. Propoziie Pentru orice automat finit nedeterminist exist un automat finit determinist care accept acelai limbaj. Avnd n vedere aceast echivalen ntre cele dou automate se pune problema, cum se poate construi un automat determinist echivalent unui automat nedeterminist dat. n cele ce urmeaz vom considera c automatul finit nedeterminist a fost construit pornind de la o expresie regulat pe baza construciei prezentate n capitolul anterior. Algoritmul care construiete automatul determinist utilizeaz o metod de construire a submulimiilor unei mulimi date. Diferena ntre automatele deterministe i cele nedeterministe este dat de cardinalitatea funciei m. Automatul determinist se va construi calculnd n mod recursiv strile acestuia, simulnd n paralel toate evoluiile posibile pe care le poate parcurge automatul nedeterminist. Starea iniial a automatului finit determinist va corespunde mulimii strilor din automatul nedeterminist n care se poate ajunge pornind din starea iniiala s0 i utiliznd numai -tranzitii. Orice stare s' a automatului determinist corespunde unei submulimi Q' Q a automatului nedeterminist. Pentru aceasta stare i un simbol de intrare a T, m(s',a) = {s Q | ( q Q')(s = m(q,a))}. Rezult deci c n funcionarea AFD care simuleaz de fapt funcionarea AFN se urmresc simultan toate "cile" pe care poate evolua automatul finit nedeterminist. Algoritmul care construiete automatul finit determinist echivalent cu un automat nedeterminist dat utilizeaz dou funcii : -inchidere i move. Funcia -inchidere : P(Q) P(Q) determin pentru fiecare mulime Q' Q setul strilor n care se poate ajunge datorit -tranziiilor. Considernd o stare q a automatului finit determinist (AFD), aceasta reprezint de fapt o submulime Q' Q a automatului nedeterminist. Notm cu -nchidere(q) = -nchidere({s}) sQ' 36

Irina Athanasiu

10/4/2003


37

unde dac s S este o stare care nu are -tranziii atunci: -nchidere({s}) = {s} altfel -nchidere({s}) = -nchidere({s'}) s' m(s,) Construcia funciei -inchidere pentru o mulime Q' se poate face utiliznd urmtorul algoritm : A = Q', B = ct timp A \ B execut fie t A \ B B = B {t} pentru fiecare u Q astfel nct m(t,) = u executa A = A {u} -nchidere(Q') = A Funcia move : P(Q) x T P(Q) este utilizat pentru construcia strii urmtoare a automatului determinist. Astfel pentru o stare q a automatului determinist, cruia i corespunde o mulime Q' Q, i o intrare a T, move(q,a) = m(s,a) sQ' Construcia automatului determinist se face prin construcia unei tabele de tranziii tranz_AFD i a unei mulimi de stri stari_AFD. stari_AFD = {-inchidere({s0})} A= ct timp stari_AFD \ A executa fie t stari_AFD \ A A = A {t} pentru fiecare a T executa B = -inchidere(move(t,a)) stari_AFD = stari_AFD {B} tranz_AFD[t,a] = B

Fie automatul nedeterminist : ---------------+ / |

37

Irina Athanasiu/

10/4/2003


38

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

Se observ c -inchidere(0) = {0, 1, 2, 4, 7}, -inchidere(move({0,1,2,4,7}),a)) = -inchidere({3,8}) = {1,2,3,4,6,7,8}. Dac q1 = {0,1,2,4,7}, q2 = {1,2,3,4,6,7,8} atunci tran_AFD(q1,a) = q2. Continund se obine urmtoarea tabel de tranziie :stare | intrare | multime corespunzatoare AFN |a |b | -----------+----+----+-------------------------------------q1 | q2 | q3 | {0,1,2,4,7} -inchidere({0}) -----------+----+----+-------------------------------------q2 | q2 | q4 | {1,2,3,4,6,7,8} -inchidere({3,8}) -----------+----+----+-------------------------------------q3 | q2 | q3 | {1,2,4,5,6,7} -inchidere({5}) -----------+----+----+-------------------------------------q4 | q2 | q5 | {1,2,4,5,6,7,9} -inchidere({5,9}) -----------+----+----+-------------------------------------q5 | q2 | q3 | {1,2,4,5,6,7,10} -inchidere({5,10}) ------------------------------------------------------------

Graful automatului finit determinist care a rezultat este :

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

+---+ | | | 4 |-> | | +---+

+---+ | | | 5 |-> | | +---+

+-----+ |+---+| || 6 || |+---+| +-----+

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

+---+ +---+ +-----+ | | b | | # |+---+| | 4 |->| 5 |->|| 6 || | | | | |+---+| +---+ +---+ +-----+

Mai interesant ns este faptul c funcia followpos poate s fie utilizat pentru construirea unui automat determinist utiliznd un algoritm similar celui pentru construirea submulimilor.stari_AFD = { first_pos(radacina) } # multime de multimi de coduri A= cat timp stari_AFD \ A executa fie t stari_AFD \ A # multime de coduri A = A {t} pentru fiecare a T executa X = { followpos(p) | r(p) = a} pt daca X atunci stari_AFD = stari_AFD {X}

43

Irina Athanasiu

10/4/2003tranz_AFD(t,a) = X


44

n algoritm firstpos(rdcina) este valoarea funciei firstpos aplicat nodului rdcin, r(c) este simbolul de intrare care n expresia regulata reprezentat de arbore are codul c. Se observ ca firstpos(rdcina) corespunde cu -inchidere(s0) iar followpos(p) reprezint -inchidere(move(...)). Aplicnd acest algoritm i rezultatele anterioare se obine automatul finit determinist reprezentat de urmtorul graf :b b --------- | 2,| a | 2,| b | 2,| b ||1,2,|| | 3 |--->| 3,|---->| 3,|---->||3,6 || +---+ |4| |5| |+----+| +---+ +---+ +------+ /\ || a | | -- |+-| 1 |> | 2 |> ||3|| | | | | | | |+-+| +---+ +---+ +---+ +---+ | | /\ -- | | | | a | +-----+ | | a | +---------------+ a

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

45

Irina Athanasiu

10/4/2003


46

1.3.1.5. Simularea unui automat finit nedeterministPrezentm n continuare un algoritm pentru simularea unui automat finit nedeterminist. Algoritmul citete un ir de intrare i verific dac automatul l accepta sau nu. Se consider c automatul a fost construit pornind de la expresia regulat utiliznd prima construcie. n consecin automatul va satisface urmtoarele proprietai : 1. are cel mult de dou ori mai multe stri fa de numrul de simboli i operatori care apar n expresia regulat; 2. are o singur stare de start i o singur stare de acceptare. Dintr-o stare de acceptare nu pleac nici o tranziie; 3. din fiecare stare pleac fie o tranziie pentru un simbol din alfabetul de intrare T, fie o tranziie sau doua -tranziii. Intrare un AFN (N) i un ir de intrare x. irul se termin cu un simbol special eof. Automatul N are o stare iniial s0 i o mulime de stari de acceptare (finale) F. Ieire. Rspuns "DA" dac N accept x, respectiv "NU" dac N nu accept x. Algoritmul de simulare se aseamn cu cel utilizat pentru construcia unui automat finit determinist echivalent cu automatul N, diferenele constau n faptul c pentru fiecare mulime de stri Q n care poate s ajunga automatul pentru un prefix al irului x se consider pentru construirea mulimii Q' de stri urmtoare numai simbolul curent din irul x. n momentul n care s-a ajuns la sfritul irului (s-a ajuns la eof) dac n setul strilor curente este inclus i o stare de acceptare (final), atunci rspunsul este "DA" altfel rspunsul este "NU".S= a= cat S -inchidere({s0}) # -inchidere(S) = {s' Q | s S, s' m(s,)} S caracterul_urmtor timp a eof executa = -inchidere(move(S,a)) # move(S,a) = m(s',a) s' S a = caracterul_urmtor

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

Algoritmul poate s fie implementat eficient utiliznd dou liste i un vector indexat cu strile automatului finit nedeterminist. ntr-o list se pstreaz setul strilor curente ale automatului, n cealalt setul strilor urmtoare. Utiliznd algoritmul de calcul al starilor urmtoare pentru -tranziii se calculeaz setul -nchidere pentru o stare dat. Vectorul este utilizat pentru a asigura funcionarea listei ca o mulime n sensul c dac o stare este coninuta n list atunci ea nu trebuie s mai poat fi adaugat. Dup ce s-a terminat calculul -inchiderii pentru o stare se face schimbarea rolului celor dou liste. Deoarece fiecare stare are cel mult dou tranziii, fiecare stare poate s produc cel mult dou stri noi. Fie |N| numrul de stri pentru AFN. Deoarece n lista pot s fie memorate maximum |N| stri, calculul strii urmtoare se poate face ntr-un timp proporional |N|. Deci timpul necesar pentru simularea AFN pentru irul de intrare x va fi proportional cu |N| x |x|. S relum de exemplu automatul :

46

Irina Athanasiu

10/4/2003


47

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

Acest AFN accept expresia regulata (a|b)*abb. S considerm de exemplu irul de intrare x = ab. Evoluia celor dou liste va fi urmtoarea :

lista 1 a ---------> -i({0}) = {0,1,2,4,7}

lista 2

-i({3,8}) = {1,2,3,4,6,7,8}

b 1, se parcurg simbolii de intrare. Dac pentru un simbol a i strile q1, q2 A, m(q1, a) i m(q2, a) fac parte din elemente diferite din P nseamn c strile succesoare strilor q1 i q2 nu fac parte din aceeai mulime a partiiei. Corespunztor Q va fi mprit n 4 mulimi, etc. Algoritmul corespunztor este: Intrare Un automat finit determinist (Q, T, m, s0, F) Ieire Mulimea mulimilor de stari echivalente din AFD. Descrierea algoritmului este:P = {F, Q - F, {d}} repeta P' = P repeta alege A P, Q ne marcat si marcheaza A new = daca |A| > 1 atunci alege first A A' = A - {first} cat timp A' executa alege next A' A' = A' - {next} se_imparte = false T' = T cat timp T' si nu se_imparte executa alege a T' T' = T' - {a} goto_first = tranz_AFD[first,a] goto_next = tranz_AFD[next, a] daca goto_next si goto_first sunt n elemente (multimi) diferite din P atunci new = new {next} se_imparte = true

daca new atunci P = P - {A} A = A - new P = P {A}{new} pana nu mai exist A P ne marcat pana P = P'

49

Irina Athanasiu

10/4/2003


50

Algoritmul utilizat nu este optim din punct de vedere al timpului de execuie. La fiecare pas mulimea de stri Q se mparte n cel mult dou noi mulimi : new i Q \ new. Exist algoritmi pentru care numrul de operaii este proporional cu n log n. S considerm urmtorul exemplu :b --\/ +---+ | | b b > | 2 | | 1 |---->| 3 |--->|| 4 || +---+ | | | | |+----+| +---+ +---+ +------+ /\ || a | | -- |+- 0}. P = ({q0, q1 ,q2}, {0,1}, {z, 0}, m, q0, z,{q0}) undem(q0,0,z) m(q1,0,0) m(q1,1,0) m(q2,1,0) m(q2,,z) = = = = = {(q1,0z)} {(q1,00)} {(q2,)} {(q2,)} {(q0,z)}

Pentru toate celelalte elemente (s, a, z) Q x (T {}) x Z care nu sunt descrise de regulile de mai sus, m(s, a, z) = . Se observ c automatul copiaz toate zerourile de pe banda de intrare n stiv i apoi descarc stiva pentru fiecare simbol 1 ntlnit la intrare. De exemplu pentru irul 0011, automatul va executa urmtoarea secven de tranziii :(q0,0011,z) |||||(q1,011,0z) (q1,11,00z) (q2,1,0z) (q2,,z) (q0,,z)

Pentru irul de intrare 011 care nu aparine limbajului evoluia va fi :(q0,011,z) ||||(q1,11,0z) (q2,1,z) (q2,1,z) (q0,1,z)

Se observ c dei s-a ajuns ntr-o stare final nu s-a ajuns la sfritul irului de intrare deci irul nu a fost acceptat. Pentru irul de intrare 001, evoluia este :(q0,001,z) |- (q1,01,0z) |- (q1,1,00z) |- (q2,,0z)

n acest caz s-a ajuns la sfritul irului dar starea n care se gseste automatul nu este final deci nici acest ir nu este acceptat.

52

Irina Athanasiu

10/4/2003


53

Pentru a demonstra c L(P) = {0n1n} trebuie s aratm c {0n1n} L(P) i L(P) {0n1n}. Se pot face urmtoarele observaii :(q0,0,z) |- (q1,,0z) (q1,0i,0z) |-i (q1,,0i+1z) (q1,1,0i+1z) |- (q2,,0iz) (q2,1i,0iz) |-i (q2,,z) (q2,,z) |- (q0,,z)

Rezult c pentru irul 0n1n, n > 1 se obine :(q0,0n1n,z) |-2n+1 (q0, , z), n > 1 (q0,,z) |-0(q0,,z)

Deci {0n1n} L(P). Trebuie s artm c i L(P) {0n1n} . Se observ c pentru a accepta un ir, P trece n mod obligatoriu prin succesiunea de stri q0, q1, q2, q0 dac n > 0. Dac (q0, w, z) |-i (q1, , ), i > 1 nseamn ca w = 0i i = 0iz. Dac (q2, w, ) |-i (q2, , ) nseamn c w = 1i i a = 0i. Dac (q1, w, ) |- (q2, , ) nseamn c w = 1 i a = 0 Dac (q2, w ,z) |-* (q0, , z) nseamn c w = . Deci dac (q0, w, z) |-i (q0, , z) atunci fie w = i i = 0 fie w = 0n1n, i = 2 n + 1. Deci L(P) {0n1n} . S considerm i automatul care accept limbajul L = {wwR|w {a,b}+}, P = ({q0, q1, q2}, {a, b}, {z, a, b}, m,q0, z, {q2}) unde :m(q0,a,z) m(q0,b,z) m(q0,a,a) m(q0,a,b) m(q0,b,a) m(q0,b,b) m(q1,a,a) m(q1,b,b) m(q1,,z) = = = = = = = = = {(q0,az)} {(q0,bz)} {(q0,aa),(q1,)} {(q0,ab)} {(q0,ba)} {(q0,bb),(q1,)} {(q1,)} {(q1,)} {(q2,)}

Funcionarea automatului pentru recunoaterea unui ir parcurge trei etape. n prima etap se copiaz n stiv irul w, apoi stiva se descarc pentru wR. Ultima etap recunoate sfritul irului de intrare n condiiile descrcrii complete a stivei. Prima etap este caracterizat de starea q0, urmtoarea de q1, q2 fiind starea final. n prima etap dac simbolul curent de pe banda de intrare nu coincide cu simbolul din vrful stivei atunci nu s-a ajuns la sfritul irului w i deci simbolul aflat sub capul de citire este copiat n vrful stivei. Dac ns simbolul curent de pe banda de intrare coincide cu simbolul din vrful stivei atunci fie s-a ajuns la sfritul irului w i ncepe wR i deci trebuies nceap descrcarea stivei fie nu s-a ajuns la sfritul irului w i atunci simbolul aflat sub capul de citire trebuie s fie copiat n vrful stivei. Din cele prezentate anterior rezult caracterul nedeterminist al automatului. S considerm de exemplu secvena de miscri pentru irul abba.

53

Irina Athanasiu(1) (q0,abba,z) ||||-

10/4/2003(q0,bba,az) (q0,ba,baz) (q0,a,bbaz) (q0,,abbaz)


54

Se observ c pentru aceast secven de tranziii nu se ajunge ntr-o stare final. Automatul fiind nedeterminist trebuie s cercetm ns toate secvenele de tranziii posibile. O alt secven este:(2) (q0,abba,z) |||||(q0,bba,az) (q0,ba,baz) (q1,a,az) (q1,,z) (q2,,)

Rezult ca automatul ajunge n starea q2 deci accept irul abba. Fie P = (Q, T, Z, m, q0, z0, F) un automat pushdown. Spunem c un ir w T* este acceptat de P prin stiva goal dac (q0, w, z0) |-+ (q, , ) pentru q Q. Fie Le(P) mulimea irurilor acceptate de P prin stiva goal. Se poate demonstra urmtorul rezultat. Dac L(P) este limbajul acceptat de automatul P prin stri finale atunci se poate construi un automat pushdown P' astfel nct L(P) = Le(P'). Automatul P' va simula funcionarea automatului P. Ori de cte ori P intr ntr-o stare final, P' poate continua simularea sau intr ntr-o stare speciala qe n care golete stiva (qe Q). Se poate ns observa c P poate s execute o secven de micri pentru un ir de intrare w care s permit golirea stivei fr ca irul s fie acceptat de ctre automatul P (pentru P nu conteaz dect ajungerea ntr-o stare final). Pentru a evita astfel de situaii se consider un simbol special pentru iniializarea stivei, simbol care nu poate s fie scos din stiva dect n starea qe. Fie P' = (Q {qe, q'}, T, Z {z'}, m', q', z', ) unde funcia m' este definit n modul urmtor : 1. dac (r, t) m(q, a, z) atunci (r, t) m'(q, a, z), pentru r, q Q, t Z*, a T {}, z Z. 2. m'(q', , z') = {(q0, z0z')}. P' i iniializeaz stiva cu z0z' (z' reprezint simbolul de iniializare al stivei pentru P'). 3. pentru q F i z Z, (qe, ) m'(q, , z); 4. pentru z Z {z'}, m'(qe, , z) = {(qe, )} Se observ c :(q',w,z') |- (q0,w,z0z') |-n (q, , y1 y2 ... yr) |- (qe, , y2 ... yr) |-r-1 (qe, , )

cu yr = z' dac i numai dac (q0, w, z0) |-n (q, , y1 y2 ... yr-1) pentru q F i y1 y2 ... yr-1 Z*. Deci Le(P') = L(P). Se poate demonstra i rezultatul invers, adic dndu-se un automat push down i limbajul acceptat de acesta prin stiva goal se poate construi un automat push down care accept acelai limbaj prin stri finale. Limbajele acceptate de automatele pushdown sunt limbajele care pot s fie descrise de gramatici independente de context. Dndu-se o gramatic independent de context s 54

Irina Athanasiu

10/4/2003


55

construim automatul care accept limbajul generat de aceasta gramatica. Fie G = (N, T, P, S), se obine automatul pushdown R = ({q}, T, N T, m, q, S, ) unde m este construit conform urmtoarelor reguli : 1. dac A P atunci (q, ) m(q, , A) 2. m(q, a, a) = {(q, )} pentru orice a T. Se observ c automatul astfel construit va accepta limbajul prin stiv goal. Se poate arata c A k w dac i numai dac (q,w,A) |-n (q, , ) k, n > 1. Altfel spus exist o derivare S + w dac i numai dac (q, w, S) |-+ (q, , ). Rezult deci c L(G) = L(R). S construim de exemplu automatul care recunoate gramatica expresiilor aritmetice G = ({, T, F}, {a, +, (, )}, P, ) unde P = { + T | T, T T * F | F, F () | a}. Aplicnd construcia propus rezult R = ({q}, {a, +, *, (, )},{, T, F, a, +, *, (, )}, m, q, , ) unde m este definit n modul urmtor :m(q, m(q, m(q, m(q, , , , b, ) T) F) b) = = = = {(q, {(q, {(q, {(q, + T),(q, T)} T * F),(q, F)} ()),(q, a)} )} cu b {a,+,*,(,)}.

S considerm de exemplu o succesiune de configuraii pentru a + a * a.(q, a + a * a, ) |||||||||||||(q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, a + a * a, a + a * a, a + a * a, a + a * a, + a * a, + a * a, T) a * a, T * a * a, F * a * a, a * * a, * F) a, F) a, a) , ). + T+ F+ a+ T) F) F) F) T) T) T) T)

n reprezentarea tranziiilor vrful stivei a fost reprezentat n stnga. Se observ c secvena de tranziii considerat, simuleaz urmtoarea secven de derivri de forme propoziionale :+TT+TF+Ta+Ta+T*F a + F * F a + a * F a + a * a.

Se observ ca n aceasta secven s-a nlocuit ntotdeauna cel mai din stnga neterminal. Din acest motiv se spune c am utilizat o derivare stnga. Secvena de derivri anterioare poate s fie reprezentat de urmtorul arbore de derivare.

55

Irina Athanasiu

10/4/2003 /|\ /|\ + T | /|\ | /|\ T T * F | | | | | | F F a | | a a


56

Acest gen de construire de secvente de derivare i deci automatele pushdown care accept limbaje prin stiv goal sunt utilizate n analiza sintactic top down (descendent recursiv). Un tip special de automat cu stiv l reprezint automatul pushdown extins = (Q, T, Z, m, q0, z0, F) pentru care m : Q x (T {}) x Z* P(Q x Z*). Se observ c n acest caz din stiv se consider nu numai simbolul din vrful stivei ci un ir de simboli plasat n vrful stivei. Considerm pentru acest tip de automat c acceptarea se face prin stari finale ( i n acest caz se poate construi un automat echivalent care s faca acceptarea prin stiv goal). S considerm de exemplu automatul care accept limbajul L = {wwR | w {a,b}*}. Fie P = ({q, p}, {a, b}, {a,b,S,z}, m, q, z, {p}) unde funcia m este definit n modul urmtor :m(q,a,) = {(q,a)} m(q,b,) = {(q,b)} m(q,,) = {(q,S)} m(q,,aSa) = {(q,S)} m(q,,bSb) = {(q,S)} m(q,,Sz) = {(p,)}

De exemplu pentru secvena de intrare aabbaa este posibil urmtoarea secven de tranziii :(q, aabbaa, z) |||||||||||(q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (p, abbaa, az) bbaa, aaz) baa, baaz) baa, Sbaaz) aa, bSbaaz) aa, Saaz) a, aSaaz) a, Saz) , aSaz) , Sz) , )

Se observ ca datorit tranziiei m(q, , ) = {(q, S)} automatul este nedeterminist. Se poate demonstra c pentru orice automat pushdown extins , exist un automat pushdown P astfel nct L() = L(P). S revenim la problema acceptrii limbajelor independente de context de ctre automate pushdown i s considerm din nou exemplul expresiilor aritmetice. Pentru generarea irului a + a * a putem s considerm i urmtoarea secven de derivari : +T+T*F+T*a+F*a + a * a T + a * a F + a * a a + a * a. 56

Irina Athanasiu

10/4/2003


57

Se observ ca n aceast secven s-a nlocuit ntotdeauna cel mai din dreapta neterminal. Din acest motiv se spune ca s-a construit o derivare dreapta. Considernd acest tip de derivri i parcurgndu-le n ordine invers (de la sfrit) se poate introduce noiunea de reducere stnga. Fie gramatica G = (N,T,P,S) o gramatic independent de context s presupunem c S * aAw aw * xw. Dac n fiecare derivare a fost nlocuit de fiecare dat neterminalul cel mai din dreapta atunci se spune c aw se reduce stnga la aAw dac A P. Dac este cel mai din stnga astfel de ir atunci spunem ca este nceputul irului aw. Deci un capt (handle) pentru o derivare dreapta este orice ir care este partea dreapta a unei producii i poate s fie nlocuit de neterminalul corespunztor ntr-o form propoziional care a aprut dintr-o derivare dreapta obinndu-se forma propoziional anterioar din derivarea dreapta. S considerm de exemplu gramatica: G = ({S, A, B},{a, b, c, d}, {S Ac | Bd, A aAb | ab, B aBbb | abb}, S). Aceast gramatic genereaz limbajul {anbnc | n > 1} {anb2nd | n > 1}. S considerm urmtoarea secven de derivari S Bd aBbbd aabbbbd. Pentru irul obinut abb este capt deoarece aBbbd este o form propoziional anterioar din derivarea dreapta, n timp ce ab nu este deoarece aAbbbd nu este o forma propoziional care poate s apar ntr-o derivare dreapta. Relund din nou gramatica pentru expresii aritmetice i secvena de derivri dreapta : +T+T*F+T*a+F*a + a * a T + a * a F + a * a a + a * a. Rezult arborele de derivare : /|\ /|\ + T | /|\ | /|\ T T * F | | | | | | F F a | | | | a a

Dac analizm acest arbore se vede c a (care reprezint frunza celui mai din stnga subarbore) este un nceput, dac se face o reducere se obine arborele :

57

Irina Athanasiu

10/4/2003 /|\ /|\ + T | /|\ | /|\ T T * F | | | | | | F F a | | a


58

Continund se ajunge la : /|\ /|\ + T /|\ /|\ T * F | | F a | a

Urmtorul capt este a, etc. Se observ c pentru a identifica un capt pentru o form propoziional obinut printro derivare dreapta se consider secvena frunzelor celui mai din stnga subarbore de adincime 1 (toate nodurile acestuia sunt fie frunze fie noduri din care se deriveaz frunze). De exemplu :| | | a sau F sau T sau T /|\ / | \ T * F

pentru care a, F, T respectiv T * F reprezint pri dreapta ale unor producii. Aceasta metoda de reducere a arborilor de derivare se numete "handle pruning". Dndu-se o gramatic independent de context G = (N, T, P, S) se poate construi un automat pushdown extins care s opereze conform metodei "handle pruning" n modul urmtor : R = ({q, r},T,N T {$}, m, q, $, {r}) unde: 1. dac A P atunci (q, A) m(q, , ) 2. m(q, a, ) = {(q, a)} pentru orice a T. Se observ c simbolii a T sunt copiai n stiva; 3. m(q, , $S) = {(r, )}. S construim utiliznd aceast tehnic automatul pushdown extins care accept gramatica expresiilor aritmetice : R = ({q, r},{a, +, *, (, )},{a, +, *, (, ), T, F, , $}, m, q, $,{r}) unde

58

Irina Athanasium(q, m(q, m(q, m(q, m(q, m(q, m(q, m(q, b, , , , , , , ,

10/4/2003


59

) = {(q, b)}, pentru b {a, +, *, (, )} + T) = {(q, )} T) = {(q, )} T * F) = {(q, T)} F) = {(q, T)} ()) = {(q, F)} a) = {(q, F)} $) = {(r, )}

Find vorba de o derivare dreapta, vrful stivei a fost figurat n dreapta. Se observ c aceast secven de tranziii este unica secven ce duce la acceptarea irului de intrare. Pentru irul a + a * a, automatul R va executa urmtoarele tranziii :(q, a + a * a, $) ||||||||||||||(q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, (q, + a * a, $a) + a * a, $F) + a * a, $T) + a * a, $) a * a, $ +) * a, $ + a) * a, $ + F) * a, $ + T) a, $ + T *) , $ + T * a) , $ + T * F) , $ + T) , $) , ?)

Automatele push down construite dup modelul prezentat anterior vor fi utilizate n analiza sintactic de tip bottom-up. Un automat push down este determinist dac pentru orice configuraie exist cel mult o singur tranziie urmtoare. Mai precis un automat push down PD = (Q, T, Z, m, q0, z0, F) este determinist dac pentru orice (q, a, z) x (T {}) x Z sunt ndeplinite urmtoarele condiii: 1. |m(q, a, z)| 1, 2. dac m(q, , z) atunci m(q, a, z) = pentru a T Avnd n vedere echivalena dintre un automat push down i limbajele independente de context, vom spune c un limbaj independent de context este determinist dac este acceptat de un automat push down determinist. Vom modifica puin condiia de acceptare, considernd c un limbaj independent de context este determinist dac exist un automat pushdown determinist care accept limbajul L$. Simbolul $ este un simbol care nu apare n alfabetul peste care este definit limbajul L. Se observ c utilizarea acestui simbol care apare concatenat cu fiecare ir din L indic de fapt posibilitatea automatului push down de a recunoate sfritul irului. n acest mod se extinde puin clasa limbajelor independente de context deterministe. Se pune intrebarea dac orice limbaj independent de context este determinist. S considerm de exemplu limbajul : L = {wwR | w {a, b, c}

59

Irina Athanasiu

10/4/2003


60

Evident un automat push down care accept acest limbaj trebuie s ghiceasc unde este mijlocul irului pentru ca s nceap descrcarea stivei. Intutitiv, o astfel de operaie nu se poate realiza cu un dispozitiv determinist. Propoziie. Clasa limbajelor acceptate de automate push down nedeterministe este mai larg dect clasa limbajelor acceptate de automate push down deterministe.

1.3.3 Maina TuringO main Turing este un acceptor care "tie" s scrie pe banda de intrare. n acest mod banda de intrare devine memorie auxiliar. Maina Turing a fost definit de ctre matematicianul englez Alan Turing (1912 - 1954) n anul 1930. Cnd a inventat maina care i poart numele, Turing era interesat nu de calculatoare ci de posibilitatea specificri i rezolvri problemelor matematice utiliznd mijloace automate. Adic, poate s fie rezolvat orice problema matematic utiliznd nite reguli elementare de prelucrare a irurilor ?. Structura unei maini Turing este:+---------------------------| +---------------------------

banda de intrare

| cap de citire / scriere | +---------+ | unitate | | de | | control | +---------+

Unitatea de control comand execuia micrilor. O micare este format din : stabilirea strii urmtoare pentru unitatea de control; scrierea unui simbol pe banda de intrare sau execuia unei deplasri cu o poziie spre stnga sau spre dreapta.

Banda de intrare este marginit la stnga i infinit la dreapta. Dup poziia ocupat de irul de intrare pe banda aceasta conine blancuri. n cele ce urmeaz vom indica simbolul blanc cu ajutorul caracterului # (presupunnd c acest simbol nu face parte din alfabetul limajului pentru care se construiete maina). De asemenea vom utiliza caracterele L i respectiv R pentru a indica o deplasare la stnga respectiv la dreapta. Maina Turing poate s scrie pe banda de intrare, deci poate s scrie att informaii intermediare ct i un rspuns nainte de a se oprii. Maina Turing are o stare special numit stare de oprire (de halt) pe care o vom nota n continuare cu h. Acceptarea sau neacceptarea unui ir este indicat de coninutul benzii cnd se ajunge n starea de oprire. S considerm o definiie formal a noiunii de main Turing. Se numete main Turing obiectul matematic : MT = (Q, T, m, q0) unde Q este o mulime finit a strilor mainii Turing, h Q; 60

Irina Athanasiu

10/4/2003


61

T este alfabetul finit de intrare care conine simbolul # dar nu conine simbolii L i R; m este funcia de tranziie m : Q x T (Q {h}) x (T {L, R}).

q0 Q este starea iniial a mainii Turing;

Dac q Q, a T i m(q, a) = (p, b) nseamn c fiind n starea q, avnd a sub capul de citire maina trece n starea p. Dac b T atunci simbolul a va fi inlocuit cu b, altfel capul se va deplasa cu o poziie la stnga sau la dreapta n funcie de valoarea simbolului b {L, R}. Se observ c maina Turing a fost definit ca un acceptor determinist. ncetarea funcionrii mainii Turing se face dac se ajunge n starea h (cnd maina se oprete) sau dac se ncearc deplasarea la stnga dincolo de captul din stnga al benzii. n acest ultim caz se spune ca maina s-a agat (a ajuns ntr-o stare de agare - hanging state). Definiia anterioar corespunde maiii Turing standard. Fa de aceast definiie exist diferite variante. S considerm un exemplu de main Turing MT = ({q0, q1}, {a, #}, m, q0), unde:m(q0, m(q0, m(q1, m(q1, a) #) a) #) = = = = (q1, (h, (q0, (q0, #) #) a) R)

S considerm c pe banda de intrare se gsete irul aaa i c poziia capului este pe primul caracter din ir. Se observ c pentru aceast stare iniial, primul simbol a este nlocuit cu #, noua stare find q1. Pentru q1, dac sub capul de citire se gsete un caracter # atunci se va face o deplasare la dreapta starea devenind q0. Se continu evoluia ntr-o manier similar pn cnd n starea q0 capul de citire se gasete pe un caracter #. n acest moment se trece n starea h i maina se oprete. Rezult ca evoluia mainii duce la tergerea unui ir de a-uri nscris pe banda de intrare. S considerm i urmtorul exemplu MT = ({q0}, {a, #}, m, q0), undem(q0, a) = (q0, L) m(q0, #) = (h, #)

n acest caz maina caut primul simbol # la stnga poziiei din care pleac capul de citire / scriere. La gsirea acestui simbol se trece n starea h. Dac nu exist un astfel de simbol maina nceteaz s funcioneze cnd ajunge la captul din stnga al benzii. O configuraie pentru o main Turing este un element din mulimea : (Q {h}) x T* x T x (T* (T - {#}) {}) Elementele unei configuraii sunt: starea curent q (Q {h}) irul aflat pe banda de intrare la stnga capului de citire / scriere (a T*) simbolul aflat sub capul de citire / scriere ( i T) irul aflat la dreapta capului de citire / scriere ( (T* (T - {#}) {})). Se observ c, deoarece irul de intrare este finit, n timp ce banda de intrare este infinit la dreapta putem s considerm ntotdeauna c irul se termin cu un caracter care nu este # (oricum n continuare pe band apar numai caractere #). Deci o configuraie este de forma

61

Irina Athanasiu

10/4/2003


62

(q, a, i, ). Pentru simplificare, o configuraie se poate reprezenta i sub forma (q, ai), subliniind simbolul pe care se gsete capul de citire / scriere. Asupra configuraiilor se poate defini o relaie de tranziie |- n modul urmtor. Fie (q1, w1, a1, u1) i (q2, w2, a2, u2) dou configuraii. Atunci: (q1,w1,a1,u1) |- (q2,w2,a2,u2) # w1 a1 u1 # # w1 a1 u1 # # w1 a1 u1# # w2 a2 u2 # # w2 a2 u2# # w2 a2 u2 # dac i numai dac exist b T {L, R} astfel nct m(q1, a1) = (q2, b) i este ndeplinit una dintre urmtoarele condiii :

62

Irina Athanasiu

10/4/2003


63

1. b T, w1 = w2, u1 = u2, a2 = b; 2. b = L, w1 = w2a2 dac a1 # sau u1 atunci u2 = a1 u1 altfel u2 = /* capul de citire / scriere este poziionat dup irul de intrare */ 3. b = R, w2 = w1a1 dac u1 = atunci u2 = a2 = # altfel u1 = a2 u2 n cazul 1 se face nlocuirea simbolului curent de pe banda de intrare (a) cu b. n al doilea caz este descris o micare la stnga, respectiv n cazul 3 se descrie o micare la dreapta. Dac b = L i w1 = atunci (q1, w1, a1, u1) nu are o configuraie urmtoare, n acest caz se spune c (q1, w1, a1, u1) este o configuraie de agare, maina find ntr-o stare de agare (hanging state). Pentru relaia |- se poate considera inchiderea reflexiv i tranzitiv notat cu |-*. Un calcul efectuat de o maina Turing este o secven de configuraii c0, c1, ..., cn astfel nct n 0 i c0 |- c1 |- ... |- cn. Se spune despre calcul c are loc n n pai. Termenul de calcul nu a fost utilizat ntimpltor. Se poate considera c o main Turing tie s evalueze funcii definite pe iruri de simboli cu valori n iruri de simboli. Dac T1 i T2 sunt doua mulimi alfabet care nu conin simbolul #, s considerm funcia f : T1* T2*. Spunem ca MT = (Q, T, m, s) calculeaz f dac T1, T2 T i pentru orice ir w T1* dac u = f(w), u T2*, atunci (s, #w#) |-* (h, #u#). Se observ c s-a considerat c capul este poziionat dup sfritul irului de intrare att la nceputul execuiei ct i la sfritul acesteia. Dac pentru o funcie f dat exist o maina Turing care o calculeaz spunem c funcia f este Turing calculabil. S considerm de exemplu maina Turing MT = ({q0, q1, q2}, {a, b, #}, m ,q0) unde funcia m este definit n modul urmtor :m(q0, m(q0, m(q0, m(q1, m(q1, m(q1, m(q2, m(q2, m(q2, a) b) #) a) b) #) a) b) #) = = = = = = = = = (q1, (q1, (q1, (q0, (q0, (q2, (q2, (q2, (h, L) L) L) b) a) R) R) R) #)

S considerm evoluia pentru irul de intrare aab.(q0, #aab#) |||||||||(q1, (q0, (q1, (q0, (q1, (q0, (q1, (q2, (q2, #aab#) #aaa#) #aaa#) #aba#) #aba#) #bba#) #bba#) #bba#) #bba#)

63

Irina Athanasiu|- (q2, #bba#) |- (q2, #bba#) |- (h, #bba#)

10/4/2003


64

Pentru irul vid evoluia este :(q0, ##) |- (q1, ##) |- (q2, ##) |- (h, ##)

Funcia calculat de aceast main Turing este funcia de interschimbare a caracterelor a i b. Din domeniul irurilor putem s trecem n domeniul numerelor naturale considernd reprezentarea unar a numerelor naturale. Adic utiliznd un alfabet I care conine un singur simbol, I diferit de #, reprezentarea unui numr natural n este data de irul = In. Se observ c numrul 0 este reprezentat de irul vid. n acest caz o funcie f : N N este calculat de o main Turing, dac aceasta calculeaz f' : I* I* unde f'() = cu In i If(n) pentru orice numr natural. De la un singur argument funcia f se poate extinde la mai multe argumente - f : Nk N pentru care corespunde f' : (I {,})* I* cu f'() = pentru un ir de forma i1, i2, ..., ik ,... ij Inj, 1 j k, i If(n1,...,nk). S considerm de exemplu funcia succesor f(n) = n + 1, n numr natural. MT = ({q0}, {i, #}, m, q0) cum(q0, i) = (h, R) m(q0, #) = (q0, i)

De exemplu (q0, #i#) |- (q0, #iii#) |- (h, #iii#). n general :(q0, #n#) |- (q0, #ini#) |- (h, #n+1#)

O main Turing poate s fie utilizat i ca acceptor de limbaj. i anume s considerm un limbaj L definit asupra alfabetului T care nu conine simbolii #, D i N. Fie dL : T* {D, N} o funcie definit n modul urmtor - pentru w T*D / dL(w) = \ N dac w L dac w L

Se spune ca limbajul L este decidabil n sens Turing (Turing decidable) dac i numai dac funcia dL este calculabil Turing. Dac dL este calculat de o maina Turing MT spunem ca MT decide L. S considerm de exemplu limbajul L = {w T* | |w| mod 2 = 0, T = {a}} (limbajul irurilor peste alfabetul T = {a} care au lungimea un numr par). Funcia dL corespunztoare poate s fie calculat de urmtoarea main Turing : MT = ({q0, q1, q2, q3, q4, q5, q6}, {a, D, N, #}, m , q0) unde m este o funcie partial definit n modul urmtor : m(q0, #) = (q1, L) pornim spre stnga

64

Irina Athanasiu

10/4/2003


65

m(q1, a) = (q2, #) se terge un a m(q1, #) = (q4, R) s-au ters un numr par de a m(q2, #) = (q3, L) s-a ters un a se continu spre stnga m(q3, a) = (q0, #) s-au ters doi de a, suntem ca la nceput m(q3, #) = (q6, R) s-a ajuns la stnga cu un numr imapar de a m(q4, #) = (q5, D) s-au ters zero sau un numr par de a m(q5, D) = (h, R) rspuns D i oprire m(q5, N) = (h, R) rspuns N i oprire m(q6, #) = (q5, N) au fost un numr impar de a S considerm evolutia mainii pentru un ir corect : (q0, #aa#) |- (q1, #aa#) |- (q2, #a#) |- (q3, #a#) |- (q0, ##) |- (q1, ##) |- (q4, ##) |- (q5, #D#) |- (h, #D#) Pentru un ir incorect se obine : (q0, #aaa#) |- (q1, #aaa#) |- (q2, #aa#) |- (q3, #aa#) |- (q0, #a#) |- (q1, #a#) |- (q2, ##) |- (q6, ##) |- (q5, #N#) |- (q3, ##) |- (h, #N#) Noiunea de acceptare este mai larg dect noiunea de decidabilitate n legatura cu limbajele. i anume dac L este un limbaj asupra alfabetului T, spunem ca limbajul L este Turing acceptabil dac exist o maina Turing care se oprete dac i numai dac w L. Limbajele Turing decidabile sunt i Turing acceptabile. Reciproca nu este ns adevarat. Fie limbajul : L = {w {a, b}* | w conine cel puin un simbol a} considernd maina Turing MT = ({q0}, {a, b, #}, m, q0) cu m(q0, a) = (h, a) m(q0, b) = (q0, L) m(q0, #) = (q0, L) Se poate constata ca dac pe banda de intrare se gasete un ir din limbaj atunci pornind din configuraia iniial se va face cutarea unui simbol a prin deplasare spre stnga. Dac un astfel de caracter este gsit maina se oprete (deci accept irul). Dac ns pe banda de intrare se gasete un ir care nu aparine limbajului atunci maina va intra n starea de agare dup ce a ajuns la captul din stnga al benzii.

65

Irina Athanasiu

10/4/2003


66

1.3.3.1. Compunerea mainilor TuringPentru a evidenia "puterea" de calcul a mainilor Turing vom prezenta mecanismul prin care o main Turing se poate construi pe baza unor maini Turing mai simple. Propoziie Fie MT o maina Turing i fie (qi, wiaiui), (i = 1, 2, 3) maini. Dac sunt posibile evoluiile : (q1, w1a1u1) |-* (q2, ww2a2u2) i (q2, w2a2u2) |-* (q3, w3a3u3) atunci este posibila i evoluia : (q1, w1a1u1) |-* (q3, ww3a3u3) Justificare. n evoluia din (q2, ww2a2u2) n (q3, w3a3u3) maina nu poate s ajunga pe banda de intrare pe un simbol aflat la stnga irului w2 (ntr-o astfel de situaie s-ar ajunge la marginea din stnga a benzii, deci s-ar intra n starea de agare i deci nu s-ar mai ajunge n configuraia urmtoare). Deoarece maina are o funcionare determinist va rezult aceai evoluie i dac irul w2a2u2 nu este la nceputul benzii de intrare. Rezult c este posibil i evoluia (q2, ww2a2u2) |-* (q3, ww3a3u3). Pe baza propoziiei anterioare putem s realizm compunerea mainilor Turing ntr-o manier similar utilizrii subprogramelor. S considerm de exemplu o maina Turing M1 care "stie" s funcioneze primind un ir pe banda de intrare pornind cu capul de citire / scriere poziionat dup ir. S presupunem c M1 nu poate s ntre ntr-o stare de agare. La oprire, capul va fi plasat de asemenea dup irul care a rezultat pe banda de intrare. Dac M1 este utilizat n cadrul unei alte maini Turing care printre alte aciuni pregtete i un ir de intrare pentru M1, atunci dup ce M1 primete controlul nu va depai limita stnga a irului su de intrare, deci nu va modifica un ir care eventual a fost memorat nainte pe banda de intrare. n cele ce urmeaz considerm ca masinile Turing care se combin nu pot s ntre n starea de agare i c fiecare are strile sale proprii diferite de strile tuturor celorlalte maini Turing. Ca maini de baza pornind de la care vom construi noi maini Turing vom considera cteva cu funcionare elementar. Aceste maini au un un alfabet de intrare T comun. 1. exist |T| maini care scriu fiecare cte un simbol din T n poziia curent a capului. O astfel de main este definit ca find Wa = ({q}, T, m, q), a T, m(q, b) = (h, a), b T. Pentru a simplifica notaiile Wa va fi reprezentat de simbolul a. 1. exist dou masini care execut deplasri elementare. i anume VL = ({q}, T, m, q) cu m(q, a) = (h, L) i VR = ({q}, T, m, q) cu m(q, a) = (h, R), a T. Vom nota aceste maini cu L i respectiv R. Reprezentarea compunerii mainilor Turing se face ntr-o manier asemntoare unei structuri de automat finit pentru care o stare este reprezentat de o maina Turing. Intrarea ntr-o stare a automatului corespunde cu iniierea funcionrii unei maini Turing. La oprirea unei maini Turing (intrarea acesteia n starea h) n funcie de simbolul aflat sub capul de citire se va trece ntr-o alt stare, adic se va iniia funcionarea unei alte maini Turing. O schem de main Turing este tripletul = (M, , M0) unde configuraii ale acestei

66

Irina Athanasiu

10/4/2003


67

M este o mulime finit de maini Turing care au toate un alfabet comun T i mulimi de stri distincte; M0 M este maina iniial; este o funcie parial , : M x T M.

O schem de main Turing reprezint o maina Turing compus din mainile care formeaz mulimea M. Funcionarea acesteia ncepe cu funcionarea mainii M0. Dac M0 se oprete atunci poate continua eventual funcionarea conform altei maini din M. Dac M0 se oprete cu capul de citire / scriere pe caracterul a atunci exist urmtoarele situaii : (M0, a) este nedefinit, n acest caz se oprete; (M0, a) = M', n acest caz funcionarea continu cu starea iniial a mainii M'.

Acelai mod de nlnuire va avea loc i la oprirea (dac intervine) mainii M'. n mod formal acest gen de compunere de maini Turing poate s fie descris n modul urmtor. Fie M = {M0, .., Mk}, k 0 astfel nct Mi = (Qi, T, mi, si), 0 i k. Fie q0, ..., qk stri care nu apar n mulimile Qi, 0 i k. Dac (M, , M0) este o schem de main Turing , ea va reprezenta maina MT = (Q, T, m, s) unde Q = Q0 ... Qk {q0, ..., qk} s = s0 m este definit n modul urmtor: a. dac q Qi, 0 i k, a T i mi(q,a) = (p, b), p h atunci m(q, a) = mi(q, a) = (p, b); b. dac q Qi, 0 i k, a T i mi(q, a) = (h, b) atunci m(q, a) = (qi, b); c. dac (Mi, a) (0 i k, a T) este nedefinit atunci m(qi, a) = (h,a); d. dac (Mi, a) = Mj (0 i k, a T) i mj(sj, a) = (p, b) atunci (p,b) p h / m(qi, a) = \ (qj, b) p = h Se observ c strile noi q0, ..., qk au fost introduse ca puncte de trecere de la o main la alta. Din definiie rezult c fiecare main funcioneaz "normal" pn cnd se oprete. Dac o main se oprete i este definit maina urmtoare se va trece n starea care face legatura cu maina urmtoare. Dac nu este definit maina urmtoare, MT se va opri. Dintr-o stare de legatur se intra n funcionarea mainii urmtoare pe baza simbolului curent de pe banda de intrare. S considerm de exemplu mulimea M = {M0} cu M0 = R = ({q}, T, m, q). Definim funcia n modul urmtor : (M0, a) = M0 dac a # (M0, #) este nedefinit n acest caz (M, , M0) reprezint o main notat cu R#, R# = ({q, q0}, T, m, q) unde m(q, a) = (q0, R), a T m(q0, a) = (q0, R), a # m(q0, #) = (h, a)

67

Irina Athanasiu

10/4/2003


68

Se observ c maina se deplaseaz la dreapta pn la primul simbol #. Dac T = {a, b. c} putem s reprezentm maina R# sub forma :a ---\ / /| \/ / | >R< | b /\ \ | / \ \| ---c

n cele ce urmeaz vom reprezenta grafic compunerea mainilor Turing utiliznd o serie de reguli : fiecare main Mi M apare o singur dat; maina iniial (M0) este indicat prin semnul >; dac a T i (Mi, a) este definit i de exemplu M' = (Mi,a) atunci va exist un arc de la Mi la M' etichetat cu a.

Se poate ntmpla ca n M s apar mai multe copii ale aceleiai maini (fiecare cu strile ei proprii diferite de strile celorlalte). n acest caz fiecare dintre exemplare reprezint o alt main Turing deci va fi desenat separat. n reprezentrile grafice urmtoare vom utiliza o serie de simplificri. De exemplu schema :a ---------/ b \ > R ----------> R \ c / | ---------- | \ # / ------------

peste alfabetul T = {a, b, c, #} poate s fie reprezentata

a,b,c,# > R --------- R sau > R -- R sau RR sau R2 indicnd faptul c se fac dou deplasri la dreapta indiferent de coninutul benzii de intrare. Dac a T, a reprezint orice simbol din T diferit de a. Deci maina care caut simbolul # la dreapta poate s fie reprezentat ca :/| /| >R< | \| \| /| /| > R < | # \| \|

a # sau

Urmtoarea schem:

68

Irina Athanasiu/| /| >R< | # | \| | \| | |a # La

10/4/2003


69

caut mergnd la dreapta un simbol diferit de #, cnd l gsete l copiaz la stnga poziiei pe care l-a gsit. Se observ c din notaia a # rezult c simbolul gsit, i care este diferit de #, este notat generic cu a i poate s fie utilizat n continuare. n cele ce urmeaz utilizm urmtoarele notaii : R#, este maina care caut primul simbol # la dreapta L#, este maina care caut primul simbol # la stnga R#, este maina care caut primul simbol diferit de # la dreapta L#, este maina care caut primul simbol diferit de # la stnga

Utiliznd aceste maini "simple" s construim o maina de copiere C care funcionez n modul urmtor. S presupunem c pe banda de intrare se gsete un ir w care nu conine simboli # (eventual irul poate s fie i vid). Presupunem ca la stnga irului de intrare se gsete un singur simbol #; pe banda de intrare nu se mai gsesc simboli diferii de # care s nu fac parte din w. Capul este poziionat pe simbolul # care marcheaz sfritul irului w. Evoluia mainii trebuie s fie (s, #w#) |-* (h, #w#w#). Se spune ca maina transform irul #w# n #w#w#. Reprezentarea grafic pentru aceasta main este :+-------------------------+ | x # | -->R --------#R# 2x L# 2 x ---+ # | R#

>L#

S urmrim evoluia mainii pentru coninutul benzii #abc#(q, #abc#) |-* (q, #abc#) |- (q, #abc#) |- (q, ##bc#) R # L# |- (q,##bc##) |- (q,##bc#) R# R# |- (q, ##bc#a#) |- (q, ##bc#a#) |- (q, ##bc#a#) L# x L# |- (q, #abc#a#) |- (q, #abc#a#) |- (q, #a#c#a#) x R # |- (q, #a#c#a#) |- (q, #a#c#a#) R# R# |- (q, #a#c#ab#) |- (q, #a#c#ab#) x L# |- (q, #a#c#ab#) |- (q, #abc#ab#) x L# |- (q, #abc#ab#) |- (q, #ab##ab#) R # |- (q, #ab##ab#) |- (q, #ab##abc#) x R#R# |- (q, #ab##abc#) |- (q,#abc#abc#)

69

Irina Athanasiu

10/4/2003L#L# x |- (q, #abc#abc#) |- (q,#abc#abc#) R R# |- (h,#abc#abc#)


70

n evolutia prezentat anterior starea nu conteaz aa c a fost notat cu un simbol generic q. Se observ c dac C ncepe s funcioneze cu un coninut al benzii de forma #u#v#w# la sfritul execuiei se obine pe banda #u#v#w#w#. C nu funcioneaz corect dac la pornire la dreapta capului de citire se gsete un simbol diferit de #. Maina SL :+----------------+ | x # | >L ->R ----> LxR ----+ # |# L#

transform irul #w# n w#. Similar se poate construi o maina SR care transform irul #w# n ##ww#. Fie T0 = T - {#} cu f : T0* T0* astfel nct f(w) =wwR, f poate s fie calculat de urmtoarea main:+--------------------+ | x # | >L ----> #R# xL# x ----+ |# R#

Pe parcursul funcionrii maina transform iruri de forma #x1 ... xn# n #x1 ... xi ... xnxnxn1 ... xi+1#, i = n-1, ..., 0. Pentru i = 0 se ajunge la #x1 ... xnxn ... x1#.

1.3.3.2. Extensii pentru maina TuringAvnd n vedere simplitatea deosebit a funcionrii unei msini Turing standard, se pune problema dac aceasta nu poate s fie fcut mai "puternic": prin adaugarea unor extensii care s o apropie eventual de un calculator real. Se poate demonstra c adugarea unor faciliti ca de exemplu : banda de intrare infinit la ambele capete; mai multe capete de citire / scriere; mai multe benzi de intrare; o banda de intrare organizat n dou sau mai multe dimensiuni (eventual o memorie aa cum apare la calculatoare);

nu crete puterea de calcul oferit. Adic, nu se schimb nici clasa funciilor care pot s fie calculate i nici a limbajelor acceptate sau decise. Demonstratiile de echivalen sunt constructive realizndu-se pentru fiecare extensie construirea unei maini Turing standard capabil s simuleze funcionarea unei maini Turing avnd extensia considerat. S considerm de exemplu o maina Turing care are o band

70

Irina Athanasiu

10/4/2003


71

infinit la ambele capete. Schimbarea definiiei formale pentru acest model de maina Turing intervine n modul n care se definete noiunea de configuraie i relaia |- asupra configuraiilor. n acest caz o configuraie este de forma (q, w, a, u) i w nu incepe cu un simbol # iar u nu se termina cu un simbol #. Nu mai exist limitri referitoare la deplasarea la stnga i deci dispar noiunile de stare i respectiv de configuraie de agare. Propoziie. Fie M1 = (Q1, T1, m1, q1) o main Turing cu banda de intrare infinit la ambele capete. Exist o main Turing standard M2 = (Q2, T2, m2, q2) astfel nct, pentru orice w (T1 - {#})* sunt ndeplinite urmtoarele condiii : dac M1 se oprete pentru w, adic:(q1, w#) |-* (h, uav), u, v T1*, a T1

atunci i M2 se oprete pentru w, adic:(q2, #w#) |-* (h, #uav), u, v T1*, a T1

dac M1 nu se oprete pentru w atunci nici M2 nu se oprete pentru w. Demonstratie. Banda de intrare pentru M2 se obine prin ndoirea benzii de intrare a mainii M1. Adic, dac considerm c banda de intrare M1 are un "mijloc" ales arbitrar :---------------------------------------| -3 | -2 | -1 | 0 | 1 | 2 | 3 | ----------------------------------------

atunci banda de intrare pentru M2 va avea forma:+--------------------------| | 0| 1| 2| 3| | $ |----+----+----+----| | | -1 | -2 | -3 | -4 | +---------------------------

n simulare se va consider deci c funcionarea masini M1 n partea dreapta a benzii de intrare corespunde funcionrii maini M2 pe pista superioar a benzii sale de intrare, respectiv funcionarea maini M1 n partea stng corespunde funcionrii maini M2 pe pista inferioar a benzii sale de intrare. Rezult deci c pentru M2 se va utiliza un alfabet care conine perechi de simboli din alfabetul T1. O astfel de pereche (a, b) va indica faptul c a este coninut de pista superioar iar b este coninut de pista inferioar. Vom nota cu T o mulime definit n modul urmtor :T = {a | a T1}

n acest caz T2 = {$} T1 (T1 x T1) (T1 x T) (T x T1). M2 simuleaza M1 n modul urmtor : 1. se mparte banda de intrare n dou piste i se copiaz irul de intrare pe pista superioar; 2. se simuleaz funcionarea M1 pe banda obinut;

71

Irina Athanasiu

10/4/2003


72

3. cnd i dac M1 se oprete, se reface forma iniial a benzii. Pentru a realiza prima etapa trebuie s se realizeze o prelucrare de iruri. Adic, dintr-o banda de intrare de forma :---------------------------------------| # | a1 | a2 | ...| an | # | # | ---------------------------------------

trebuie s se ajung la un coninut al benzii de forma :+-----------------------------------| | a1 | a2 | ...| an | # | | | $ |----+----+----+----+----| # | | | # | # | ...| # | # | | +-----------------------------------

unde a1, ..., an (T1 - {#})*. Se observ c prelucrrile necesare nu sunt deosebit de dificile. Etapa a doua poate s fie realizata de ctre o maina M1' care are n mulimea sa de stri pentru fiecare q Q1 o pereche de stri notate i . Dac M1' este ntr-o stare nseamn c M1' acioneaz asupra pistei superioare a benzii de intrare. Dac M1' este n starea atunci nseamn c M1' acioneaz asupra pistei inferioare. De asemenea exist strile i care reprezint oprirea n situaia n care M1' lucra pe pista superioar respectiv inferioar. Funcia de tranziie m' pentru M1' este definit n modul urmtor : a) dac q Q1, (a1, a2) T1 x T1 i m1(q, a1) = (p,b) atunci/ (, L) dac b = L m1'(,(a1,a2) = (, R) dac b = R \ (, (b, a2)) dac b T1

b) dac q Q1, (a1, a2) T1 x T1 i m1(q, a2) = (p, b) atunci/ (, R) dac b = L m1'(,(a1,a2) = (, L) dac b = R \ (, (a1, b)) dac b T1

c) dac q Q1 {h} atuncim1'(, $) = (, R) m1'(, $) = (, R)

d) dac q Q1 {h} atuncim1'(, #) = (, (#, #)) m1'(, #) = (, (#, #))

e) dac a1, a2 T1 atunci

72

Irina Athanasiu

10/4/2003


73

m1'(, (a1, a2)) = (h, (a', a2)) m1'(, (a1, a2)) = (h, (a1, a'))

f) pentru situaiile care nu se ncadreaz n nici unul dintre cazurile anterioare m1' se definete arbitrar. Se observ c n cazurile a i b este descris funcionarea mainii M1 la dreapta i respectiv la stnga "mijlocului" ales. Cazul c. trateaza comutarea ntre piste care trebuie realizat atunci cnd se ajunge la limita din stnga a benzii. Cazul d. indic modul n care se face extinderea celor doua piste la dreapta. Cazul e trateaza intrarea n starea de oprire (h) a maini simulate M1. Se observ ca la intrarea n aceasta stare se va produce intrarea n starea h i a mainii M1' cu inregistrarea pistei pe care s-a facut oprirea mainii simulate. Dac banda de intrare a masini M1 conine irul w (T1 - {#})* i aceasta se oprete cu un coninut de forma :----------------------------------------------| # | b1 | b2 | ...| bi | ...| bn | # | # | -----------------------------------------------

atunci M1' se va opri cu un coninut de forma :+------------------------------------| | ck+1 | ck+2 | ... | c2k | | | $ |------+------+-----+-----| # | | | ck | ck-1 | ... | c1 | | +-------------------------------------

unde c1c2 ... c2k = # ... # b1b2 ... bi-1 b bi+1 ... bn # ... # cu bi #, 1 i n. Pentru etapa a treia se face translatarea simbolilor diferii de # de pe pista inferioar pe pista superioar :+------------------------------------------| | b1 | b2 | ... | bi | ... | bn | | | $ |----+----+-----+----+-----+----| # | | | # | # | ... | # | ... | # | | +------------------------------------------

Din nou aceasta prelucrare este simpl. n final se reface banda sub forma :+------------------------------------------| # | b1 | b2 | ... | bi | ... | bn | # | +------------------------------------------

Rolul alfabetului T utilizat n construirea mainii M1' este de a permite identificarea poziiei capului la oprirea mainii M1'. Similar definitiei din cazul masinilor Turing standard putem s considerm i n acest caz definiia notiunii de calcul. i anume dac T1 i T2 sunt doua mulimi de tip alfabet care nu conin simbolul # atunci spunem c funcia f : T1* T2* este calculat de maina Turing, M care are banda de intrare infinit la ambele capete, dac i numai dac pentru orice w T1*, dac f(w) = u atunci (q, w#) |-* (h,u#). De asemenea noiunile de acceptare respectiv de

73

Irina Athanasiu

10/4/2003


74

decidabilitate referitoare la limbaje pot s fie definite pentru masinile Turing cu banda infinit la ambele capete ntr-o maniera similara celei de la maina Turing standard. Orice funcie care este calculat i orice limbaj care este acceptat sau decis de o maina Turing cu banda infinit la ambele capete este calculat respectiv acceptat sau decis de o main Turing standard. Construcii i rezultate similare pot fi realizate i pentru celelalte extensii considerate la inceputul acestui subcapitol. Din acest motiv n tratarea pe care o vom realiza n continuare putem s considerm pentru a simplifica demonstraiile n loc de maini Turing standard maini care au oricare dintre extensiile amintite sau chiar combinaii ale acestora. Extinderea masini Turing se poate face i prin renunarea la caracterul determinist al acestora. Pentru o main Turing nedeterminist funcia m este definit n modul urmtor : m : Q x T P((Q {h}) x (T {L, R})) Dupa cum s-a aratat pentru orice automat finit nedeterminist se poate construi un automat finit determinist echivalent. n cazul automatelor push down aceasta echivalenta nu exist. Cu alte cuvinte automatele push down nedeterministe sunt "mai puternice" dect cele deterministe deoarece automatele push down nedeterministe accepta o clasa mai larga de limbaje. n cazul masinilor Turing nedeterministe deoarece pentru acelai ir de intrare se pot obine rezultate diferite, se pune problema cum se alege "calculul util" efectuat de maina Turing. Vom restringe puin problema considernd numai noiunea de acceptare. n acest caz ceea ce conteaz este c maina Turing se oprete n una din evoluiile sale posibile. Rezultatul depus pe band nu este n acest caz neaprat semnificativ. S considerm mai nti un exemplu de main Turing nedeterminist. Fie limbajulL = { w { a, b}* | w contine sirul abaab}

Evident, limbajul este de tip regulat i poate s fie acceptat de un automat finit determinist. O soluie de maina Turing nedeterminista care accepta acest limbaj este :a, b -\/ b a a b a /| >L -----> L ----> L ----> L ----> L ----> a R | # | | | | | | \| #| b,# | b,# | a,# | b,# | #| -------->------>------- TE'| | | ----------+--------+--------+--------+--------+--------+--------| ' | |'->+TE'| | |' |' | ----------+--------+--------+--------+--------+--------+--------| T |T -> FT'| | |T->FT' | | | ----------+--------+--------+--------+--------+--------+--------| T' | |T' |T'->*FT'| |T' |T' | ----------+--------+--------+--------+--------+--------+--------| F |Fa| | |F->() | | | ----------------------------------------------------------------+

Pentru irul a + a * a rezult urmtoarele micri (stiva este reprezentata cu vrful la stnga):Stiva Intrare Iesire ------------+-----------------------+---------------------$ | a+a*a$ | ------------+-----------------------+---------------------TE'$ | a+a*a$ | TE' ------------+-----------------------+---------------------FT''$ | a+a*a$ | T FT' ------------+-----------------------+---------------------aT''$ | a+a*a$ | Fa ------------+-----------------------+---------------------T''$ | +a*a$ | ------------+-----------------------+----------------------

112

Irina Athanasiu

10/4/2003


113

'$ | +a*a$ | T' ------------+-----------------------+---------------------+TE'$ | +a*a$ | ' +TE' ------------+-----------------------+---------------------TE'$ | a*a$ | ------------+-----------------------+---------------------FT''$ | a*a$ | T FT' ------------+-----------------------+---------------------aT''$ | a*a$ | Fa ------------+-----------------------+---------------------T''$ | *a$ | ------------+-----------------------+---------------------*FT''$| *a$ | T' *FT' ------------+-----------------------+---------------------FT''$ | a$ | ------------+-----------------------+---------------------aT''$ | a$ | Fa ------------+-----------------------+---------------------T''$ | $ | ------------+-----------------------+---------------------'$ | $ | T' ------------+-----------------------+---------------------$ | $ | ' -----------------------------------------------------------

Construcia tabelei de analiza este realizat cu ajutorul a doua funcii FIRST i FOLLOW. FIRST : (N T)* P(T {}) FOLLOW : N P(T {$}) Dac w este un ir de simboli w (N T)*, FIRST(w) reprezint setul terminalelor cu care ncep irurile derivate din w. Dac w * atunci FIRST(w). Pentru un neterminal A, FOLLOW(A) reprezint mulimea terminalelor a care pot s apar imediat dupa A ntr-o form propoziional; adica dac exist o derivare S * Aa atunci a FOLLOW(A). Pentru a calcula FIRST(X) pentru toi simbolii X din gramatic se aplic urmtoarele reguli pn cnd nu se mai pot aduga simboli terminali sau pentru nici o mulime FIRST(X). 1. Dac X este un terminal atunci FIRST(X) = {X}; 2. Dac exist o producie X atunci FIRST(X) = FIRST(X) {} 3. Dac exist o producie X Y1 Y2 ... Yk i a FIRST(Yi), FIRST(Y1), ..., FIRST(Yi-1), (Y1 Y2 ... Yi-1 * ) atunci a FIRST(X). Dac FIRST(Yj), 1 j k, atunci FIRST(X). (orice simbol terminal din FIRST(Y1) este inclus n FIRST(X). Dac Y1 * atunci i orice simbol terminal din FIRST(Y2) este inclus n FIRST(X), etc.). Putem s calculm funcia FIRST pentru orice ir X1 X2 ... Xm n modul urmtor. Se adaug la FIRST(X1 X2 ... Xm) toi simbolii diferiti de din FIRST(X1). Se adaug apoi toi simbolii din FIRST(X2) diferiti de dac FIRST(X1), etc. n final dac apare n FIRST(Xi), 1 i m, se adauga la FIRST(X1 X2 ... Xm).

113

Irina Athanasiu

10/4/2003


114

Pentru a calcula FOLLOW(A) pentru A N se aplic urmtoarele reguli n mod repetat pn cnd nimic nu se mai poate adauga la mulimile FOLLOW: 1. $ face parte din FOLLOW(S) (S este simbolul de start al gramaticii); 2. Dac exist o producie A wB atunci FIRST() \ {} FOLLOW(B); 3. Dac exist o producie de forma A w B sau o producie A wB i FIRST() ( * ) atunci FOLLOW(A) FOLLOW(B) (B poate s apar i n alte contexte). S considerm de exemplu din nou gramatica fr recursivitate stnga pentru expresii aritmetice: TE', ' +TE' | , T FT', T' *FT' | , F () | a. FIRST() = FIRST(T) = FIRST(F) = {(,a} FIRST(E') = {+,} FIRST(T') = {*,} FOLLOW() = FOLLOW(') = {),$} FOLLOW(T) = FOLLOW(T') = {+,),$} FOLLOW(F) = {+,*,),$}

Pentru construirea tabelei de analiz se utilizeaz urmtoarele reguli: Dac A w este o producie i a FIRST(w) atunci dac simbolul pe banda de intrare este a analizorul trebuie s nlocuiasc n stiv pe A cu w. Dac w * atunci A este nlocuit n stiv cu w numai dac a FOLLOW(A) (n particular simbolul a poate s fie $).

Rezult urmtorul algoritm pentru construcia tabelei :initializare matrice M pentru fiecare p = A w P executa pentru fiecare a FIRST(w) T executa M[A,a] = M[A,a] {A w}

daca FIRST(w) atunci pentru fiecare b FOLLOW(A) executa /* b T {$} */ M[A,b] = M[A,b] {A w}

Aplicnd acest algoritm asupra gramaticii expresiilor aritmetice va rezulta tabela cu care a fost ilustrat funcionarea analizei predictive. S considerm ns i urmtoarea gramatic : S i t S S' | a, S' e S | , b. ( este vorba de gramatica care descrie instruciunea if). Pentru aceast gramatic rezult urmtoarea tabel de analiz:

114

Irina Athanasiu

10/4/2003


115

neterminal a b e i t $ ----------+--------+--------+--------+---------+--------+--------| S | S -> a | | |S->iEtSS'| | | ----------+--------+--------+--------+---------+--------+--------| S' | | |S' -> | | |S' > | | | |S' -> eS| | | | ----------+--------+--------+--------+---------+--------+--------| | | > b | | | | | -----------------------------------------------------------------+

M[S',e] = {S' eS, S' } deoarece FOLLOW(S') = {e, $}. Se tie c n aceast form gramatica este ambigu i ambiguitatea se manifest prin alegerea ce trebuie s fie fcut cnd se ntlnete simbolul e (else). Soluia corect este de a alege producia S' eS (aceast alegere corespunde asocierii cuvintului else cu cel mai recent then). Se observ c alegerea permanent a produciei S' ar impiedica aducerea terminalului e (else) n vrful stivei ceea ce nu poate conduce la o evoluie corect. O gramatic pentru care n tabela de analiz nu exist intrri cu mai multe alternative se spune c este o gramatic LL(1) (primul L se refera la parcurgerea irului de intrare de la stnga (Left) la dreapta, al doilea L pentru utilizarea derivrii stnga (Left), iar 1 se refer la utilizarea unui terminal pentru a adopta o decizie de analiza). Gramaticile LL(1) sunt gramatici neambigue, nerecursive stnga i factorizate. Se poate arta c o gramatic G este LL(1) dac i numai dac pentru oricare doua producii de forma A , A , cu sunt satisfacute urmtoarele condiii : 1. FIRST() FIRST() = 2. dac * atunci FIRST() FOLLOW(A) = iar dac * atunci FIRST() FOLLOW(A) = . Gramatica pentru expresii aritmetice (fr recursivitate stnga) este LL(1) n timp ce gramatica considerat pentru instructiunea if nu este LL(1). Se pune problema cum se poate realiza o analiz predictiv pentru un limbaj descris de o gramatic care nu este LL(1). O solutie este de a transforma gramatica astfel nct s devin LL(1). n anumite cazuri (ca de xemplu n cazul anterior al gramaticii pentru limbajul corespunztor instruciunilor if) se poate face o "potrivire" a tabelei M, dar nu exist o regul general de transformare a matricii de analiz astfel nct intrrile multiple s poat s fie nlocuite cu intrri simple. Transformarea suferit de o gramatic pentru a deveni LL(1) o poate face ns dificil de recunoscut. De obicei analiza predictiv este utilizat pentru instruciuni (nu pentru expresii).

3.1.1.3. Tratarea erorilor n analiza predictivExistena n stiv a terminalelor i neterminalelor pe care analizorul se ateapt s le gseasc pe banda de intrare simplific mult problema diagnosticrii erorii. O eroare este detectat n timpul analizei dac n vrful stivei se gsete un terminal care nu coincide cu terminalul curent de pe

Curs Compilatoare - Irina Athanasiu

Documents

Transcript of Curs Compilatoare - Irina Athanasiu