Lucrare de Curs LFPC [PDF]

Zitiervorschau

Ministerul Educaţiei al Republicii Moldova Universitatea Tehnică a Moldovei Catedra Automatica si Tehnologii Informationale

Lucrarea de Curs la Limbaje Formale si Proiectarea Algoritmilor

A efectuat:

A verificat:

Chişinău 2015

Lucrarea Nr.1 Scopul lucrarii: 1.Pentru gramatica formală G=(VN, VT, P, S) construiţi 5 şiruri care aparţin limbajului L(G) generat de această gramatică. 2.Construiţi arborii de derivare pentru aceste şiruri. 3.Construiţi (desenaţi) automatul finit echivalent. Varianta 4. VN={S, L }, VT={a, b,c,d,e,f,j } , P= { 1. S  aS 2. S  bS 3. S  cS 4. S  dL 5. L  eL 6. L  fL 7. L  jL 8. L  e 9. L  f 10.L  j 11.S  d } 1. a)SaSabSaabd b)SbsbdLbdjLbdje c)ScScbScbaScbadLcbadf d)SdLdeLdejLdejf e)SbSbcSbcdLbcdjLbcdje 2. a)

b)

c)

d)

e)

3.

q0 q1 q2

a q0 -

b q0 -

c q0 -

d e f j q1q2 q1q2 q1q2 q1q2 -

Lucrarea Nr.2 Scopul lucrarii: Este dat automatul finit AF=(Q, , , q0, F). Reprezentaţi automatul sub formă de graf. Este sau nu automatul dat determinist? Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent. Construiţi gramatica regulată echivalentă cu AFD Inventaţi un şir peste vocabularul  care nu va fi acceptat de către AFD. Arătaţi acest lucru scriind secvenţa (secvenţele) de configuraţii respective. 6. Pentru automatul finit AFD=(Q, , , q0, F) construiţi 5 şiruri acceptate de automat. Lungimea şirurilor să nu fie mai mică decât n+2, unde n este numărul de stări din Q. 7. Scrieţi expresia regulată echivalentă. 8. Pentru fiecare şir x scrieţi secvenţa de configuraţii pentru acceptarea şirului, adică (q0, x) — (qi1, x1) — (qi2, x2) — … — (qf, ), unde qf  F. 9. Petru toate cele 5 şiruri obţinute construiţi aplicând lema de pompare descompunerea x=uvw. 1. 2. 3. 4. 5.

Varianta 4 AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3},  = { a, b, c}, F = { q3}.  (q0, a) = {q1},  (q1, a) = {q2},  (q2, b) = {q2, q3},  (q2, c ) ={q2},  (q3, a) ={q3} . 1.Este data automatul finit AF=(Q, , , q0, F). Reprezentaţi automatul sub formă de graf.

2.Este sau nu automatul dat determinist. 3. Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent. Q’ a b c q0 q1 q1 q2 q2 q2,q3 q2 q2q3 q3 q3,q2 q2 q3 q3 c

a q0

a q1

b

b q2

a

a q2q3

q3

