UNIVERSITATEA BABE-BOLYAI CLUJ-NAPOCA FACULTATEA DE MATEMATIC I INFORMATIC CENTRUL DE FORMARE CONTINU I NVMNT LA DISTAN

GRIGOR MOLDOVAN MIHAELA LUPEA VASILE CIOBAN

LIMBAJE FORMALE I AUTOMATE Culegere de probleme

2000

3

1. NOIUNI FUNDAMENTALE I PROBLEME PROPUSE.....................31.1. GRAMATICI I LIMBAJE........................................................................................................................3 1.1.1. Probleme propuse...................................................................................................................................6 1.1.2. Indicaii i soluii ..................................................................................................................................8 1.2. AUTOMATE FINITE.................................................................................................................................20 1.2.1. Automate finite deterministe (AFD), automate finite nedeterministe (AFN)......................................20 1.2.2. Reprezentare..........................................................................................................................................21 1.2.3. Configuraii i relaii de tranziie......................................................................................................22 1.2.4. Limbaj acceptat de un AF.................................................................................................................22 1.2.5. Funcionare............................................................................................................................................23 1.2.6. Echivalena dintre AFD i AFN........................................................................................................24 1.2.7. Minimizarea automatelor finite...........................................................................................................25 1.2.8. Construcia AFD redus........................................................................................................................25 1.2.9. Automate finite cu -micri..............................................................................................................26 1.2.10. Probleme propuse...............................................................................................................................26 1.2.11. Indicaii i soluii.................................................................................................................................31 1.3. EXPRESII REGULARE.............................................................................................................................35 1.3.1. Probleme rezolvate...............................................................................................................................39 1.3.2. Probleme propuse.................................................................................................................................43 1.3.3. Indicaii i soluii.................................................................................................................................46 1.4. GRAMATICI I LIMBAJE REGULARE...............................................................................................47 1.4.1. Legtura dintre gramaticile regulare i automatele finite................................................................47 1.4.2. Proprieti de nchidere ale limbajelor regulare...............................................................................48 1.4.3. Lema de pompare pentru limbaje regulare.......................................................................................49 1.4.4. Probleme propuse.................................................................................................................................50 1.4.5. Indicaii i soluii.................................................................................................................................52 1.5. GRAMATICI I LIMBAJE INDEPENDENTE DE CONTEXT...........................................................56 1.5.1. Proprieti de nchidere ale limbajelor independente de context...................................................56 1.5.2. Arbori de derivare...............................................................................................................................56 1.5.3. Simplificarea gramaticilor independente de context.........................................................................58 1.5.4. Forma normal Chomsky....................................................................................................................61 1.5.5. Forma normal Greibach.....................................................................................................................61 1.5.6. Leme de pompare pentru limbaje independente de context...........................................................62 1.5.7. Probleme propuse.................................................................................................................................62 1.5.8. Indicaii i soluii ................................................................................................................................65 1.6. AUTOMATE PUSH-DOWN.....................................................................................................................70 1.6.1. Reprezentare..........................................................................................................................................71 1.6.2. Limbaj acceptat de un APD..............................................................................................................71 1.6.3. Probleme propuse.................................................................................................................................72 1.6.4. Indicaii i soluii.................................................................................................................................73 1.7. TRANSLATARE I TRANSLATOARE..................................................................................................84 1.7.1. Translator finit......................................................................................................................................84 1.7.2. Translator push-down...........................................................................................................................85 1.7.3. Probleme propuse.................................................................................................................................86 1.7.4. Indicaii i soluii.................................................................................................................................86

2. PROBLEME I PROGRAME COMPLEXE...........................................882.1. PROBLEME PROPUSE..............................................................................................................................88 2.1. INDICAII I SOLUII............................................................................................................................90

B I B L I O G R A F I E....................................................................................102

1. NOIUNI FUNDAMENTALE I PROBLEME PROPUSE1.1. GRAMATICI I LIMBAJEFie o mulime de elemente, finit i nevid. O astfel de mulime o numim alfabet, iar elementele ei le numim simboluri. O succesiune de simboluri ale alfabetului o numim secven peste alfabetul , iar o mulime de simboluri consecutive dintr-o secven se numete subsecven. Exemplu: Dac w = a1a2an; atunci w este o secven peste alfabetul , iar dac w=a1a2a3a4a5 atunci w = a3a4 este o subsecven a secvenei w. Dac x = a1a2an iar y = b1b2bm atunci z = xy, adic z = a1anb1bm reprezint concatenarea secvenelor x i y. Dac x, y, z sunt secvene peste alfabetul , atunci x este un prefix al secvenei xy, y un sufix al secvenei xy, iar y n secvena xyz este o subsecven. De asemenea, adesea vom folosi notaia an = aa (de n ori). Lungimea unei secvene w, peste un alfabet , notat |w|, este numrul simbolurilor din care este alctuit. Secvena de lungime 0, o notm cu , deci | | =0, i se numete secvena vid. Exemplu: Dac w = a1a2an atunci |w| = n. Notm cu * mulimea tuturor secvenelor peste alfabetul . Exemplu: Dac = {a}, atunci * = { , a, a2, , an ,} Observaie: O secven peste alfabetul , poate fi considerat i ca un element al monoidului liber ( *, ) generat de , iar operaia " " este operaia de concatenare : * x * > * definit mai sus. Operaia de concatenare este asociativ i * este elementul neutru. Cele dou proprieti ale concatenrii definesc structura de monoid. Pentru operaia de concatenare nu folosim simboluri speciale. Numim limbaj peste alfabetul , o submulime L a mulimii *, deci L *. Elementele unui limbaj le numim cuvinte. Un limbaj poate s fie finit, adic s conin un numr finit de cuvinte, sau s fie infinit. Dac L1 este un limbaj peste alfabetul 1, iar L2 este un limbaj peste alfabetul 2 atunci prin operaiile: - L1 L 2 (reuniune); - L1 L 2 (intersecie); - L1 L 2 (diferena); - L1 L 2 = {uv | uL1, vL2} (concatenarea); obinem, de asemenea, nite limbaje peste alfabete alese corespunztor.3

Fie L, L1, L2 limbaje peste un alfabet , atunci putem defini urmtoarele limbaje:-

L = {x * | x L}

(complementara); (nchiderea reflexiv i tranzitiv);

L* = Lnn 0

unde Ln = LL n -1 , L0 ={ };

-