4.Construiţi gramatica regulată echivalentă cu AFD a)q0→aq1 b)q2→b q1→aq2 q3→a q2→bq2 q2q3->b q2q3->bq2 q2q3->a q2→cq2 q2→bq3 q2q3->aq3 q3→aq3 5. Inventaţi un şir peste vocabularul  care nu va fi acceptat de către AFD. Arătaţi acest lucru scriind secvenţa (secvenţele) de configuraţii respective. x=aacbca (q0,aacbca) —(q1,acbca) —(q2,cbca) —(q2,bca) —(q2q3,ca) —(q2,a)-impas 6.Pentru automatul finit AFD=(Q, , , q0, F) construiţi 5 şiruri acceptate de automat. Lungimea şirurilor să nu fie mai mică decât n+2, unde n este numărul de stări din Q. x1=aaccbcba x2=aacbbaa x3=aabbaaa x4=aacbcbba x5=aacbbba 7.Scrieţi expresia regulată echivalentă. 𝑎𝑎 ∗ (𝑏 + 𝑐)∗ ∗ 𝑏 ∗ 𝑎∗ 8.Pentru fiecare şir x scrieţi secvenţa de configuraţii pentru acceptarea şirului, adică (q0, x) — (qi1, x1) — (qi2, x2) — … — (qf, ), unde qf  F. a)(q0,aaccbcba) —(q1,accbcba) —(q2,ccbcba) —(q2,cbcba) —(q2,bcba) —(q2q3,cba) — —(q2,ba) —(q2q3,a) —(q3,e) b)(q0,aacbbaa) —(q1,acbbaa) —(q2,cbbaa) —(q2,bbaa) —(q2q3,baa) —(q2q3,aa) —(q3,a) — (q3,e) c) (q0,aabbaaa) —(q1,abbaaa) —(q2,bbaaa) —(q2q3,baaa) —(q2q3,aaa) —(q3,aa) —(q3,a) — (q3,e) d) (q0,aacbcbb) —(q1,acbcbb) —(q2,cbcbb) —(q2,bcbb) —(q2q3,cbb) —(q2,cbb) — (q2q3,bb) —(q2q3,b) —(q2q3,e) e) (q0,aacbbba) —(q1,acbbba) —(q2,cbbba) —(q2,bbba) —(q2q3,bba) —(q2q3,ba) —(q2q3,a) —(q3,e)

9.Petru toate cele 5 şiruri obţinute construiţi aplicând lema de pompare descompunerea x=uvw. a)aaccbcba a a c c b c b a q0q1q2q2q2q2q3q2q2q3q3 u=aa v=c w=cbcba b) aacbbaa a a c b b a a q0q1q2q2q2q3q2q3q3q3 u=aa v=c w=bbaa c) aabbaaa a a b b a a a q0q1q2q2q3q2q3q3q3q3 u=aab v=b w=aaa d) aacbcbb a a c b c b b q0q1q2q2q2q3q2q2q3q2q3 u=aa v=c v=bcbb e) aacbbba a a c b b b a q0q1q2q2q2q3q2q3q2q3q3 u=aa v=c w=bbba

Lucrarea Nr.3 EPS004. Să se elimine ε producţiile. G = (VN , VT , P, S), VN= {S, L, A, I}, VT = {a,b} P= { 1. S→ L 2. L→ A I 3. L→ a A 4. L→ L a A I 5. L→ L b I 6. A→ a I b 7. A→ I 8. I→ b 9. I→ ε } Algoritmul de eliminare ε – producţii 1.Construim Nε 2.Initial P=P\{A→ ε} Eliminam din P toate ε-productii 3.Pentru toate productiile A→ α din P si toate combinatiile posibile 4.Repetam pasul 3 cat timp apar productii noi in P. 5.Daca S∈Nε(ε∈L(b))atunci P=P∪{ S→ ε}

1.Eliminam ε – producţii Nε={} Nε={I} Nε={I,A} Nε={I,A,L} Nε={I,A,L,S} 1.S→L 2.L→AI L→A L→I 3.L→aA L→a 4.L→LaAI L→aAI L→LaI L→LaA L→aA L→La L→aI L→a 5.L→LbI L→Lb L→bI L→b 6.A→aIb A→ab A→aI

Lucrarea Nr.4 FNC004. Să se reducă la Forma Normală Chomsky gramatica independentă de context G = (VN , VT , P, S), VN= {S, L, A, I}, VT = {a,b} P= { 1. S→ L 2. L→ A I 3. L→ a A 4. L→ L a A 5. L→ L b I 6. A→ a I b 7. I→ b 8. I→ ε}. Eliminăm ε producţii: 1. Nε={} Nε={I} 2. S→L -redenumire L→AI L→A -redenumire L→aA L→LaA L→LbI L→Lb A→aIb A→ab I→ b Eliminam redenumirile 1.Rs={S} 2.S→L L→A S→AI S→aA

RL={L} RA={A} RL=RL U RS={L,S} RA=RA U RL={A,L,S}

S→LaA S→LbI S→Lb L→AI L→aA L→LaA L→LbI L→Lb A→aIb A→ab S→aIb S→ab L→aIb L→ab I→b Aducem la forma normala Chomsky S→AI S→XA X→a S→QA Q→LX S→LM M→YI Y→b S→LY L→AI L→XA L→QA L→LM A→XC C→IY A→XY S→XC S→XY L→XC L→XY I→b

Lucrarea Nr.5 REC004. Să se elimine recursia stângă. G = (VN , VT , P, S), VN= {S, L, A, I}, VT = {a,b} P= { 1. S→ L 2. L→ A I 3. L→ a A 4. L→ L a A I 5. L→ L b I 6. A→ a I b 7. A→ A I 8. I→ b 9. I→ a L }. Pentru S nu este recursie stanga Pentru L: a)L→LaAI b) L→AI a1)L→AIX a2)X→aAI a3)X→ aAIX b) L→AI Pentru A: A→aIb A→AI a1)A→aIbY a2)Y→I a3)Y→IY b)A→aIb S→L L→AIX L→Aax X→aAI X→bI X→ aAIX X→bIX L→AI L→aA A→aIbY Y→I Y→IY A→aIb

L→LbI L→aA L→aAX X→bI X→bIX L→aA

Lucrarea Nr.6 FNG004. Să se reducă la forma normală Greibach gramatica independentă de context G=(VN, VT, P, S,), VN={S, A, B, C}, VT ={a, b}, P={ 1. S → B C A3→ A3A2A2 –recursie stinga 2. C → B B A3→a 3. C → a A3→aX 4. A → b A1→b 5. B → C A A2→A3A1 } 1. S → B C 2. C → B B 3. C → a 4. A → b 5. B → C A Notam

A0 = S A1 = A A2 = B A3 = C A0→A2A3 A3→A2A2 A3→a A1→b A2→A3A1 Pentru i=0: A0→A2A3 Pentru i=3: A3→A2A2 -teorema substitutiei A3→a Pentru i=1: A1→b Pentru i=2: A2→A3A1 A0→A2A3

A3→a A3→aX X→A1A2 X→A1A2X i=3 A3→a A3→aX X→bA2 X→bA2X i=2 A2→aA1 A2→aXA1 i=1 A→b i=0 A0=aA1A2 A0=aXA1A2

FNG A3→a A3→aX X→bA2 X→bA2X A2→aA1 A2→aXA1 A0→aA1A2 A0→aXA1A2

Lucrarea Nr.7 UVWXY004. Este dată gramatica independentă de context : G=(VN, VT, P, S,), VN={S, A, B}, VT ={a, b}, P={ 1. S → B S 2. S → A S 3. S → a 4. A → A S 5. A → a 6. B → S B 7. B → b }. a) Construiţi un cuvânt arbitrar z, care aparţine limbajului L(G), | z | ≥ 8; b) Aplicând teorema “uvwxy” construiţi reprezentarea z= uvwxy. Z=aaaabaaa S B A a

S B A S

S b A S B

a

S a a

S

B

a

a

a

u=aa v=a w=abaa

Lucrarea Nr.8 AS004. Este dat limbajul L= { an-2bdcn | n>=2}. a) Construiţi gramatica independentă de context G care generează limbajul L. Construiţi derivările şirurilor x1 (n=2), x2 ( n=3) şi x3 (n=4). b) Construiţi automatul cu memorie stivă care acceptă limbajul L. Arătaţi secvenţele de acceptare pentru şirurile şirurile x1, x2 şi x3. Gramatica independent de context: Pentru n=2:bdcc Pentru n=3:abdccc Pentru n=4:aabdcccc