* * L+ = Ln s a uL+ = L L= L+ L , L = L+ } ; (nchiderea tranzitiv); { n 1L1 / L2 = { w* yL2: wyL1} L1 \ L2 = { w* yL2: ywL1} (ctul la dreapta); (ctul la stnga);

-

Un ansamblu G = (N, , P, S) unde: - N este un alfabet de simboluri neterminale; - este un alfabet de simboluri terminale; - P (N )* N (N )* x (N )*, P este o mulime finit de producii; - SN, S este simbolul iniial ; se numete gramatic. Dac ( , )P, atunci convenim s notm aceast producie astfel: i nseamn c se nlocuiete cu . Observaie: Din definiia unei gramatici rezult evident c N = .

O gramatic reprezint o modalitate de specificare a unui limbaj. Fie gramatica G = (N, , P, S). Pe mulimea (N )* se definesc relaiile binare: => (derivare direct);

=> => =>* +

k

(k derivare);

(+ derivare);

(* derivare).

4

Avem => 1, 2, , (N )* astfel nct = 1 2, = 1 2, iar ( ) P. k O k derivare" este o succesiune de k derivri directe, adic = > < > =

1, .k.1 . N,

()

*

astfel nct => 1 => ... => k-1 => .

ntre dou secvene avem o "+ derivare" dac k>0 astfel nct ele s fie ntr-o relaie de "k derivare". ntre dou secvene avem o "* derivare" dac = sau = > . >+

Limbajul generat de o gramatic G = (N, , P, S) este:L( G ) = {w | w * , S = > w}*

Fie gramatica G = (N, , P, S). O secven x(N )* astfel nct S = > x, se numete form propoziional. O form propoziional care nu conine neterminale se numete propoziie. O propoziie este un cuvnt al limbajului generat de gramatica G. Dou gramatici G1 i G2 sunt echivalente dac ele genereaz acelai limbaj, deci L(G1) = L(G2). Dup forma produciilor gramaticilor, acestea se clasific (dup Chomsky) n gramatici de tip 0,1,2,3. Gramaticile de tip 0 sunt gramaticile care nu au nici o restricie referitoare la forma produciilor. Gramaticile de tip 1 sunt gramaticile n care pentru orice producie din P avem | | | |. Dac producia S aparine gramaticii, atunci S nu apare n membrul drept al nici unei producii. Gramaticile de tip 2 sunt gramaticile n care produciile sunt de forma A , AN, (N )*. Gramaticile de tip 3 sunt gramaticile n care orice producie are numai una din formele urmtoare: AaB sau Ab, unde A,BN i a,b , iar dac producia S aparine gramaticii, atunci S nu apare n membrul drept al nici unei producii. Gramaticile de tip 1 se mai numesc gramatici dependente de context, cele de tip 2 sunt gramatici independente de context, iar cele de tip 3 gramatici regulare.5

*

1.1.1. Probleme propuse1.1.1. S se defineasc mulimea numerelor naturale N ca limbaj. 1.1.2. Fie gramatica G = (N, , P, S) unde N = {S,C}, = {a,b}, P = {S ab | aCSb, CS | bSb, CS b}. S se arate c ab(ab2)2L(G). 1.1.3. Se d gramatica G = (N, , P, S) unde: N = {S,A}; = { , p, q, r, ', (, )}; , , P = {S (S) | (S) | (S) | A, AA' | p | q | r}. (S) (S) S se verifice c urmtoarele secvene aparin limbajului generat de aceast gramatic: a) ((p') (p)) (r''); b) ((p) (q')); c) r''''. 1.1.4. Se d gramatica G = (N, , P, S) unde: N = {S,A}; = { , p, q, r, '}; , , P = {S | | S | A, AA' | p | q | r}; SS SS S se verifice c pqr L(G). pqr 1.1.5. Fie gramatica G = ({S}, {a,b,c}, {S a2S | bc}, S). S se arate c: L(G) = {a2nbc | n 0}. 1.1.6. Se d gramatica G = ({S,H}, {b,c,d,e}, {S bbSe | H, H cHdd cd}, S). Care este limbajul generat de aceast gramatic ? 1.1.7. Se d gramatica independent de context G = ({S,A,B}, {a,b,c}, P, S) unde: P = {S AB, A aAb | ab, B cB | c}. a) Care este limbajul generat de acest gramatic ? b) S se reprezinte sub form de vectori, list ramificat i tablou gramatica dat. 1.1.8. S se construiasc gramatici pentru generarea limbajelor:6

a) L = {a2n-1 | n 1}; b) L = {a2n | n 1}. 1.1.9. S se construiasc gramatici care genereaz limbajul L = {xnyn | n 1}. 1.1.10. S se construiasc o gramatic dependent de context care genereaz limbajul: L = {anbncn | n 1}. 1.1.11. S se construiasc o gramatic dependent de context care genereaz limbajul: L = {anbncndn | n 1}. 1.1.12. S se dea o gramatic care genereaz limbajul L = {anbncndnen | n 1}. 1.1.13. S se construiasc gramaticile care genereaz limbajele: a) L1 = {ww | w{a,b}*}; b) L2 = {ambnambn | m,n 1}; c) L3 = {wxw | w,x{a,b}*}. 1.1.14. S se construiasc gramaticile care genereaz limbajele: a) L1 = a 2 | n 0 ;

{

n

b) L 2 = a k | n 0, k N, fixat . 1.1.15. S se construiasc gramaticile care genereaz: a) expresiile algebrice ce conin operandul a i operatorii: +, *, ( ,) ; b) expresiile algebrice ce conin operandul a i operatorii: +, -, *, :, (, ). 1.1.16. S se construiasc o gramatic care genereaz limbajul L = {a2mbn+1c2n+1dm | m 1, n 0}. 1.1.17. S se construiasc gramatici care genereaz limbajele: a) L1 = {anbncmdm | n,m 1}; b) L2 = {anbnambm | n,m 1}. 1.1.18. S se construiasc o gramatic care genereaz limbajul L = {anbncndmem | n,m 1}.7

{

}

n

}

1.1.19. S se construiasc gramatici dependente de context care genereaz limbajele: a) L1 = {anbncm | n m 0}; b) L2 = {anbncm | m n 0}; c) L3 = {anbmcl | n m l 0}; d) L4 = {anbncm | 0 n m 2n}.

1.1.20. Pentru o secven w s notm numrul de simboluri s din aceast secven cu nrs(w).S se construiasc gramatici care genereaz limbajele: a) L1 = {w{a,b,c}* | nra(w)+nrb(w)=nrc(w)}; b) L2 = {w{a,b,c}* | nra(w)=nrb(w)=nrc(w)}. 1.1.21. S se demonstreze c pentru ctul la dreapta dintre limbaje avem: a) L1 / (L2 L3) = (L1 / L2 ) (L1 / L3); b) (L1 L2) / L3 = (L1 / L3 ) (L2 / L3); c) L1 / (L2 L3) = (L1 / L3 ) / L2; d) (L1 L2 ) / L3 = L1 / (L2 / L3) L1 / (L3 / L2); e) L1 / (L2 L3) = (L1 / L2 ) (L1 / L3); f) (L1 L2) / L3 = L1 / L3 L2 / L3; Proprieti similare exist i pentru ctul la stnga.

1.1.2. Indicaii i soluiin rezolvarea problemelor de determinare a unei gramatici care genereaz un limbaj, esenial este stabilirea mulimii P a produciilor. De aceea de multe ori mulimea P o vom da n mai multe variante; totodat de multe ori schimbnd produciile se pot introduce noi neterminale, deci gramaticile care genereaz limbajul s fie complet diferite. S reinem i alte amnunte legate de recursivitatea produciilor: - pentru familiarizarea cu definiiile recursive trebuie ncercat s se definesc foarte multe noiuni matematice i informatice n acest mod pornind de la noiuni simple cum ar fi cea de identificator i anume: := ; :=mulimea literelor alfabetului latin; :=mulimea cifrelor zecimale, .a.m.d.8

- s reinem apoi c pentru gramaticile de tipul 1, 2 i 3 dup fiecare derivare, lungimea secvenei din (N )* se mrete; - definiiile recursive nu sunt unice ntotdeauna, fapt ce se va vedea i n continuare (pentru aceeai problem n multe cazuri se vor da gramatici diferite). 1.1.1. Avem = {0,1,2,3,4,5,6,7,8,9} iar * {w w=aw1, a{1,2,3,4,5,6,7,8,9}, w1 *} {0} = N 1.1.2. Trebuie s artm c dup un numr finit de derivri directe, >, din simbolul iniial S*

se obine cuvntul ab(ab2)2=ababbabb, adic S = > ab (ab 2 ) 2 . Numerotm produciile gramaticii date, astfel: 1. S ab 2. S aCSb 3. C bSb 4. C S 5. CS b aplic n trecerea de la o secven la o secven , de exemplu, = > sau dac 3 folosim succesiv, de la stnga la dreapta, de exemplu produciile i, j, k mai scurt vom scrie = > .i, j, k +

Vom scrie sub relaia de derivare direct, >, numrul regulii de producie care se

Avem astfel: S = > aCSb = > abSbSb = > ababbSb = > ababbabb 2 3 1 1 sauS = > aCSb = > ababbabb .2 3,1,1 +

Observm c produciile 4 i 5 nu au fost folosite. 1.1.3. Procednd analog cu rezolvarea problemei precedente numerotm produciile astfel: 1. S (S) (S) 5. A A' 2. S (S) (S) 6. A p 3. S (S) 7. A q 4. S A 8. A r i atunci avem:+ +

S = > (S ) (S )= > (( S ) (S )) (S ) = > ((A ) (A )) (A )= > ((A)' (A )) (A )= > 2 1 4, 4 , 4 5 6 , 6,5

((p' ) (p)) (A' ) = > ((p' ) (p)) (A' ' ) = > ((p' ) ( p)) ( r' ' ) .5 8

b) i c) analog.9

1.1.4. Procedm analog cu rezolvarea problemei precedente. Numerotm produciile astfel: 1. S SS 4. S A 7. A q 2. S SS 5. A A' 8. A r 3. S S 6. A p i atunci avem:+ + +

S = > S S= > S S S= > S S S S = > A A A S=S > p q r S S > S =1 2 1, 2 4 ,4 ,4+ 6 , 7 ,8

6 , 7 ,8

1

pqr SSS = > pqr AAA = > pqr pqr .4, 4,4

+

1.1.5. Egalitatea mulimilor, L(G) = {a2nbc| n 0} se demonstreaz prin dubl incluziune: a) {a2nbc| n 0} L(G), pe scurt "". Fie w=a2nbc, n fixat. Trebuie s artm c wL(G). ntr-adevr, folosind de n ori producia 1. S>a2S i odat producia 2. S>bc, avem:

S = > (a 2 ) n S = > a 2n bc, adica a 2n bc L(G) .1 2

n

b) A demonstra incluziunea invers (""), adic L(G) {a2nbc 0}, revine la a arta n c gramatica G genereaz numai cuvinte de forma a2nbc. Pentru a demonstra acest lucru s considerm propoziia care depinde de numrul natural n, P(n): "Folosind de n ori produciile S a2S, Sbc se obin numai secvene de forma a2nS sau a2(n-1)bc". Demonstrm proprietatea P(n) prin inducie matematic. 1) Verificare. Dac n=1, deci folosind o singur producie, obinem secvena a2S sau bc. 2) Demonstraia. Presupunem c P(k) este adevrat i trebuie s demonstrm c i P(k+1) este adevrat. Secvenele a2(k+1)S, a2kbc se obin folosind cte una din cele dou producii, pornind de la secvena a2kS. Din proprietatea P(n) rezult c singurele cuvinte generate de gramatic sunt de forma a b, n 0 i este adevrat incluziunea "".2n

1.1.6. L(G)={b2ncmd2m-1en| m 1, n 0}. 1.1.7. a) L(G)={aibicj | i 1, j 1}; b)10

1) vectorial; vom construi vectorii: N: S A B $ : a b c $

P: S A B # A a A b |

a b # B c B |

c # $

Am marcat sfritul irului de caractere ce definesc cei trei vectori cu $, iar sfritul regulilor de producie cu acelai membru stng, cu #. 2) list ramificat nlnuit Pentru fiecare membru drept al fiecrei producii se construiete o sublist liniar. Considerm nodurile listei de forma: a b c d unde cmpurile au urmtoarele semnificaii: a - simbolul terminal sau neterminal al gramaticii (numai din membrul drept al fiecrei producii); b - pointer sau ntreg astfel: b:= 0 dac a ; b:= pointer spre capul primei subliste ataate regulii de producie cu membrul stng a. c - pointer sau ntreg; Considerm urmtoarele propoziii: p - a este primul simbol al membrului doi dintr-o producie; u - a este ultimul simbol al membrului doi dintre toate regulile de producie cu acelai membru stng; x - producia curent este ultima din irul produciilor cu acelai membru stng;11

L - legtura spre capul urmtoarei subliste asociat regulii de producie cu acelai membru stng; c:= dac p atunci {dac x atunci 0 altfel L} altfel {dac u atunci 0 altfel -1} d - pointer sau ntreg dac a este ultimul simbol al membrului drept al unei producii atunci d:=0 altfel d este pointer spre urmtorul nod al sublistei. Pentru gramatica dat n problem avem urmtoarea reprezentare:

12

3) tabelar cu notaiile de la reprezentarea prin list ramificat obinem: a 1 2 3 4 5 6 7 8 9 10 A B a A b a b c B c B 3 8 0 3 0 0 0 0 8 0 c 0 0 6 -1 -1 0 0 10 -1 0 D 2 0 4 5 0 7 0 9 0 0

1.1.8. a) Gramatici care genereaz limbajul {a, a3, a5, ... }: G = ({S}, {a}, P, S) cu P ={SaSa | a} sau P = {SaaS | a} sau P = {SSaa | a} etc. b) Pentru limbajul {a2,a4,...} avem gramaticile: G = ({S}, {a}, P, S) cu P={SaSa | aa} sau P={SaaS | aa} sau P={SSaa | aa}. 1.1.9. Vom da mai multe gramatici care genereaz acest limbaj: a) G1 = ({S}, {x,y}, P, S) cu P = { S xSy | xy };13

Demonstrm c L(G1)=L prin dubl incluziune: " " este imediat: Fie w=xnyn, n>0, deci wL; Folosind producia S xSy de n-1 ori avem:

S = > x n -1Sy n -1 ;*

n -1

Folosind a doua producie (S xy) obinem: xn-1Syn-1 => xnyn, deci S = > x n y n i cu alte cuvinte wL(G);

" ". Demonstraia acestei incluziuni, revine la stabilirea faptului c gramatica G1 genereaz numai cuvinte de forma xnyn. Pentru a demonstra acest lucru s considerm propoziia "Folosind de n ori produciile gramaticii G1, se obin numai secvene de forma xnSyn respectiv xnyn". Aceast propoziie se demonstreaz uor prin inducie matematic. De aici rezult c este adevrat incluziunea "". b) G2 = ({S,A}, {x,y}, P, S) cu P = {S xAy, xA xxAy, A }. c) G3 = ({S,B}, {x,y}, P, S) cu P = {S xBy, By Byy, B }. d) G4 = ({S,A,B}, {x,y}, P, S) cu P={S xA, A By, B S | } sau P = {S xA | xy, A By, B S}. e) G5 = ({S,A,B}, {x,y}, P, S) cu P = {S By, BxA, AS | } sau P = {S By | xy, B xA, A S}. Se observ c gramaticile G1, G4, G5, sunt independente de context (de tipul 2 dup Chomsky) iar G2 i G3 sunt dependente de context (tipul 1). 1.1.10. G = (N, , P, S) N = {S,B}, = {a,b,c}; P = {S aSBc | abc, cBBc, bBbb} Numerotm produciile: 1. S aSBc; 2. S abc; 3. cB Bc; 4. bB bb. Vom da cteva explicaii: - folosind prima producie {SaSBc} de n-1 ori se obine secvena an-1S(Bc)n-1; - folosind apoi producia a 2-a obinem dup nc o derivare secvena n a bc(Bc)n-1; - n continuare se folosete a 3-a producie de 1+2+...+n-1 ori pentru a obine anbBn-1cn; - se folosete n final ultima producie de n-1 ori i se obine anbncn. Exemplu: s ncercm s obinem cuvntul a4b4c4:14

S = > aSB c= > a aSB c B = > a 2 aSB c B c B= c> a 4 b c B ccBB = > a 4 b c B BB c c= > c c c1 1 1 2 3 3

a 4 bcBB cBcc = > a 4 bcBBBccc = > a 4 bBcBBc 3 = > a 4 bBB cBc 3 = > a 4 bBBBc = >3 3 3 3 4

4

a b bBBc = > a bb bBc = > a b c .4 4 4 4 4 4 4 4 4

Am scris sub notaia de derivare numrul produciei folosite i am subliniat membrul stng al fiecrei producii folosite. S remarcm, n finalul rezolvrii, c se pot da i alte gramatici care genereaz limbajul cerut: 1) o gramatic cu produciile oarecum simetrice fa de gramatica anterioar: G = (N, , P, S) N = {S,B}, = {a,b,c}, P = {SaBSc | abc, Ba aB, Bb bb}. 2) o gramatic cu mai multe neterminale i producii: G = (N, , P, S) N = {S,B,C}, = {a,b,c}, P = {SaBSC | aBC, CB BC, bC bc, cC cc, aB ab, bB bb}. 1.1.11. Vom da dou gramatici echivalente bazate pe ideea de la problema precedent: a) G = (N, , P, S) N = {S,B,C}, = {a,b,c,d}, P = {SaSBCd |aBCd, dBBd, dCCd, CBBC, bBbb, cCcc, aBab}. b) G = (N, , P, S) N = {S,B,C,D}, = {a,b,c,d} P = {SaSBCD | aBCD, DBBD, CBBC, aBab, bCbc, cDcd, bBbb, cCcc, dDdd}. 1.1.12. G = (N, , P, S) cu N = {S,B,C,D,E}, ={a,b,c,d,e}, Produciile sunt: SaSBCDE | aBCDE EBBE, ECCE, aBab, cCcc, cDcc, dEde, DBBD, DCCD, bBbb, bCbc, dDdd, eEee, CBBC, EDDE. 1.1.13. Gramaticile construite sunt dependente de context. a)G = (N, , P, S}15

N = {S,A,B,C,D}, = {a,b}, P = {SCD, CaCA | bCB, ADaD, BDbD, AaaA, AbbA, BaaB, BbbB, C , D }. C=marcator central al cuvntului; D=marcator drept al cuvntului;C -produciile cu membrul stng C genereaz de fapt secvene de forma w WD (unde W este oglinditul lui w dar cu litere mari, adic dac w=abb atunci W = B A ) dup B care C se nlocuiete cu . -secvena W trebuie inversat, neterminalul de la sfritul su se nlocuiete cu terminalul corespunztor (folosind produciile ADaD sau BDbD) i acesta se deplaseaz spre stnga la locul su (folosind produciile AaaA, AbbA, BaaB, BbbB); -cnd toate neterminalele au ajuns pe rnd lng D cuvntul dorit a fost generat n stnga lui D, iar acesta se nlocuiete cu .

Exemplu: x=ww, unde w=abb, deci x=abbabb. Avem:S = > CD = > aCAD = > abCBAD = > abbCBBAD = > abbBBAD = > abbBBaD = > abbBaBD1 2 3 3 10 4 8

= > abbaBBD = > abbaBbD = > abbabBD = > abbabbD = > abbabb . 8 5 9 5 11

(Am numerotat produciile n ordinea scrierii lor n mulimea P). b) G = (N, , P, S} N = {S,A,B,C,D,E}, = {a,b}, P = {SCD, CaCA | E, EbEB | bB, ADaD, BDbD, AaaA, AbbA, BaaB, BbbB, D }; -vezi a) n care w=ambn. Exemplu: x=aabaab. Avem:S = > CD = > aCAD = > aaCAAD = > aaEAAD = > aabBAAD = > aabBAaD = > aabBaAD1 2 2 3 5 6 8

= > abbaBBD = > abbaBbD = > abbabBD = > abbabbD = > abbabb . 8 5 9 5 11

(Am numerotat produciile n ordinea scrierii lor n mulimea P).16

c) G = (N, , P, S} N = {S,A,B,C,D,X}, = {a,b}, P = {SCD, CaCA | bCB | X, XaX | bX | , ADaD, BDbD, AaaA, AbbA, BaaB, BbbB, D }; -vezi a) cu modificarea c C-ul dup ce i-a ndeplinit rolul de mijloc al cuvntului va genera prin trecerea n X o secven oarecare de simboluri a,b. 1.1.14. a) G = (N, , P, S}, N = {S,A,B,C}, = {a}, P = { SBAB, BABC, CAAAC, CBAAB, Aa, B }. Practic de la forma propoziional BAB se nlocuiete A cu doi de A cu ajutorul lui C trecndu-l pe acesta de la stnga la dreapta. Se ajunge la forma propoziional BAAB de unde se poate ajunge la: 1o) cuvntul aa folosind ultimele dou producii; 2o) sau la forma propoziional BAAAAB folosind produciile: BABC, CA>AAC, CB>AAB. Procesul se poate continua pentru a obine orice cuvnt din limbajul cerut. Evident c exist i o alt gramatic cu produciile simetrice care genereaz acelai limbaj: P = { SBAB, ABCB, ACCAA, BCBAA, Aa, B }. sau a) G = (N, , P, S} N = {S,A,B,C}, = {a}; P = {SBAB, BABC, CAAAC, CBAAB, Aa, B }. -B=marcatori de stnga i dreapta ai cuvntului; -A-ul cel mai din stnga e nlocuit cu C (s-a pierdut temporar un A); -C parcurge de la stnga la dreapta irul de A-uri i transform fiecare A n AA; -cnd C-ul ajunge la marginea dreapt se reface A-ul pierdut prin AA. exemplu: w=a4

S = > B A B > B C B > B A A =B> B C A =B> B A A C= B B A A A A > A A A A=B> = = > =B1 2 4 2 3 4 6 5

aAAAB = > aaAAB = > aaaAB = > aaaaB = > aaaa.5 5 5 6

(Am numerotat produciile n ordinea scrierii lor n mulimea P). b) Folosind aceeai idee de la punctul a) obinem: G = (N, , P, S} N = {S,A,B,C}, = {a}, P = {SBAB, BABC, CAAkC, CBAkB, Aa, B }.17

1.1.15. a)Dm dou gramatici echivalente: G1 = ({E}, {a}, P, E) cu P = {EE+E | E*E | (E) | a} i G2 = ({E,T,F}, {a}, P, E) cu P = {EE+T | T, F (E) | a, TT*F | F}. b)Analog dou gramatici echivalente: G3 = ({E}, {a}, P, E) cu P = {EE+E | E-E | E*E | E:E | (E) |a} i G4 = ({E,T,F}, {a}, P, E) cu P={EE+T | ET | T, TT*F | T:F | F, F (E) | a}. 1.1.16. G = ({S,H}, {a,b,c,d}, P, S) cu P = {SaaSd | X, XbXcc | bc}. 1.1.17. a) Ideea folosit este urmtoarea: considerm cuvintele formate din dou secvene. Prima secven anbn iar a doua cmdm apoi vom concatena cele dou secvene. Practic avem gramatica: G1 = ({S,X,Y}, {a,b,c,d}, P, S) cu P = {SXY, XaXb | ab, YcYd | cd}. Neterminalul X genereaz secvenele anbn, iar neterminalul Y genereaz secvenele cmdm. b) Relund ideea de la punctul a) avem gramatica: G2 = ({S,X,Y}, {a,b}, P, S) cu P = {SXY, XaSb | ab, YaYb | ab}. 1.1.18. Folosind ideea de la problema 1.1.17. avem gramatica: G = ({S,X,Y}, {a,b,c,d,e}, P, S) cu P = {SXY, XaSBc | abc, cBBc, bBbb, YdYe | de}. 1.1.19. a)G = (N, , P, S), N = {S,A,B}, = {a,b,c} P = {SaSBc | A, cBBc, bBbb, aBab, AaAb | }. exemplu: fie w=a3b3cS = > aSBc = > aABc = > aaAbBc = > aaaAbbBc = > a 3 bbBc = > a 3 b 3c 3 .1 2 6 6 7 4

(Am numerotat produciile n ordinea scrierii lor n mulimea P). Prima producie genereaz formele propoziionale de forma akS(Bc)k. Produciile numerotate cu 2 i 6 asigur multiplicarea akbk i astfel ne asigurm c n m. Producia a 3-a interschimb c cu B. Produciile 4 i 5 transform neterminalele B n b. Producia a 7-a ajut la tergerea lui A. Se poate demonstra uor c nu se genereaz i alte cuvinte dect cele cerute n enun.18

b) G = (N, , P, S), N = {S,B,C}, = {a,b,c}, P = {SaSBc | C, aBab, cBBc, bBbb, CCc | }. exemplu: fie w=a2b2c4S = > aSBc = > a 2SBcBc = > a 2 CBcBc = > a 2 CcBcBc = > a 2 CccBcBc = > a 2 b 2 c 41 1 2 6 6 +

(Am numerotat produciile n ordinea scrierii lor n mulimea P). Idea folosit este asemntoare cu cea folosit la punctul a). Produciile 2 i 6 permit s obinem relaia m n. c) G = (N, , P, S), N = {S,A,B,X}, = {a,b,c}, P = {SaSBc | X, cBBc, bBbb, aBab, XaXb | A, AaA | }. exemplu: fie w=a3b2cS = > aSBc = > aXBc = > aaXbBc = > aaAbBc = > a 3 AbBc = > a 3 bBc = > a 3 b 2 c.1 2 6 7 8 9 4

(Am numerotat produciile n ordinea scrierii lor n mulimea P asemntor punctului a). d) G = (N, , P, S), N = {S,B}, = {a,b,c}, P = {SaSBc | aSBcc | , aBab, cBBc, Bcbc, bBbb} exemplu: fie w=a2b2c3 S = > aSBc = > aaSBccBc = aaBccBc = > aabccBc = > a 2 bcBcc = > a 2 bBccc = > a 2 b 2 c 3 .1 2 3 6 5 5 7

(Am numerotat produciile n ordinea scrierii lor n mulimea P asemntor punctului a). 1.1.20. a) G = (N, , P, S} N = {S}, = {a,b,c}, P={SaSc | cSa | bSc | cSb | SS | }; Primele dou producii permit ca atunci cnd n forma propozitional se introduce un a s se introduc i cte un c n orice ordine. Produciile 3 i 4 permit ca atunci cnd n forma propozitional se introduce un b s se introduc i cte un c n orice ordine. Producia a 6-a permite eliminarea lui S. Exemplu: w=acbc.S = > aSc = > acSbc = > acbc.1 4 6

(Am numerotat produciile n ordinea scrierii lor n mulimea P). b) G = (N, , P, S} N = {S,A,B,C}, = {a,b,c},19

P = {SASBC | , ABBA, BAAB, ACCA, CAAC, CBBC,BCCB, Aa, Bb, Cc}. exemplu: w=cba.S = > ASBC = > ABC = > BAC = > BCA = > CBA1 2 3 5 8 9 ,10 ,11 +

= > cba .

(Am numerotat produciile n ordinea scrierii lor n mulimea P). 1.1.21. c) Demonstrm prin dubl incluziune egalitatea celor dou mulimi mergnd pe echivalene: xL1/(L2L3) yL2L3 a.. xyL1 y2L2 i y3L3 a.. xy2y3L1 y2L2 i xy2L1/L3 x(L1/L3)/L2.

1.2. AUTOMATE FINITE1.2.1. Automate finite deterministe (AFD), automate finite nedeterministe (AFN) Un automat finit (acceptor) este un ansamblu M = (Q, , , qo, F) n care: - Q este o mulime finit i nevid de elemente numite stri; - este o mulime finit i nevid numit alfabet de intrare; - : QxP(Q) este o aplicaie numit funcie de tranziie; - qoQ, qo este stare iniial; - F Q, F este o mulime nevid numit mulimea strilor finale. Observaie. n definiia de mai sus P(Q) este mulimea tuturor prilor (submulimilor) lui Q. Deci, n particular, P(Q) i QP(Q). Apoi, qQ, a avem (q,a)=Q1Q. Fie M un automat finit (AF). Dac qQ, a avem |(q,a)| 1 atunci automatul M se numete automat finit determinist (AFD), iar n caz contrar automatul se numete automat finit nedeterminist (AFN). Dac qQ, a avem |(q,a)| =1, atunci automatul finit M se numete automat finit determinist complet (total) definit. n acest caz avem ntotdeauna qQ, a (q,a) = {p}, pQ. Observaii:1o. Fie M=(Q, , , qo, F) un AFD. Avem acelai automat i dac funcia de tranziie :QxP(Q) se nlocuiete printr-o funcie parial definit pe Qx de forma: ':QxQ unde qQ, a avem ' (q, a) = , daca (q, a) = . p, daca (q, a) = {p}

20

2o. Dac M este un AFD complet definit atunci evident funcia de tranziie ' menionat la 1o va fi i ea complet definit. 3o. ntotdeauna i invers, de la funcia ' definit la 1o se poate trece la .

1.2.2. ReprezentareUn automat finit poate fi reprezentat sub form de tablou sau sub forma unui graf orientat. Astfel, tabloul alturat ne furnizeaz toate elementele care definesc un automat finit M=(Q,,,qo,F), unde Q={qo,...,qn}, ={a1,...,am} i n care se consider:

1, daca q i F zi = . 0, altfel

O alt reprezentare asociat automatului M = (Q, , , qo, F), este graful orientat cu noduri i arce etichetate astfel: - mulimea vrfurilor se eticheteaz cu stri, elemente ale lui Q; - starea iniial se reprezint printr-un nod de forma:

- starile finale (deci qF) se reprezint prin noduri de forma:-

dac (p,a)q atunci avem arcul, (p,q) care se eticheteaz cu a, adic:

21

1.2.3. Configuraii i relaii de tranziieFie M = (Q, , , qo, F). Mulimea configuraiilor acestui automat este format din Qx*. Pe mulimea configuraiilor automatului finit M se definesc relaiile binare:

k + *

tranziia direct; k tranziia; + tranziia; * tranziia.

Avem (p,aw) (q,w) (p,a)q; p,qQ, a, w*. Apoi (p,w1) (q,w2) dac i numai dac de la prima configuraie se poate ajunge la a doua configuraie folosind k tranziii directe; p,qQ; w1,w2*. ntre dou configuraii avem o "+ tranziie", dac i numai dac k>0 astfel nct ntre ele s avem o "k-tranziie", iar * (p,w1) (q,w2) p=q, w1=w2 adic (p,w1)=(p,w2) sau (p,w1) + k

(q,w2); p,qQ, w1,w2*.

Configuraia (qo,w) se numete configuraie iniial iar (q,), qF se numete configuraie final.

1.2.4. Limbaj acceptat de un AFLimbajul acceptat de automatul M = (Q, , , qo, F) este: T(M) = {w | w*, (qo,w) (q,),qF}. Dou automate M1 i M2 sunt echivalente dac ele accept acelai limbaj, adic T(M1) = T(M2). Automatele finite sunt o alt form de specificare a unor limbaje. Relaia de tranziie direct definete o micare a AF. Apoi, wT(M), dac i numai dac n graful22*

care definete automatul M, exist un drum de la starea iniial la o stare final i arcele sunt etichetate succesiv cu simbolurile cuvntului w.

1.2.5. FuncionareFuncionarea unui automat finit M = (Q,,,qo,F) se petrece n timp i este * definit de relaia . Funcionarea automatului finit M care la momentul de timp ti are configuraia (q,w), w = aw', presupune trecerea la momentul de timp t i+1 sau oprirea acestuia. n acest proces de trecere deosebim urmtoarele situaii: 1o micare, dac (q,aw') (p,w') adic (q,a) p, deci la momentul ti+1 are configuraia (p,w'); o 2 blocare, dac (q,a)=; * 3o staionare, dac (q,w) (q,w). La momentul iniial to configuraia automatului este (qo,w). Apoi, la funcionarea AF trebuie s avem n vedere c: - momentele de timp luate n considerare sunt discrete, adic operaiile acestor maini sunt sincronizate; - trecerea de la o stare la alta a AF nu se face ntmpltor; - automatul rspunde (trece eventual ntr-o nou stare) ntotdeauna unui simbol de intrare; - exist un numr finit de stri, iar la un moment de timp dat, AF se poate gsi ntr-o singur stare. O stare q a unui automat M = (Q, , , qo, F) este o stare inaccesibil dac i numai dac nu exist nici o secven w * astfel nct: (qo,w) (q,); n caz contrar starea q este accesibil. Automatul M poate fi transformat ntr-un AF echivalent, M',care s conin numai stri accesibile din starea iniial qo. Pentru determinarea lui M' = (Q', , ', qo, F') se poate folosi algoritmul: a) So={qo}, i:=0; b) Si+1 = Si {q | qQ, (p,a)q, pSi, a}; c) Dac Si+1 Si, atunci i := i+1, salt la b); d) Q' = S i +1 , F' = F S i +1 iar ' (q, a) = (q, a), q Q' , a . Fie M = (Q, , , qo, F). O stare qQ este o stare neproductiv dac i numai dac nu exist w* astfel nct:23*

(q,w) (p,), pF; n caz contrar starea q este o stare stare productiv. Automatul M poate fi transformat ntr-un AF echivalent, M', care s conin numai stri productive. Pentru determinarea lui M' = (Q', , ', qo, F') se poate folosi algoritmul: a) Ao=F, i:=0; b) Ai+1= Ai {ppQ, q(p,a), a, qAi}; c) dac Ai+1 Ai, atunci i := i+1, salt la b); d) Q' = A i +1 , F' = F, ' (q, a) = { p Q' | p (q, a) }, q Q' , a . Observaie: Dac qoQ' atunci T(M)=, adic automatul M nu accept nici o secven.

*

1.2.6. Echivalena dintre AFD i AFNTeorem. Fie M1 un automat finit (nedeterminist). ntotdeauna exist un automat finit determinist M2, astfel nct cele dou automate s fie echivalente, adic: T(M1) = T(M2). Construcia AFD. Se d M1 = (Q1, , 1, q0, F1). Atunci AFD echivalent cu M1 este M2 = (Q2, , 2, q 'o , F2) unde: Q2 = P(Q1), q 'o = {q0}, F2 = {S | SQ1, SF1 }, iar a i S Q1, S , avem unde 2 : Q2xQ2. 2 (S a) = 1 (q a), , ,q S

si 2 (a) = ,

Observaii. 1o.Funcia de tranziie 2 a AFD, M2, dat mai sus, este complet definit. 2o.Elementele Sk, k 0 (n numr finit) ale mulimii Q2 i valorile funciei 2 : Q2x Q2 care definesc automatul M2 se pot obine din automatul M1 i astfel: - S0 = {q0}, 2(S0,a) = 1(q0,a), a . - fiecare submulime 1(q,a) a lui Q1, dac este diferit de submulimile deja determinate se noteaz cu Si, i 1. - pentru fiecare nou stare Sk a automatului M2 se calculeaz: 2 (S k , a) = 1 (q, a), a ;q k S

aceast stare Sk este un candidat la mulimea strilor lui M2 n sensul precizat mai sus; procesul se termin cnd nu mai obinem stri noi;24

evident c F2 = {S | SQ2, SF1 }. 3o. Teorema de mai sus justific considerarea n continuare a automatelor finite deterministe complet definite, fr a avea o limitare a unor rezultate teoretice.

1.2.7. Minimizarea automatelor finiteFie automatul finit determinist (AFD) complet definit: M = (Q, , , qo, F). Dou stri distincte q1 i q2 din Q sunt difereniate de x, x*, dac n relaiile:(q 1 , x) (q 3 , ); (q 2 , x) (q 4 , ),* *

q3 i q4 nu aparin simultan lui F sau Q F, ori dac cel puin una din aceste relaii nu are loc. Dou stri distincte q1, q2 Q sunt k-difereniate de x, x* dac i numai dac au loc condiiile de mai sus i |x| k. Dou stri distincte q1, q2Q sunt echivalente dac i numai dac nu exist nici o secven care s le diferenieze; notm acest fapt prin q1 q2. Dou stri distincte q1, q2Q sunt k-echivalente dac i numai dac nu exist nici o secven x, |x| k care s le diferenieze; notm acest fapt prin:q1 q 2 .k

Observaie. Dac q 1 q 2 atunci q1 i q2 aparin simultan lui F sau lui Q - F. Lem. Fie M un AFD cu n stri. Strile q1 i q2 sunt echivalente dac i numai dac ele sunt (n-2)-echivalente. Observaie. Avem

0

... .

n 2

n -3

1

0

Un AFD este un automat redus dac nu conine stri inaccesibile, stri neproductive i nu conine perechi de stri distincte echivalente. Teorem. Oricare ar fi un automat finit M1, ntotdeauna exist un automat finit redus M' astfel nct: T(M1) = T(M').

1.2.8. Construcia AFD redus25

Se d M1 = (Q1, , 1, q 'o , F1). - Transformm acest automat, ntr-un AFD fr stri inaccesibile i neproductive (vezi algoritmii anteriori); notm automatul astfel obinut M=(Q, , , qo, F); 0 1 - Construim relaiile de echivalen , , . . . i folosim lema enunat mai sus; - Automatul redus M = (Q, , , q 'o , F ) are: - Q' = Q/ mulimea claselor de echivalen; notm clasa care conine starea p astfel: [p]. - ' ([p],a) = [q] dac (p,a) = q; - q 'o = [q0] ; - F = {[q] | qF}. Teorem. Automatul redus are numrul minim de stri, dintre toate automatele deterministe echivalente.

1.2.9. Automate finite cu -micriUn AFN cu -micri este un ansamblu M = (Q, , , qo, F) ale crui componente au aceleai semnificaii ca la un AF oarecare, doar c funcia de tranziie este definit astfel: : Qx ( { }) P(Q). Avem o -tranziie ntre dou configuraii (p,w) (q,w) dac i numai dac (p,)q; pQ, qQ, w*; adic n reprezentarea grafic avem o legtur de urmtoarea form:

ntr-un AFN cu -micri se pot pune n eviden printr-un procedeu analog cu cel de la observaia 2o de mai sus, toate strile accesibile dintr-o stare q, folosind numai -tranziii. Teorem. Dac L este un limbaj acceptat de un AFN cu -micri, M1, ntotdeauna exist un AFN fr -micri, M2, echivalent cu M1, adic: L = T(M1) = T(M2).

1.2.10. Probleme propuse1.2.1. S se reprezinte tabelar urmtoarele AF:

26

1.2.2. S se reprezinte sub form de graf urmtoarele AF: a) M = ({p,q,r}, {a,b}, , p, {p}) A p Q q R r P b p 1 p 0 r 0

b) M = ({p,q,r,t}, {a,b,c}, , p, {q,r}) a p q q p r t t q B P T R p c r p p q 0 1 1 0

1.2.3. S se reprezinte sub form de graf automatul finit: M = (Q, , , qo, {qo}) unde Q = {qo,q1,q2,q3}, ={0,1}, iar funcia :QxQ este dat de tabloul urmtor: qo 0 q2 1 q127

q1 q2 q3

q3 q0 q1

qo q3 q2

Verificai apoi pe graful obinut c: a) secvenele 1010, 1100 sunt acceptate de automat; b) secvena 1011 nu este acceptat de automat. 1.2.4. S se construiasc AF care accept limbajul L definit peste alfabetul {0,1} i care are proprietatea c orice cuvnt al limbajului conine cel puin dou zerouri consecutive. 1.2.5. S se construiasc automatul finit care accept limbajul: L={0n1m | n 0, m 1} {1n0m | n 0, m 1}. 1.2.6. S se construiasc automatele care accept limbajele: a) L1={0(10)n | n 0}; b) L2={1(01)n | n 0}; S se precizeze apoi, automatul redus care accept limbajul L1L2. 1.2.7. S se construiasc automatele care accept urmtoarele limbaje (peste {a,b}*) descrise narativ: a) L1 format din secvene care conin un numr par de a-uri i numr par de b-uri; b) L2 format din secvene care conin un numr par de a-uri i numr impar de b-uri; c) L3 format din secvene care conin un numr impar de a-uri i numr par de b-uri; d) L4 format din secvene care conin un numr impar de a-uri i numr impar de b-uri; 1.2.8. S se construiasc automatele care accept urmtoarele limbaje (peste {a,b,c}*) descrise narativ: a) L1 format din secvene care conin un numr par de a-uri i numr par de b-uri; b) L2 format din secvene care conin un numr par de a-uri i numr impar de b-uri; c) L3 format din secvene care conin un numr impar de a-uri i numr par de b-uri; d) L4 format din secvene care conin un numr impar de a-uri i numr impar de b-uri; 1.2.9. S se construiasc automatele care accept urmtoarele limbaje (peste {a,b,c}*) descrise narativ: a) L1 format din secvene care conin un numr par de a-uri, b-uri i c-uri; b) L2 format din secvene care conin un numr par de a-uri i b-uri i un numr impar de c-uri; c) L3 format din secvene care conin un numr impar de a-uri i un numr par de b-uri i c-uri ;28

d) L4 format din secvene care conin un numr impar de a-uri b-uri i c-uri; 1.2.10. S se construiasc automatele M care accept urmtoarele limbaje: a) T(M)={w1aaw2 | w1{b,ab}*, w2{a,b}*}; b) T(M)={w1aaaw2 | w1, w2{a,b}*}; c) T(M)={1n0m1u | n 0, m 1, u{0,1}*}; d) T(M)={0n1m0q | n,m,q 1}; e) T(M)={0n1m0q | n,m 1, q 0}; 1.2.11. S se construiasc automatele M care accept urmtoarele limbaje: a) T(M) = {w | w{b,ccc}*}; b) T(M) = {c3n | n 1}; c) T(M) = {a,bc}*; d) T(M) = {bc, c, d}*; e) T(M) = {0(10)n01m | n 0, m 0} {(10)n01m | n 1, m 0} cu cel mult 4 stri; 1.2.12. Se d automatul finit nedeterminist reprezentat mai jos:

S se construiasc AFD echivalent. 1.2.13. Fie Li de secvene acceptate de automatele finite deterministe M i = (Q i , , i , q , Fi ) unde i: QixQi; i=1,2. 0 0 Fie M = (Q1xQ2, , , qo, F) unde ((p,q),a) = ( 1(p,a), 2(q,a)) iar q 0 = (q 1 , q 2 ), F = {(p,q) | pF1 i qF2}. Artai c T(M)=L1L2.0 i

mulimea

1.2.14. Fie Li

de secvene acceptate de M i = (Q i , , i , q , Fi ) unde i: QixQi, i=1,2 .0 i

mulimea

automatul

finit

determinist

29

0 0 Fie M = (Q1xQ2, , , qo, F) unde ((p,q),a) = ( 1(p,a), 2(q,a)) iar q 0 = (q 1 , q 2 ), F = {(p,q) | pF1 sau qF2}. Artai c T(M)=L1L2.

1.2.15. S se construiasc automate care accept urmtoarele limbaje: a) numerele ntregi definite n limbajele C i PASCAL; b) numerele reale definite n limbajele C i PASCAL; c) declaraiile tablourilor n C; d) declaraiile tablourilor n PASCAL; 1.2.16. S se construiasc un automat finit peste alfabetul {0,1,...,9} care s accepte numai cuvinte cu proprietile: -primul caracter este 0; -al i-lea caracter este o cifr mai mare sau egal dect oricare din cele i-1cifre anterioare. 1.2.17. S se construiasc automate finite care accept limbajele urmtoare: a) mulimea cuvintelor peste alfabetul {a,b} n care orice dou a-uri sunt separate printr-o secven de lungime 4k, k > 0 de simboluri b. b) mulimea cuvintelor peste alfabetul {0,1} cu cel mult dou zerouri consecutive i cel mult dou 1-uri consecutive. c) mulimea cuvintelor peste alfabetul {0,1} n care orice pereche de 0-uri alturate apare naintea oricrei perechi de 1 alturate. d) mulimea cuvintelor peste alfabetul {a,b} a cror lungime este divizibil cu trei. e) mulimea cuvintelor care ncep cu 1 i reprezint scrierea n binar a tuturor numerelor divizibile cu cinci. f) mulimea cuvintelor peste alfabetul {a,b,c} care au aceeai valoare cnd le evalum de la stnga la dreapta ca i de la dreapta la stnga conform urmtoarei tabele de operaii: a a a b c c b b a a c c c b a

1.2.18. S se construiasc automatele finite care accept numai cuvinte peste alfabetul {a,b,c} cu proprietatea c:30

a) simbolul cu care se termin cuvntul mai apare cel puin o dat n cuvnt; b) simbolul cu care ncepe cuvntul este acelai cu cel cu care se termin cuvntul; c) simbolul cu care ncepe cuvntul mai apare cel puin o dat n cuvnt; d) exist un simbol n cuvnt care mai apare cel puin o dat n cuvnt. 1.2.19. Cte limbaje diferite definite peste alfabetul {0,1} sunt acceptate de toate automatele finite cu dou stri dac: a) ele sunt deterministe; b) ele sunt nedeterministe;

1.2.11. Indicaii i soluii1.2.1. a) Automatul este complet definit iar reprezentarea tabelar este urmtoarea: Q a b P q p 0 Q p p 1 b) c) i d) se reprezint analog. 1.2.2. a) graful de tranziie este urmtorul:

Limbajul acceptat de automat este T(M)= {{b,ab,a2bna}*, n 0}. 1.2.3. Avem urmtorul graf de tranziie:

31

a) De la qo la qo exist drumuri cu arcele etichetate 1010 respectiv 1100; b) Nu exist drum de la qo la qo cu arce etichetate n ordinea 1011. 1.2.4. Dm reprezentarea automatului prin graful de tranziie:

1.2.5. Dm reprezentarea automatului prin graful de tranziie:

1.2.6.

Limbajul L1L2 este acceptat de automatul de mai jos:

32

1.2.7. Vom rezolva doar acest punct deoarece pentru a obine celelalte automate se modific doar mulimea strilor finale ale automatului urmtor:

a) F = {p}; b) F = {t}; c) F = {q}; d) F = {r}. 1.2.8. i 1.2.9. Vezi problema 1.2.7., grafurile vor fi spaiale de forma unui cub. muchiile sale fiind etichetate cu simbolurile a, b, c. 1.2.10. Vom rezolva doar punctul a), graful de tranziie al automatului care accept limbajul este:

1.2.11. Vezi problemele 1.2.5. i 1.2.6. 1.2.12. Avem M = (Q, , , qo, F) unde Q = {qo, q1, q2}, = {0,1}, F = {q2}, :QxQ funcia de tranziie corespunztoare.Vom nota cu M = (Q, , , q0, F) AFD astfel nct: T(M) = T(M'). Construcia lui M' se face considernd: Q ' =P(Q q '0 ={q '0 }, F ' ={S | S Q SF , ':Q'xQ' cu ), , }

, '(S,a) = {p | pQ, qS, a, (q,a)p} = q (q a) . S Se poate ns considera ca mulime a strilor automatului M', mulimea Q P(Q) construit pornind de la submulimea {q0}, cci altfel ar trebui s considerm |P(Q)|= 2|Q| elemente. Avem deci So = {qo}; '(So,0) = {q1} = S1; '(So,1) = {q2} = S2; '(S1,0) = {q1,q2} = S3; '(S1,1) = {q1} = S1;33

'(S2,0) = {q2} = S2; '(S2,1) = {q1,q2} = S3; '(S3,0) = {q1,q2} = S3; '(S3,1) = {q1,q2} = S3; Astfel, Q/ = {So,S1,S2,S3}, F/ = {S2,S3} Reprezentarea grafului de tranziie este urmtoare:

1.2.15. a) Vom da graful de tranziie al automatului ce accept numerele ntregi:

1.2.16. M = (Q, , , qo, F) unde: Q = {qo, q1, . . . , q10}, = {0, 1, ..., 9}, F = Q \ {qo} Funcia de tranziie este definit astfel: (qo, 0) = q1; (qi, i-1) = qi, i=1, . . . , 10; (qi, j) = qj+1, i=1, . . . , 9, j=i, . . . , 9; nu este definit n restul cazurilor. Dac = {0,1,2,3} atunci avem graful de tranziie:

34

1.2.17. a) Vom da rezolvarea sub forma unui graf de tranziie:

1.3. EXPRESII REGULAREFie un alfabet. Mulimile regulare peste se definesc recursiv astfel: 1) este o mulime regular peste ; 2) { } este o mulime regular peste ; 3) Oricare ar fi a, {a} este mulime regular peste ; 4) Dac P i Q sunt mulimi regulare peste , atunci mulimile: P Q, PQ, i P* sunt, de asemenea mulimi regulare; 5) Orice alt mulime regular se obine aplicnd de un numr finit de ori regulile 1)4). Fie un alfabet. Definim recursiv expresiile regulare i mulimile regulare reprezentate de acestea, astfel: 1) este o expresie regular reprezentnd limbajul ; 2) este o expresie regular reprezentnd limbajul { }; 3) Dac a, atunci a este expresie regular reprezentnd limbajul a; 4) Dac p i q sunt expresii regulare reprezentnd limbajele P i Q atunci: (p+q) este expresie regular reprezentnd limbajul P Q;35

(pq) este expresie regular reprezentnd limbajul PQ; p* este expresie regular reprezentnd limbajul P*; 5) Orice alt expresie regular se obine aplicnd de un numr finit de ori regulile 1) -4). Observaii. 1o. Se constat imediat c expresiile regulare peste alfabetul sunt secvene obinute prin concatenare de simboluri din alfabetul {, , +, *, (, )}; 2o. Limbajele asociate expresiilor regulare sunt mulimi regulare; 3o. De multe ori simbolul "+" n scrierea expresiilor regulare se nlocuiete cu "|"; 4o. Orice expresie regular peste alfabetul reprezint un limbaj regular peste alfabetul . o 5 . Au loc urmtoarele identiti (se pot demonstra): a) b) c) d) e) r+s = s+r; (r+s)+t = r+(s+t); (rs)t = r(st); r(s+t) = rs+rt; (r+s)t=rt+st; f) * = ; g) (r*)* = r*; h) (+r)* = r*; i) r+ = +r = r; j) r = r=; k) (r*s*) = (r+s)*; l) r*+ = +r*=r*; m) r=r =r

Dou expresii regulare sunt egale dac limbajele reprezentate de acestea sunt egale. Teorem. Dac r este o expresie regular, atunci exist un AFN care accept limbajul reprezentat de aceast expresie regular i reciproc. Construcia. Se construiete AFN cu -micri din aproape n aproape dup urmtorul procedeu: Expresia AFN Observaii regular

a, aE xpresia regulara a reprezinta lim bajul {a} care este acceptat de acest autom at

36

p+qf 1 si stari stare f2

nu vor m ai

fi

finale; noua finala q f , iar

noua star e initiala este qo

f 1 nu mai este stare finala noua stare initiala ramane q1 , noua star e finala f 2 pq f 1 nu mai este stare finala; noua stare initiala este qo , noua star e finala

p* AFN cu -micri astfel obinut se poate transforma ntr-un AFN fr -micri. Invers, dac se d un AFD, M, determinarea expresiei regulare ce reprezint limbajul acceptat de acest automat se poate face prin dou metode: 1) Fie M = ({q1,q2,...,qn}, , , q1, F) Se noteaz cuk R ij = { | (q i , ) (q j , ) [, = , 0 aB | (A,a)B} {A>a | (A,a)B, BF}.

47

1.4.2. Proprieti de nchidere ale limbajelor regulareTeorem. Dac L1, L2 sunt limbaje regulare peste alfabetul , atunciL1 L2 , L1 L2 , L1 L2 ,n * L1 = L1 , n 0 * L1 = - L1 ,

sunt limbaje

regulare. Construcia. Fie automatele: L2=T(M2)., ,, M1 = ( Q1 , , 1 , q o , F1); M 2 = ( Q2 , , 2 , q o , F2 ) ; cu

L1=T(M1),

a) Automatul care accept limbajul L1 L 2 este M = (Q, , , q, F) unde:Q = Q1 Q2 { q o }, q o Q1 Q2 ;

F1 F2 , daca L1 L 2 F= ; {q}, daca L1 L 2 F1 F2 , ( q o , a) = 1 (q,o , a) 2 (q,o , a), ; a

( q, a ) , daca q Q1 ( q, a ) = 1 2 ( q, a ) , daca q Q 2

b) Automatul care accept limbajul L1L2 este M = (Q, , , qo, F) unde:Q = Q1 Q2 ;qo = qo ;F F 2 , d a c a = F F 1 2 , q d a c a" 0

,

F 2 ; q " F 2 0

q (,

q ) aa q 1 Q 1 ( , a, d c a = 1 ( , a ( " , a, d c ) q ) q0 ) aa ( , a, d c aa q 2 Q 2 q )

c) Automatul care accept limbajul L* este M = (Q, , , qo, F) unde: 1Q = Q1 { q o } ; F = F1 { q o} ;( q o , a) = 1 (q,o , a) ;

48

1 ( q a, ) ,d a c qa Q1 - F1 ( qa ,)= . " 1 ( qa, ) 1 ( q0 , a )d a c qa F1d) Automatul care accept limbajul L1 = * - L 1 are n vedere faptul c automatul M1 care accept limbajul L1 trebuie s aib proprietatea: (s,a)=1, (s,a)Qx, adic s fie total definit. Atunci automatul care accept limbajul L1 notat M = (Q, , , qo, F) are Q=Q1,, q o = q o , = 1 , F = Q - F1 .

Observaie. Dm o metod de a construi automatul M1 total definit echivalent cu M de la punctul d): Fie M = (Q, , , qo, F) atunci automatul total definit echivalent cu M este: , , M1 = ( Q1 , 1 , q o , F1) astfel ca T(M) = T(M1), i are Q1 = Q {k}, F1 = F iar funcia 1: Q1x P(Q1), este definit astfel: (q, a), daca | (q, a) | 0 1 (q, a) = {k}, daca | (q, a) | = 0 q Q, a .

1 (q, k) = {k}, a .

Deci, pentru simbolurile a pentru care nu exist arce corespunztoare dintr-o stare q se construiesc arce spre k (o stare nou introdus); totodat avem bucl pe k, a; starea k va fi neproductiv. e) Pentru construirea automatului care accept limbajul L1 L 2 se ine seama de relaiaL1 L 2 = L1 L 2 .

Exist i alt metod: considerm automatele care accept cele dou limbaje, , M1 = ( Q1 , 1 , q o , F1), M 2 = ( Q2 , 2 , q o , F2 ), ,,

care sunt deterministe i total definite cu I :Qix Qi; i=1,2. Atunci automatul M cu proprietatea c T( M1) T( M 2 ) = T(M) este M = (Q1 xQ 2 , , , (q,o , q,o, ), F1 xF 2 ) unde (( p1 , p2 ), a) = (1 ( p1 , a), 2 ( p2 , a)) , p1 Q1 , p2 Q2 . a

1.4.3. Lema de pompare pentru limbaje regulare

49

Propoziie . Dac L este un limbaj regular, atunci exist un numr natural p astfel nct, orice cuvnt wL de lungime cel puin p (w p) s aib o descompunere de forma w=xyz, unde 0 Abb = > Aabb = > Aaabb = > aaabb1 4 5 5 6

Conform regulilor de transformare de mai sus se pot obine urmtoarele producii: - din (1) (SBb)P se obine (Bb)P' (1') - din (2) (SAb)P se obine (Ab)P' (2') - din (3) (BBb)P se obine (BbB)P' (3') - din (4) (BAb)P se obine (AbB)P' (4') - din (5) (AAa)P se obine (AaA)P' (5') - din (6) (Aa)P se obine (SaA)P' (6') w se va genera de la stnga spre dreapta astfel:

S = > aA = > aaB = > aaaA =' > aaabB = > aaabb ' ' ' '6 5 5 4 1

53

Ordinea aplicrii produciilor corespunztoare din cele dou gramatici pentru generarea aceluiai cuvnt este invers. 1.4.4. Dac L este regular atunci exist o gramatic regular G = (N, , P, S) care l genereaz i are numai producii de forma AaB, Aa, S . Construim gramatica G' = (N, , P', S) cu produciile P' = {ABa | (AaB)P} {Aa | (Aa)P} {S | (S)P}. Se demonstreaz uor c aceast gramatic genereaz L , iar conform problemei ~ precedente aceast gramatic este regular, deci limbajul generat de ea L , este regular. 1.4.5. Dac L este regular atunci exist un automat finit M = (Q, , , q0, F) fr stri inaccesibile i neproductive care l accept. a) construim un automat M' din automatul M astfel nct toate strile automatului M vor deveni n M' stri finale M' = (Q, , , q0, F'), F'=Q M' va accepta limbajul format din mulimea prefixelor (nu neaprat proprii) cuvintelor limbajului L. b) construim un automat M" care accept reuniunea tuturor limbajelor acceptate de Mi, i=0,1, . . . n. Mi se obin din M astfel nct fiecare stare a automatului devine pe rnd stare iniial. Fie Q = {q0, q1, q2, . . . qn}, construim MI = (Q, , , qi, F), I = 0, 1, . . . n. M0=MS) U F ( L = T ( M " ) =~

n

T ( M )

i

i= 0

M" va accepta limbajul format din mulimea sufixelor (nu neaprat proprii) cuvintelor limbajului L. Dac dorim sufixele proprii eliminm din reuniune M0; c)combinm a) i b).

1.4.7. a) Automatul construit este:

54

iar gramatica este G = ({A,B,C,D,E,F,G,H,I}, {a,b}, P, A) unde P: AbA | aB | a | b | BbC | bG | b CbD | b DbE | b EbF | b FaB | a GbH HbI I bB | b

55

1.5. GRAMATICI I LIMBAJE INDEPENDENTE DE CONTEXTO gramatic G = (N, , P, S) este independent de context dac produciile P ale acestei gramatici sunt numai de forma A, AN; (N)*. Gramaticile regulare sunt cazuri particulare de gramatici independente de context. Limbajul generat de o gramatic independent de context se numete limbaj independent de context.

1.5.1. Proprieti de nchidere ale limbajelor independente de contextTeorem. Dac L1 i L2 sunt limbaje independente de context atunci * L1 L2 , L1 L2 , L1 sunt limbaje independente de context. Observaii. Fie GI = (Ni, i, Pi, Si), i=1,2, dou gramatici independente de context i LI = L(Gi), i=1,2. 1o. Dac L = L 1 L 2 , L = L(G), G = { N, , P, S } atunci:N = N 1 N 2 S }, = 1 2 , P = P1 P2 S S1 | S 2 }, S N 1 N 2 . { {

2o. Dac L = L1 L 2 , L = L(G), G = (N, , P, S), atunci:N = N 1 N 2 S }, = 1 2 , P = P1 P2 { S S1S 2 }, S N 1 N 2 . {

3o. Dac L = L*1 , L = L(G), G = (N, , P, S), atunci: 4o. nu e independent de

G = ( N 1 { S }, 1 , P1 { S S S1 | }, S).

L1 L 2m n n

context; sunt

dm

un de

contraexemplu context, dar

L1 = {a b c | m, n 1} i L 2 = {a m b m c n | m, n 1} L1 L 2 = {a m bm cm | m 1}

dependente

nu este independent de context. 5o. L1 nu e independent de context, pentru c dac ar fi atunci conform relaiei L1 L2 = L1 L2 ar rezulta c intersecia este independent de context (ceea ce n general nu e adevrat).

1.5.2. Arbori de derivareArborii de derivare sunt arborescene ordonate cu vrfuri etichetate cu simboluri din mulimea neterminalelor i mulimea terminalelor; ei conin o r!aa!cin, noduri interioare i noduri terminale (care nu au succesori).

Fie G = (N,,P,S) o gramatic independent de context. Numim arbore de derivare sau arbore de analiz sintactic (a.a.s) o arborescen cu urmtoarele proprieti: 1o. Fiecare vrf are o etichet, care este un simbol din N {} ; 2o. Eticheta din r!aa!cin este S; 3o. Dac un nod este interior i are eticheta A atunci A trebuie s fie din N; 4o. Dac un nod are eticheta A iar nodurile succesoare acestuia, n ordine de la stnga la dreapta sunt etichetate cu X1, X2, . . . Xn atunci AX1X2. . . Xn trebuie s fie o producie din P. o 5 . Dac un nod are eticheta , atunci acesta nu are succesori. Nodurile terminale formeaz frontiera arborelui i ea, n ordine de la stnga la dreapta, formeaz o secven peste {}. Fie G o gramatic independent de context. Dac ntr-o derivare direct se nlocuiete cel mai din stnga neterminal atunci derivarea direct o numim derivare de stnga i o notm= >.d

=>.s

Dac ntr-o derivare direct se nlocuiete cel mai din

dreapta neterminal, atunci derivarea direct se numete derivare de dreapta i o notm

Fie gramatica independent de context G = (N, , P, S) atunci pentru o secven w succesiunea de derivri directe:*

S => 1 => 2 => . . . => n = w reprezint o derivare pentru cuvntul w sau altfel spus o analiz sintactic. Dac aceast succesiune de derivri directe se obine pornind de la S la w atunci avem o analiz sintactic descendent i aceasta corespunde construirii a.a.s. de sus n jos. Dac construirea a.a.s. se face de jos n sus, adic de la w la S, atunci avem o analiz sintactic ascendent. Aceste derivri pot fi fcute numai cu derivri de stnga sau numai cu derivri de dreapta. Teorem. Fie G = (N, , P, S) o gramatic independent de context. Un cuvnt w peste alfabetul , deci din *, aparine limbajului generat de G, adic wL(G), dac i numai dac w este frontul unui arbore de analiz sintactic. O gramatic G = (N, , P, S) independent de context este ambigu dac i numai dac exist cel puin un cuvnt care admite doi a.a.s. distinci; n caz contrar gramatica este neambigu. Limbajul generat de o gramatic ambigu (neambigu) este un limbaj ambiguu (neambiguu).57

Observaii. 1o. Noiunea de ambiguitate poate fi definit mai general, pentru orice tip de gramatic. Astfel o gramatic este ambigu dac exist un cuvnt al limbajului generat de ea cu proprietatea c exist cel puin dou derivri de stnga (sau de dreapta) distincte pentru el. 2o. Definia anterioar este, de fapt, o particularizare relativ la gramaticile independente de context.

1.5.3. Simplificarea gramaticilor independente de contextFie G = (N,,P,S) o gramatic independent de context cu L = L(G), L . 1. Simboluri inaccesibile Un simbol xN este simbol inaccesibil dac nu exist nici o derivare * S = > x cu ,(N) , n caz contrar simbolul este accesibil.*

Lema 1. Gramatica G este echivalent cu o gramatic G' = (N', ', P', S) fr simboluri inaccesibille. Algoritm. Gramatica G' conine numai simboluri accesibile care se determin astfel: 1o. V0 := { S }, i := 1 ; 2o. Vi := Vi-1 {x | (A x ) P, A Vi-1 , , (N )* } ; 3o. Dac Vi Vi-1 atunci i:=i+1 salt la 2o altfel stop.N := N Vi , ' := Vi

Mulimea produciilor P' este: {A (A>)P, AN', (N' ')*}. 2. Simboluri neproductive Un simbol A, AN este neproductiv dac nu exist nici o derivare de forma * A = > x , x , n caz contrar A este simbol productiv.*

Lema 2. Gramatica G este echivalent cu o gramatic G' = (N', , P', S) care conine conine numai simboluri productive. Algoritm. Simbolurile productive se determin astfel: 1o. N 0 := , i := 1; 2o. N i := N i-1 { A | (A ) P, (N i-1 )* };58

3o. Dac N i N i-1 atunci i:=i+1 salt la 2o altfel N':=N i stop. Mulimea produciilor P' este: {A (A)P, AN', (N')*}. Observaie: trebuie ca SN', pentru c dac SN' atunci L(G) = , adic gramatica iniial G nu genereaz nici o secven. 3. Simboluri neutilizabile Un simbol este neutilizabil dac el este fie inaccesibil, fie neproductiv. Lema 3. Gramatica G este echivalent cu o gramatic G' = (N', ', P', S) fr simboluri neutilizabile. Observaie. Pentru obinerea gramaticii G' se aplic: a) algoritmul corespunztor lemei 1 pentru G; b) algoritmul corespunztor lemei 2 pentru gramatica obinut la a). 4. -producii O producie de forma A se numete -producie. Dac L(G) atunci avem producia S i S nu apare n membrul drept al nici unei producii. Putem elimina pe S din celelalte producii considernd un nou simbol de start S' i produciile S | S. Lema 4. Gramatica G este echivalent cu o gramatic G' = (N', , P', S') n care: a) dac L(G) atunci G' nu are -producii; b) dac L(G) atunci avem o singur producie S iar celelalte producii nu-l conin n membrul drept pe S'. Observaie. Gramatica G' se numete -independent. Algoritm. Pentru obinerea gramaticii G' = (N', , P', S') fr -producii procedm astfel: 1o. Construim mulimea N care are ca elemente acele neterminale care prin derivare conduc la adic N = { A | A N, A = > }. Se poate folosi pentru determinarea mulimii N un algoritm similar cu cei utilizai pentru determinarea simbolurilor accesibile i a celor productive: a) N 0 := { A | (A ) P }, i := 1 ; b) N i := N i-1 { A | (A ) P, N*-1 }; i59*

c) Dac N i N i-1 atunci i:=i+1, salt la b) altfel N := N i , stop. - dac S N atunci: N'=N, S'=S, i P' se construiete conform 2o. - dac S N atunci: N'=N {S'},

P = { S , S S }

mulimea construit conform 2o.

2o. Fie n P producia A oB11B22...Bkk, unde k 0, Bi N iar n i nu exist simboluri din N , 1 i k. n P' includem toate produciile A oX11X22...Xkk, ce se obin punnd n toate modurile posibile: i excluznd eventualele producii de forma A care s-ar obine prin acest procedeu. 5. Redenumiri O producie de forma AB se numete redenumire. Lema 5. Gramatica G este echivalent cu o gramatic G' = (N, , P', S) fr redenumiri. Algoritm 1o Pentru fiecare AN se construiete mulimea NA = {B | A = > B }; Construcia este iterativ: a) No := {A}, i:=1; b) Ni: = Ni-1 {C | (B>C)P, BNi-1} c) dac Ni Ni-1 atunci i:=i+1, salt la b) altfel NA:=Ni. 2o Produciile din P' se obin dup cum urmeaz: dac (B)P, atunci NA astfel nct BNA. n P' introducem toate produciile A cu proprietatea c BNA. Produciile de forma AB din P nu se includ n P'. O gramatic independent de context fr simboluri neutilizabile, fr -producii i fr redenumiri se numete gramatic proprie. Teorem. Oricare ar fi o gramatic G independent de context cu L(G) i (G , L )*

Bi i = 1, k . Xi =

exist o gramatic proprie G', echivalent cu G, adic L(G) = L(G'). 6. Recursivitate60

7. O producie de forma A A se numete recursiv la stnga. Lema 6. Fie G o gramatic proprie cu produciile P. Aceast gramatic G este echivalent cu o gramatic G' = (N', , P', S) ale crei producii P' nu conin recursiviti la stnga. Pentru produciile din P cu membrul stng A, considerm urmtoarea partiie: M1 = {AA1, AA2, . . . AAr} M2 = {A1, A2, . . . As}. Atunci P' va fi format din produciile: Ai, AiZ; 1 i s apoi Zi, ZiZ; 1 i r. Procedm analog cu celelalte producii de acest fel ale mulimii P. Atunci N'=N mulimea neterminalelor Z astfel introduse. Observaie: Recursivitatea nu se poate elimina, ea se transform din recursivitate la stnga n recursivitate la dreapta.

1.5.4. Forma normal ChomskyO gramatic independent de context G = (N, , P, S) se spune c este n forma normal Chomsky (FNC) dac orice producie din P este de una din formele: a) A BC, A,B,CN; b) A a, a, AN; c) dac L(G) atunci (S ) P , iar S nu apare n membrul drept al nici unei producii. Teorem. Oricare ar fi G=(N, , P, S) o gramatic independent de context, ntotdeauna exist o gramatic n forma normal Chomsky G', astfel nct L(G) = L(G').

1.5.5. Forma normal GreibachO gramatic G = (N, , P, S) este n forma normal Greibach (FNG) dac P are producii numai de forma: a) A a, AN, a, N*; b) dac L(G) atunci (S ) P, iar S nu apare n membrul drept al nici unei producii.61

Teorem. Oricare ar fi G = (N, , P, S) o gramatic independent de context, ntotdeauna exist o gramatic n forma normal Greibach, astfel nct L(G)=L(G').

1.5.6. Leme de pompare pentru limbaje independente de contextPropoziie. (Lema de pompare) Fie L un limbaj independent de context. Exist atunci atunci o constant n dependent numai de L astfel c dac zL i |z| n, atunci avem descompunerea z=uvwxy cu proprietile: a) |vx| 1, b) |vwx| n, c) uviwxiyL i 0. Propoziie. (Lema Bar-Hillel) Dac L este un limbaj independent de context, atunci exist p>0, q>0 astfel nct pentru orice zL, |z|>p s avem o descompunere z=uvwxy cu |vwx| q i |v| + |x| 0 (v i x nu sunt simultan vide), iar uviwxiyL, i 0.

1.5.7. Probleme propuse1.5.1. S se construiasc gramatica care genereaz expresiile regulare peste alfabetul {a,b}. 1.5.2. Fie limbajele L1 = {01n0 | n 1} i L2={10n1 | n 1}. S se construiasc gramaticile care genereaz limbajele: * * L1 L2, L1L2, L1 , L 2 . 1.5.3. S se defineasc o gramatic independent de context care genereaz peste alfabetul {b,c} toate cuvintele ce au acelai numr de b-uri ca i c-uri. 1.5.4. S se defineasc o gramatic independent de context care genereaz peste alfabetul {b,c,d} toate cuvintele n care bc nu este o subsecven. 1.5.5. S se defineasc o gramatic independent de context care genereaz mulimea palindroamelor peste alfabetul {b,c}. (Un palindrom este un cuvnt identic cu oglinditul su). 1.5.6.62

S se construiasc gramaticile independente de context care genereaz limbajele: a) {bmc2mdenfn | m, n 1}; b) {bmcndnemfp(ghk)p | m 2, k,n 0, p 1}; c) {bmcn | 1 n m 2n}; d) {bm+pcdm+nefn+p | m, n, p 0}. 1.5.7. S se construiasc gramaticile independente de context care genereaz limbajele: a) L1 = {anbm | n m 0}; c) L3 = {anbkcm | m n 0,k 0}; b) L2 = {anbm | m n 0}; d) L4 = {anbkcm | n m 0,k 0}. 1.5.8. S se construiasc gramaticile independente de context care genereaz limbajele: a) L1 = {anbm | 1 n m 2n}; c) L3 = {anbm | 2n m 3n,n 0}; b) L2 = {anbm | 1 n m 5n}; d) L4 = {anbm | 3m n 5m,m 0}. 1.5.9. S se construiasc gramaticile independente de context care genereaz limbajele: a) L1 = {anbmcmdn | n,m 0}; b) L2 = {anbkcn-k | n k 0}; c) L3 = {anbkcn+k | n 0,k 0}. 1.5.10. S se construiasc gramaticile independente de context care genereaz limbajele: ~ ~ a) L1={ x x | x{0,1}*} x este oglinditul (reversul) lui x; b) L2={ xw x | x,w{0,1}*}; c) L3={ x x w | x,w{0,1}*};d)~ ~

L4={ wx x | x,w{0,1}*}.

~

1.5.11. S se construiasc gramaticile independente de context care genereaz limbajele: a) L1={w{a,b}* | nra(w)=nrb(w)}; b) L2={w{a,b}* | nra(w) nrb(w)}. 1.5.12. S se construiasc gramaticile care genereaz limbajele: a) L1 = { w{a,b}* | nra(w)=2*nrb(w), iar simbolurile "a" apar perechi} ex: aabbbaaaa L1; abbaabaaa L1; b) L2 = { w{a,b}* | nra(w)=k*nrb(w),kN, iar simbolurile "a" apar n grupuri de multiplu de k elemente}; c) L3 = {w{a,b}* | 2*nra(w)=3*nrb(w), simbolurile "a" apar n grupuri de multiplu de 3 elemente, iar simbolurile "b" apar n grupuri de multiplu de 2 elemente}; ex: aaabbbbaaa L3.63

1.5.13. S se construiasc gramaticile care genereaz expresii aritmetice avnd doar operanzi notai cu "a" i operatorii binari +,-,/,* a) n forma polonez prefixat; b) n forma polonez postfixat; c) n forma polonez infixat (cu paranteze). 1.5.14. S se arate c gramaticile care conin produciile urmtoare sunt ambigue i s se gseasc cte o gramatic echivalent neambigu: a) S aS | Sb | c; b) S if b then S else S | if b then S | a; c) S a | aB , Ba SB; aB d) S S (S) S) 1. 1.5.15. S se arate c gramaticile care conin produciile urmtoare sunt ambigue: a) A AA | a; b) A A | A | a; c) A A | A | a. 1.5.16. S se arate c gramatica G = ({S,B,C}, {a,b,c}, P, S), cu P={SabC | aB, Bbc, bCbc} este ambigu. 1.5.17. Fie gramatica G=({S,A,B},{a,b},P,S) i avnd produciile urmtoare: S aB | bA A a | aS | bAA B b | bS | aBB i w=aaabbabbba a) gsii o derivare de stnga pentru w; b) gsii o derivare de dreapta pentru w; c) construii arborele de derivare cu frontul w; d) este aceast gramatic neambigu? e) se poate descompune w conform lemei de pompare? 1.5.18. Descriei limbajul generat de gramatica G = ({S}, {a,b}, P, S), P={SbSS | a}. 1.5.19. S se descrie limbajul generat de gramatica G=({S,A,B}, {a,b,c,d}, P, S) cu produciile: S Ac | Bd A aAb | ab B aBbb | abb64

1.5.20. Artai c L(G) este mulimea secvenelor peste alfabetul {0,1} care conin un numr multiplu de 3 de simboluri 0, unde: G = ({S,A,B}, {0,1}, P, S), P={S0A | 1S | , A0B | 1A, B0S | 1B}, S). 1.5.21. Fie G=({S,A,B,C}, {a,b}, P, S) cu mulimea produciilor: P={SAB | C, Aa, BCB |A, Cb}. S se arate c L(G) = {b} {abna 0}. n 1.5.22. S se aduc la forma normal Chomsky i la forma normal Greibach gramaticile de la problemele 1.5.16., 1.5.17., 1.5.19., 1.5.20.

1.5.8. Indicaii i soluii1.5.1. G = (N, , P, S); N = {S}, = {a,b,+,*,(,)}, P = {SS+S | SS | (S) | S* | a | b | | }. 1.5.3. O astfel de gramatic este: G = (N, , P, S) cu N = {S}, = {b,c} P = {SbSc | cSb | SS | bc | cb}. 1.5.4. G = (N, , P, S) cu N = {S,E}, = {b,c,d}, P = {SbE | cS | dS | b | c | d, EbE | dS | b | d}. 1.5.5. G = (N, , P, S) cu N = {S}, = {b,c}, P = {SbSb | cSc | b | c | }. 1.5.6. a) G = (N, , P, S) N = {S,J,K}, = {b,c,d,e,f}, P = {SJdK, JbJcc | bcc, KeKf | ef}. b) G = (N, , P, S) N = {S,J,L,K,Q}, = {b,c,d,e,f,h,g}, P = {SJK, JbJe | bbee | bbLee, LcLd | cd, KfKQ | fQ, QghQ | gh}. c) G = (N, , P, S)65

N = {S}, = {b,c}, P = {SbSc | bbSc | bc | bbc}. d) G = (N, , P, S) N = {S,G,H}, = {b,c,d,e,f}, P = {SbSf | GH, GbGd | c, HdHf | e}. Un cuvnt wL(G) se poate scrie w=bm+pcdm+nefn+p=bp((bmcdm)(dnefn))fp. 1.5.7. a) G = (N, , P, S) cu N = {S,A}, = {a,b}, P = {SaSb AaA | }. A, b) G = (N, , P, S) N = {S,B}, = {a,b}, P = {SaSb | B, BBb | }. c) G = (N, , P, S) N = {S,B,C}, = {a,b,c}, P = {SaSc | B, BbB | C, C->Cc | }. d) G = (N, , P, S) N = {S,A,B}, = {a,b,c}, P = {SaSc BBb AaA | }. B, A, 1.5.8. a) G = (N, , P, S) N = {S}, = {a,b}, P = {SaSb | aSbb | ab | abb}. b) G = (N, , P, S) N = {S}, = {a,b}, P = {SaSb | aSb2 | aSb3 | aSb4 | aSb5 | ab | ab2 | ab3 | ab4 | ab5 }. c) G = (N, , P, S) N = {S}, ={a,b}, P = {SaSbb | aSbbb | }. d) G = (N, , P, S) N = {S}, ={a,b}, P={Sa3Sb | a4Sb | a5Sb | }. 1.5.9. a) G = (N, , P, S) N = {S,H}, = {a,b,c,d}, P = {SaSd | H, HbHc | }. b) se observ c anbkcn-k se poate scrie sub forma an-k(akbk)cn-k i se reduce la problema de la a) G = (N, , P, S) N = {S,H}, = {a,b,c}, P = {SaSc | H, HaHb | }. c) se observ c anbkcn+k se poate scrie sub forma an(bkck)cn i se reduce la problema de la punctul a) G = (N, , P, S) N = {S,H}, = {a,b,c}, P = {SaSc | H, HbHc | }.66

1.5.10. a) G = (N, , P, S) N = {S}, = {0,1}, P = {S0S0 | 1S1 | }. b) G = (N, , P, S) N = {S,X}, = {0,1}, P={S0S0 | 1S1 | X, X0X | 1X | }. c) G = (N, , P, S) N = {S,S1,S2}, = {0,1}, P = {SS1S2, S10S10 | 1S11 | , S20S2 | 1S2 | }. d) G = (N, , P, S) N = {S,S1,S2}, = {0,1}, P = {SS2S1, S10S10 | 1S11 | , S20S2 | 1S2 | }. 1.5.11. a)-gramatic ambigu G = (N, , P, S) N = {S}, = {a,b}, P = {SaSb | bSa | SS | }. -gramatic neambigu G = (N, , P, S) N = {S,A,B}, ={a,b}, P = {SaB | bA, AaS | bAA | a, BbS | aBB | b}. b)-gramatic ambigu G = (N, , P, S) N = {S,A}, = {a,b}, P = {SaSb | bSa | SS | A, AaA | a}. -gramatic neambigu G = (N, , P, S) N = {S,A,B,X}, = {a,b}, P = { SAB | bA | , AAS | bAA | X, BbS | ABB | b, XaX | a}. 1.5.12. a) G = (N, , P, S) N = {S,A,B}, = {a,b}, P = {SAB | BA | , AAS | BAA | aa, BBS | ABB | b}. b) G = (N, , P, S) N = {S,A,B}, = {a,b}, P = {SAB | BA | , AAS | BAA | ak, BBS | ABB | b}. c) G = (N, , P, S) N = {S,A,B}, = {a,b}, P = {SAB | BA | , AAS | BAA | a3, BBS | ABB | b2}. 1.5.13.67

Gramaticile de la a) i b) sunt neambigue, ele rezult din definiiile recursive ale celor dou forme poloneze prefixat i postfixat. a) G = (N, , P, S) N = {S}, = {a,+,-,/,*}, P = {S+SS | -SS | /SS | *SS | a}. Exemplu: w=+*+aaa-a/aa S> +SS > +*SSS > +*+SSSS > +*+aSSS > +*+aaSS > +*+aaaS > > +*+aaa-SS > +*+aaa-aS > +*+aaa-a/SS > +*+aaa-a/aS > +*+aaa-a/aa Pentru forma polonez prefixat am folosit derivri de stnga pentru c ele sunt mai sugestive, fiind dirijate de forma cuvntului pornind de la stnga spre dreapta. Exist o singur derivare de stnga a fiecrui cuvnt din limbaj, gramatica este neambigu. b) G = (N, , P, S) N = {S}, = {a,+,-,/,*}, P = {SSS+ | SS- | SS/ | SS* | a}. Exemplu: w=aa+a*aaa/-+ S> SS+ > SSS-+ > SSSS/-+ > SSSa/-+ > SSaa/-+ > Saaa/-+ > SS*aaa/-+ > Sa*aaa/-+ > SS+a*aaa/-+> Sa+a*aaa/-+ > aa+a*aaa/-+ Pentru forma polonez postfixat am folosit derivri de dreapta pentru c ele sunt mai sugestive, fiind dirijate de forma cuvntului pornind de la dreapta spre stnga. Exist o singur derivare de dreapta a fiecrui cuvnt din limbaj, gramatica este neambigu. c) G = (N, , P, S) N = {S}, = {a,+,-,/,*,(,)}, P = {SS+S | S-S | S/S | S*S | (S) | a}. Aceast gramatic este ambigu deoarece pentru unele cuvinte din limbaj exist dou derivri de stnga distincte. Exemplu: pentru cuvntul w=a+a*a avem derivrile urmtoare: S > S+S > a+S > a+S*S > a+a*S > a+a*a i S > S*S > S+S*S > a+S*S > a+a*S > a+a*a. Se poate construi i o gramatic neambigu echivalent cu cea de mai sus: G' = (N', , P', E) N' = {E,T,F}, = {a,+,-,/,*,(,)}, P' = {EE+T | E-T | T, TT*F | T/F | F, FE) | a} E = are semnificaia de expresie F = are semnificaia de factor T = are semnificaia de termen Exemplu: cuvntul w=a+a*a se poate obine n mod unic prin derivare de stnga: E > E+T > T+T > F+T > a+T > a+T*F > a+F*F > a+a*F > a+a*a. 1.5.14. a) w=aacb i cele dou derivri de stnga pentru w sunt: S > aS > aaS > aaSb > aacb i68

S > Sb > aSb > aaSb > aacb Produciile de mai sus se pot nlocui cu produciile urmtoare: SaS | cB, BbB | }. Aceast gramatic este neambigu, generarea cuvintelor limbajului se face n mod unic de la stnga spre dreapta. w=aacb S > aS > aaS > aacB > aacbB > aacb De fapt cele dou gramatici genereaz limbajul L = {amcbn | m,n 0}. b) Pentru w=if b then if b then a else a avem dou derivri de stnga distincte: S > if b then S else S > if b then if b then S else S > if b then if b then a else S > if b then if b then a else a i S > if b then S > if b then if b then S else S > if b then if b then a else S > if b then if b then a else a . Ambiguitatea rezult din faptul c else-ul se poate ataa oricruia din cele dou then-uri. Pentru a nltura ambiguitatea trebuie s facem o convenie de ataare a unui else la un then. Convenia va fi urmtoarea: else-ul se va ataa ultimului then. Gramatica neambigu care modeleaz if...then..else... va fi: G = (N, , P, S) N = {S,S'}, = {a,b,if,then,else} P = {S if b then S | if b then S' else S | a, S'if b then S' else S' | a }. Faptul c doar S' precede un else, asigur c ntre o pereche then-else generat de orice producie trebuie s apar fie a fie un alt else. c) Pentru w=aaaa avem urmtoarele derivri: S > aB > aaB > aaaB > aaaa=w i S > aB > aSB > aaBB > aaaB > aaaa=w. Limbajul generat de aceast gramatic este L = {an 1}, iar o gramatic neambigu n care l genereaz este: G = (N, , P, S} N = {S}, ={a}, P = {SaS | a}. d) Dou derivri de stnga distincte pentru w=((1) sunt: S > (S > ((S > ((S) > ((1)=w i S > (S > ((S) > ((1)=w Gramatica genereaz limbajul L = {(m1)n | m,n 0}; O gramatic neambigu care genereaz acest limbaj este: G = (N, , P, S) N = {S,A}, = {(,1,)}69

P = {S(S | 1A, A>A) | } n acest caz cuvintele se genereaz n mod unic de la stnga la dreapta: nti se genereaz parantezele deschise, apoi simbolul 1, iar la sfrit parantezele nchise. S > (S > ((S > ((1A > ((1A) > ((1)=w.

1.5.15. Gramaticile din enun sunt independente de context. a) Pentru w=aaaL(G) cei doi arbori de derivare distinci cu frontul w sunt:

b) Fie cuvntul w=aL(G). Cei doi arbori de derivare cu frontul w sunt:

70

c) Cei doi arbori de derivare cu frontul w pentru w=a sunt:

71

1.5.16. Fie w=abcL(G) i avem dou derivri de stnga distincte pentru w: a) S

=>1

abC

=>4

abc i

b) S

=>2

aB

=>3

abc.

1.5.19. L(G)={anbnc | n 1} {anb2nd | n 1}.

72

1.6. AUTOMATE PUSH-DOWNUn automat push-down (APD) este un ansamblu M = (Q, , , , qo, Zo, F) unde: - Q este o mulime finit i nevid de elemente numite stri; - este un alfabet denumit alfabetul de intrare; - este un alfabet denumit alfabetul memoriei stiv; - qoQ, qo este stare iniial; - Zo, Zo este simbolul de start al memoriei stiv; - F Q, F este mulimea strilor finale; - :Qx({})xP0(Qx*) este funcia de tranziie care are ca valori submulimi finite din Qx* (n general parial definit). Fie APD M = (Q, , , , qo, Zo, F). Spunem c acest automat este determinist dac: 1) qQ i Z, n cazul c |(q,,Z)| = 1, atunci (q,a,Z) = , a; 2) |(q,a,Z)| 1, qQ, a {}, Z. n caz contrar APD este nedeterminist. Observaie. Dac qQ, a {}, Z atunci (q,a,Z)={(p1,1), . . . (pn,n)} pkQ, k*, k{1,..,n}. O configuraie a automatului M este (q,w,)Qx*x* care nseamn c automatul se gsete n starea q, pe banda de intrare urmeaz s se citeasc (accepte) secvena w, iar n memoria stiv avem secvena . Pe mulimea configuraiilor se definesc relaiile binare:a)

tranziie direct (q,ax,Z) (p,x,) (q,a,Z)(p,) sau (q,ax,Z) (p,ax,) (q,,Z)(p,)

n ultimul caz spunem c a avut loc o -tranziie, adic nu s-a avansat pe banda de intrare (unde p,qQ, a, Z, x*, , din *). Tranziia direct nseamn cu alte cuvinte urmtoarele: - se trece (eventual) n alt stare; - se avanseaz (sau nu) pe banda de intrare; - se nlocuiete simbolul Z, din vrful stivei, cu o secven de simboluri din ; b) + c) * k

k tranziia (k tranziii directe); + tranziia (nchiderea tranzitiv);

d) * tranziia (nchiderea reflexiv i tranzitiv)70

1.6.1. ReprezentareFie M = (Q, , , , qo, Zo, F) i Q = {qo,q1,. . . qn}, = {Zo,Z1,. . . Zk} Pentru reprezentare automatului se poate alctui urmtorul tabel: { } B (q0,b,Z0) (q0,b,Zm ) (qn,b,Z0) (qn,b,Zm )

Qx Z0 q0 Zm Z0 qn Zm

a (q0,a,Z0) (q0,a,Zm) (qn,a,Z0) (qn,a,Zm)

(q0, , Z0) (q0, , Zm) (qn, , Z0) (qn, , Zm)

1.6.2. Limbaj acceptat de un APDFie APD M = (Q, , , , qo, Zo, F). Configuraia (qo,w,Zo) o numim configuraie iniial. Configuraia (q,,), qF o numim configuraie final dup criteriul strii finale, iar configuraia (q,,) se numete configuraia final dup criteriul stivei vide. Limbajul acceptat de APD, M, dup criteriul strii finale este: T1(M) = {w | w*, (qo,w,Zo) (q,,), qF, *}*

iar limbajul acceptat de APD, M, dup criteriul stivei vide este T2(M) = {w| w*, (qo,w,Zo) (q,,), qQ}71*

Observaii. 1o. Pentru un limbaj acceptat de un APD dup criteriul stivei vide nu are nici o importan mulimea strilor finale F, se poate considera c n acest caz F=; altfel n tabelul anterior se adaug la nceput o coloan cu elemente zi:=dac qiF atunci 1 altfel 0, i=0,1,...,n. 2o. Se folosete pentru T2(M) uneori notaia T(M), deci T(M) = T2(M). 3o. Cele dou criterii de acceptare sunt echivalente. Teorem. Fie automatul push-down M. Exist ntotdeauna un automat push-down M' astfel nct T(M') = T1(M); de asemenea i reciproc. Teorem. Oricare ar fi L un limbaj independent de context, exist un automat push-down M astfel nct T(M) = L. Vom da un algoritm de trecere de la o gramatic independent de context la automatul push-down care accept limbajul generat de gramatic. Fie L un limbaj independent de context, atunci exist o gramatic independent de context G = (N, , P, S) astfel nct L = L(G). Se construiete automatul push-down M = ({q}, , N, , q, S, ) cu proprietatea T(M)=L(G), astfel:a) b)

c)

dac (A )P atunci (q, ) (q, ,A); (neterminalul din vrful stivei este expandat prin ); (q,a,a );={(q, )} a ; (se terge simbolul din vrful stivei dac acesta coincide cu cel de pe banda de intrare) (.,.,.)= n celelalte cazuri.

1.6.3. Probleme propuse1.6.1. S se construiasc un automat push-down care accept limbajul L = {anbn | n 0}. 1.6.2. S se construiasc un automat push-down care accept limbajul L = {anb3n | n>0}. 1.6.3. S se construiasc un automat push-down care accept limbajul L = {a3nbn | n 0}. 1.6.4. S se construiasc un automat push-down care accept limbajul L = {a2nb3n | n 0}. 1.6.5. S se construiasc un automat push-down care accept limbajul L = {anbn|n 1} {anb2n | n 1}.72

1.6.6. S se construiasc un automat push-down care accept limbajul L = {anbm | 00}. 1.6.8. S se construiasc un automat push-down care accept limbajul L = {a nbm | 1 n m 2n}. 1.6.9. S se construiasc un automat push-down care accept limbajul L = {anbm | 1 pn m qn,p q}. 1.6.10. S se construiasc un automat push-down care accept limbajul L= {anbm | 1 m n 2m}. 1.6.11. S se construiasc un automat push-down care accept limbajul ~ L = { wd w | w{a,b,c}*}}. 1.6.12. ~ S se construiasc un automat push-down care accept limbajul L={ w w |w{a,b,c}*}}. 1.6.13. S se arate c cele dou criterii de acceptare ale unui APD sunt echivalente, adic: a) Fiind dat un APD care accept un limbaj L dup criteriul stivei vide, atunci un automat APD care accept acelai limbaj dup criteriul strii finale (S se dea construcia); b) analog, n sens invers. 1.6.14. S se arate c nu pentru orice APD nedeterminist exist unul determinist echivalent cu el; adic exist limbaje independente de context care nu sunt acceptate de un APD determinist ci doar de unul nedeterminist. 1.6.15. S se construiasc un automat push-down care accept limbajul L = {w{a,b}* | nra(w)=nrb(w)}.

1.6.4. Indicaii i soluii1.6.1. Ideea rezolvrii const n: - la fiecare simbol a citit de pe banda de intrare se adaug n stiv un simbol A;73

- la terminarea citirii tuturor simbolurilor a consecutive de pe banda de intrare, n stiv sunt attea simboluri A cte simboluri b trebuie s urmeze pe banda de intrare pentru a respecta forma cuvintelor din limbaj; - la fiecare simbol b citit de pe banda de intrare se scoate din stiv un simbol A; - dup ce s-a citit un simbol b de pe banda de intrare, nu pot s mai apar simboluri a pe banda de intrare; - dac la terminarea citirii cuvntului de pe banda de intrare n stiv este doar simbolul Z0 atunci stiva se golete i cuvntul este acceptat dup criteriul stivei vide; M = (Q, , , , q0, Z0, F); Q = {q0,q1}, = {a,b}, = {Z0,A}; F= (automatul accept limbajul dup criteriul stivei vide); :{q0,q1}x{a,b,}x{Z0,A} P({q0,q1}x{Z0,A}*) i este definit astfel: q0 - este starea n care se citesc repetat simboluri a de pe banda de intrare adugndu-se cte un A n stiv; q1 - este starea n care se trece dup citirea primumului b de pe banda de intrare, apoi se vor citi repetat b-uri tergndu-se cte un A din stiv pentru fiecare b; 1. (q0, ,Z0) = {(q0, )} -este acceptat secvena vid

prin vidarea stivei;

2. (q0,b,Z0) = -cuvntul nu poate s nceap cu un simbol b; 3. (q0,a,Z0) = {(q0,A,Z0)} -s-a citit primul simbol a i s-a adugat un A n stiv; 4. (q0, ,A) = -nu e o situaie valid pentru c am terminat de citit cuvntul i nu am citit nici un b, deci forma cuvntului nu e cea dorit (cuvntul este format numai din simboluri a); 5. (q0,a,A) = {(q0,AA)} -se citete un a de pe banda de intrare i se adaug un A n stiv; 6. (q0,b,A) = {(q1, )} -s-a citit primul b i s-a ters un A din stiv; -s-a trecut n starea q1 pe care o putem numi stare de tergere; 7. (q1, ,A) = -s-a terminat de citit cuvntul, dar n stiv au mai rmas simboluri a, deci cuvntul are mai multe simboluri a dect b; 8. (q1,b,A) = {(q1, )} -suntem n starea de tergere, se citete un b de pe banda de intrare, se terge un A din stiv;74

9. (q1,a,A) = -din aceast stare de tergere nu se poate citi un a de pe banda de intrare pentru c forma cuvntului nu ar fi cea dorit (ar alterna a-urile i b-urile); 10. (q1, ,Z0) = {(q1, )} -n acest moment s-a terminat de citit cuvntul de pe banda de intrare, iar n stiv avem doar Z0, deci tergem i acest simbol, stiva devine vid, deci cuvntul este acceptat; 11. (q1,a,Z0) = -din starea q1 nu putem citi un a (forma cuvntului nu convine pentru c alterneaz aurile i b-urile"); 12. (q1,b,Z0) = -nu e o situaie valid pentru c citim un b dar n stiv nu mai exist nici un A pentru a fi ters (cuvntul are mai multe simboluri b dect a); Tabelar funcia se reprezint astfel: Qx Q0 Q1 Z0 A Z0 A A {(q0,AZ0} {(q0,AA} { } b {(q1, } {(q1, } {(q0, } {(q1, }

Exemple : 1) w=aabb (q0,aabb,Z0) 3 (q0,abb,AZ0) (q0,bb,AAZ0) (q1,b,AZ0) (q1,,Z0) (q1,,) 5 6 8 10 - s-a ajuns la o configuraie final dup criteriul stivei vide, deci cuvntul este acceptat de automat; 2) w= (q0,,Z0) 1 (q0,,) -cuvntul este acceptat dup criteriul stivei vide; 3) w=abab (q0,abab,Z0) (q0,bab,AZ0) (q1,ab,Z0) blocare 3 6 11 -cuvntul nu este acceptat, forma lui nu convine; 4) w=ba (q0,ba,Z0) blocare 275

-cuvntul nu este acceptat, forma lui nu convine; 5) w=aab (q0,aab,Z0) (q0,ab,AZ0) (q0,b,AAZ0) (q1,,AZ0) blocare 3 5 6 7 -cuvntul nu este acceptat, forma lui nu convine; 6) w=aaba (q0,aaba,Z0) (q0,aba,AZ0) (q0,ba,AAZ0) (q1,a,AZ0) blocare 3 5 6 9 -cuvntul nu este acceptat, forma lui nu convine; 7) w=aa (q0,aa,Z0) (q0,a,AZ0) (q0,,AAZ0) blocare 3 5 4 -cuvntul nu este acceptat, forma lui nu convine; 8) w=abb (q0,abb,Z0) (q0,bb,AZ0) (q1,b,Z0) blocare 3 6 12 -cuvntul nu este acceptat, forma lui nu convine; 1.6.2. Vom prezenta dou automate echivalente care accept limbajul L: a) la fiecare simbol a citit de pe banda de intrare se adaug n stiva 3 simboluri A; - dup citirea tuturor simbolurilor a n stiv sunt attea simboluri A, cte simboluri b trebuie s urmeze pe banda de intrare; - la fiecare b citit se scoate din stiv un A; - cuvintele din limbaj vor fi acceptate dup criteriul strii finale; - automatul este determinist M = (Q, , , , q0, Z0, F) Q = {q0,q1,q2}, = {a,b}, = {Z0,A} F={q2} criteriul de acceptare este cel al strii finale; :{q0,q1,q2}x{a,b,}x{Z0,A}P({q0,q1,q2}x{Z0,A}*) i este definit astfel: (q0,a,Z0)={(q0,AAAZ0)} (q0,a,A) ={(q0,AAAA)} (q0,b,A) ={(q1,)} (q1,b,A) ={(q1,)} (q1,,Z0)={(q2,Z0)} - n acest moment s-a terminat de citit cuvntul de pe banda de intrare, iar n stiv este doar simbolul Z0; (deci cuvntul este de forma dorit). Pentru ca automatul s accepte cuvntul dup criteriul strii finale el trebuie s treac intr-o stare final q2; (., . ,.) = n celelalte cazuri; b) la fiecare simbol a citit se adaug n stiv un simbol A; - la terminarea citirii simbolurilor a, n stiv vor fi de trei ori mai puine simboluri A dect numrul simbolurilor b care trebuie citite n continuare; - la fiecare grup de 3 simboluri b citite se va scoate din stiv un A, aceasta se76

realizeaz folosind nc dou stri intermediare; - cuvintele vor fi acceptate dup criteriul stivei vide; - automatul este determinist; M = (Q, , , , q0, Z0, F) Q = {q0,q1,q2,q3}, = {a,b}, = {Z0,A} F = criteriul de acceptare este cel al stivei vide :{q0,q1,q2,q3}x{a,b,}x{Z0,A}P({q0,q1,q2,q3}x{Z0,A}*) i este definit astfel: (q0,a,Z0)={(q0,AZ0)} (q0,a,A) ={(q0,AA)} (q0,b,A) ={(q1,A)} -s-a citit primul simbol b, stiva rmne nemodificat, se trece n starea intermediar q1; (q1,b,A) ={(q2,A)} -s-a citit un numr multiplu de 3 plus 2 simboluri b, nu se modific coninutul stivei, se trece n starea intermediar q2; (q2,b,A) ={(q3,)} -s-a citit un numr multiplu de 3 simboluri b, se terge un A se revine la stare q3 pentru a se citi un alt grup de 3 simboluri b; (q3,b,A) ={(q1,A)} -s-a citit un numr multiplu de 3 plus 1 simboluri b, stiva rmne nemodificat, se trece n starea intermediar q1; (q3,,Z0)={(q3,)} (., ., .) = n celelalte cazuri; Observaii: 1o. Cnd automatul este n starea q1 s-au citit un numr multiplu de 3 plus 1 simboluri b; 20. Cnd automatul este n starea q2 s-au citit un numr multiplu de 3 plus 2 simboluri b; 3o. Cnd automatul este n starea q3 s-au citit un numr multiplu de 3 simboluri b. 1.6.3. Vom prezenta dou automate echivalente care accept limbajul {a3nbn}: a) la un grup de trei simboluri a citite de pe banda de intrare se adaug n stiv un simbol A, aceasta se realizeaz folosind nc dou stri intermediare; -dup citirea tuturor simbolurilor a, n stiv sunt attea simboluri A, cte simboluri b trebuie s urmeze pe banda de intrare; -la fiecare b citit se scoate din stiv un A; -cuvintele din limbaj vor fi acceptate dup criteriul stivei vide; M = (Q, , , , q0, Z0, F) Q = {q0,q1,q2,q3}, = {a,b}, = {A,Z0} F = criteriul de acceptare este cel al stivei vide :{q0,q1,q2,q3}x{a,b,}x{Z0,A}P({q0,q1,q2,q3}x{Z0,A}*) i este definit astfel:77

(qo,,Zo)={(qo,)}; (qo,a,Zo)={(q1,AZo)}; (q1,a,A) ={(q2,A)}; (q2,a,A) ={(qo,A)}; (qo,a,A) ={(q1,AA)}; (qo,b,A) ={(q3,)}; (q3,b,A) ={(q3,)}; (q3,,Zo)={(qo,)}; (., ., .) = n celelalte cazuri. b) la fiecare simbol a citit se adaug n stiv un simbol A; -la terminarea citir