Automatul cu memorie stiva care accepta limbajul:  (q0,z0,a) = (q0,az0)

 (q0,z0,b) = (q0,az0)  (q0,a,b) = (q0,aa)  (q0,a,d) = (q1,aa)  (q1,a,c) = (q1, ε)  (q1,z0, ε) = (q1, ε) n=2 :bdcc (q0,z0,bdcc)—(q0,az0,dcc)—(q1,aaz0,cc)—(q1,az0,c)—(q1,z0, ε) —(q1, ε) — acceptare. n=3:abdccc (q0,z0,abdccc) —(qo,azo,bdcc) —(q0,aaz0,dccc) —(q1,aaaz0,ccc) — (q1,aaz0,cc) —(q1,az0,c) —(q1,z0, ε) —(q1, ε) — acceptare. n=4:aabdcccc (q0,z0,aabdcccc) —(q0,az0,abdcccc) —(q0,aaz0,bdcccc) —(q0,aaaz0,dcccc) — (q1,aaaaz0,cccc) —(q1,aaz0,ccc) —(q1,aaz0,cc) —(q1,az0,c) —(q1,z0, ε) — (q1, ε) —acceptare. Lucrarea Nr.9 PRSMP008. Este dată gramatica independentă de context : G=(VN, VT, P, S,), VN ={S, A, F, E}, VT ={a,b,c,d,e}, P={ 1. S → A 2. A → F 3. A → E c F 4. F → a 5. F → b 6. F → d E 7. E → A e Să se construiască matricea relaţiilor de precedenţă şi să se analizeze şirul daeecdbe

S A F E

PRIM A,F,E,a,b,d F,E,a,b,d,A a,b,d A,F,E,a,b,d

ULTIM A,F,a,b,E,e F,a,b,E,e a,b,E,e e

EQ = {(Ec),(cF),(dE),(Ae)}

}.

1. (Ec)=>E=c ULTIM(F)>c=>e>c 2. (cF)=>c=A cc c = < < < d < < < < < < e > > > $ < < < < < < ($,daeecdbe,$)—D($d,aeecdbe,$)—D($da,eecdbe,$)—R4($dF,eecdbe,$)— R2($dA,eecdbe,$)—D($dAe,ecdbe,$)—R7($dE,ecdbe,$) —R6($F,ecdbe,$)— R2($A,ecdbe,$)—D($Ae,cdbe,$)—R7($E,cdbe,$)—D($Ec,dbe,$)—D($Ecd,be,$) — D($Ecdb,e,$)—R5($EcdF,e,$)—R2($EcdA,e,$)—D($EcdAe,$)—R7($EcdE,$) — R6($EcF,$)—R2($A,$)—($S,$)—acceptare

Lucrarea Nr.10 LL(1)007. Este dată gramatica independentă de context G=(VN, VT, P, S,), VN ={S, A, E, R, D, X, Z}, VT ={a,b,c,d}, P={ 1. S → A 2. A → c E 3. E → R d 4. R → D X 5. X → ε 6. X → b D X 7. D → a Z 8. Z → ε 9. Z → c R d Să se construiască tabelul de analiză LL(1) şi să se analizeze şirul

X S A E

FR(X) c c a

FL(X) $ $ $

}.

1.S→A 2.A→cE 3.E→Rd 4.R→DX 5.X→ε 6.X→bDX 7.D→aZ 8.Z→ε 9.Z→cRd

R X D Z

a b,ε A c,ε

Nε={X,Z} a a

b

c

d

SD(α) c c a a d b a b,d c

$

V

c

V

d

V

$

S

S

1

A

2

E

3

R

4

X

Z

1.S→A 2.A→cE 3.E→Rd 4.R→DX 5.X→ε 6.X→bDX 7.D→aZ 8.Z→ε 9.Z→cRd

V

b

D

d d b,d b,d

2 6

5

7 8

9

8

Analiza şirului caadbad: (S$,caadbad$)—1(A$,caadbad$)—2(cE$,caadbad$)—V(E$,aadbad$)— 3(Rd$,aadbad$)—4(DXd$,aadbad) —7(aZXd$,aadbad) —V(ZXD$,adbad) — sirul nu este acceptat Analiza sirului cabad

(S$,cabad$)—1(A$,cabad$)—2(cE$,cabad$)—V(E$,cabad$)— 3(Rd$,cabad$)—4(DXd$,abad) —7(aZXd$,abad) —V(ZXD$,bad) — 8(XD$,bad) —6(bDXd$,bad) —V(DXd$,ad) —7(aZXd$,ad) —(ZXd$,d) — (ZXd$,d)—8(Xd$,d) —5(d$,d)-acceptare