lfa

Limbaje formale s, i automateLaborator 1

1. Să se rezolve problema verificării parantezelor. Să se citească o expresiearitmetică de la tastatură cont, inând numere(operanzi), operatori (+,-,*, /,∧ ) s, i paranteze ( (, ),[,],{,} ). Cu ajutorul unei stive să se verificecorectitudinea expresiei.Exemplu: 12 ∗ {[(4 + 5)/(4 − 1)] ∧ 2 − 4} − 10

CaracterCont,inut stivăOperat,ia asupra stivei

1 ∅

2 ∅

* ∅

{ { push

[ {[ push

( {[( push

4 {[(

+ {[(

5 {[(

) {[ pop,dacă top=(

/ {[

( {[( push

4 {[(

- {[(

1 {[(

) {[ pop,dacă top=(

] { pop,dacă top=[

2 {

- {

4 {

} ∅ pop,dacă top={

- ∅

1 ∅

0 ∅

Dacă s-a parcurs expresia s, i stiva rămâne goală înseamnă că expresiaeste corectă, altfel expresia este incorectă.

1

2. Să se transforme o expresie din forma infix cu paranteze în forma po-loneză inversă (formă postfix) folosind o stivă s, i o coadă, apoi să seevalueze expresia obt, inută, folosind o altă stivă.

a. se cites,te expresia de la tastatură

b. se verifică corectitudinea parantezelor (vezi Problema 1.)

c. se creează forma poloneză inversă

d. se evaluează expresia

Observat, ie:

- formă infix ($10 + 25)

- formă postfix $10 25 + (unde $ reprezintă semnul minus)

Notat, ia postfix nu necesită paranteze s, i poate fi evaluată us,or cu o stivă.Algoritmul de transformare din infix în forma poloneză inversă

(postfix)Expresia este parcursă caracter cu caracter. Dacă caracterul actual este pa-ranteză deschisă ((,[,{) sau operator (+,−, ∗, /,∧) atunci el se pune în stivă.Dacă este operand se pune într-o coadă de s, iruri de caractere (coadă post-fix). Dacă caracterul actual este o paranteză închisă, atunci se scot din stivăoperat, iile până la cea mai apropiată paranteză deschisă (până la perecheasa).Atent, ie în cazul operatorilor avem o except, ie, un operator mai put, in

prioritar nu se poate pune peste un operator mai prioritar. (operatorii adi-tivi nu pot veni exact după un operator multiplicativ sau putere, respectivoperatorii multiplicativi un pot fi puse în stivă peste operatorul putere). Înacest caz se scoate din stivă operatorul mai prioritar s, i se pune în coada post-fix s, i se pune în stivă în locul lui operatorul mai put, in prioritar. Dacă aces,tioperanzi nu sunt unul peste celălalt în stivă, ci sunt despărt, ite de paranteze,atunci această regulă nu se aplică.

Evaluarea expresiei din coada postfixSe spun pe rând operanzii (numerele) în stiva de evaluare, dacă vine un ope-rator el nu se pune în stiva de evaluare, ci se scot două (în cazul operatoruluibinar) operanzi din stivă se execută operat, ia între ele (operand2 <operat, ie>operand1)s, i rezultatul lor se pune înapoi în stivă. În final un număr varămâne în stivă, care va fi de fapt valoarea expresiei.

2


Not, iuni introductive

1. Alfabet (vocabular): O mult, ime finită s, i nevidă de elemente. Notat, ie:V

2. Simbol (literă): Un element al alfabetului V. Notat, ie: litere mici

3. Cuvânt peste alfabetul V: S, ir finit constând din 0 sau mai multe simbo-luri ale lui V, unde un simbol poate să apară de mai multe ori. Notat, ie:w

4. Cuvânt vid: λ sau ε

5. Mult, imea tuturor cuvintelor din alfabetul V: V + = V ∗\{λ}

6. Concatenare: w1w2 s, i Putere: wi = wi−1w s, i w0 = λ

7. |w|: lungimea cuvântului w

8. Na(w): Numărul de aparit, ii al simbolui a în cuvântul w.

9. Limbaj peste alfabetul V:L ⊂ V∗ o submult, ime de s, iruri.Limbajul vid Φ nu cont, ine niciun cuvânt, iar Lλ = {λ} cont, ine unelement, deci nu este vid

10. Exsită două reprezentări ale limbajelor:

- : în cazul limbajului finit cuvintele pot fi enumerate

- : în cazul limbajului infinit cuvintele sunt descrise printr-un meca-nism generativ

1

11. Sistem de rescriere: SR = (V, F ), unde w ∈ V s, i (α, β) ∈ F . Elemen-tele lui F sunt reguli de rescriere sau product, ii. Notat, ie α → β

12. α ⇒ β : Dacă există o secvent,a prin care obt, inem din α, folosindregulile de resciere, pe β

13. Gramatică: Un quadruplu format din G = (VT , VN , S, P )

- VT : mult, imea terminalelor, o mult, ime finită. Se notează cu literemici

- VN : mult, imea netermimalelor, o mult, ime finită. Se notează cu literemariVT ∩ VN = ∅

- : S simbol de start, S ∈ VN

- : P product, ii sau reguli de derivare

Cuvintele (w, u, v, . . . ) cont, in totdeauna numai terminali w ∈ T ∗

α, β, . . . sunt s, iruri care cont, in s, i terminali s, i neterminali.α ∈ (N ∪ T )∗

Probleme propuse

1. Să se enumere cuvintele peste alfabetul V = {a, b, c} astfel încât

- niciun simbol să nu se repete

- lungimea cuvintelor să fie cel mult 3

2. Să se detemine următoarele cuvinte αβ, βα, α2β, β2α, α2β2, α2λβ2, dacăα = ab s, i β = bc

3. Să se construiască gramatica pentru generarea limbajului

L = {aibi, unde i > 0}

4. Se dă următoare gramatică G = ({a, b, c}, {S,B}, S, P )

P:

S → aSBc|λcB → BcaB → abbB → bb

Să se derive cuvântul a3b3c3.

2

5. Ce limbaj generează următoarea gramatică G = ({a, b, c, d}, {S,A}, S, P )

P:S→ aSd|aAdA→ bAc|bc

6. Să se schimbe product, iile de la punctul anterior astfel încât limbajulgenerat să fie:

L = {aibicjdj , unde i > 0, j > 0}

7. Să se construiască o gramatică pentru generarea s, irurilor formate din0 s, i 1, cu lungimea s, irului multiplu de 3.

8. Să se construiască gramatica pentru generarea limbajului

L = {w ∈ {0, 1}∗, w nu cont, ine s, irul 101}

9. Să se găsească gramatica pentru expresii aritmetice. Simbolurile termi-nale sunt: a, +, ∗, (, ). Gramatica să genereze numai expresii aritmeticevalide ca de exemplu (a + a) ∗ a.

10. Să se scrie un program care verifică egalitatea simbolurilor a s, i b încuvintele peste alfabetul V = {a, b} folosind o stivă. Cuvântul se in-troduce de la tastatură. Să se extindă programul astfel încât să verificeegalitatea simbolurilor a, b s, i c în cuvintele peste alfabetul V = {a, b, c}.

3


Ierarhia lui Chomsky

a. gramatici de tip 0 - fără restrict, ii α → β, unde α, β ∈ (VT ∪ VN)∗

b. gramatici de tip 1 - gramatici dependente de context (DC)αAβ → αγβ, unde α, β, γ ∈ (VT ∪ VN )∗ s, i A ∈ VN

avem o except, ie S → λ

c. gramatici de tip 2 - gramatici independente de context (IDC)A → α, unde A ∈ VN s, i α ∈ (VT ∪ VN )∗

d. gramatici de tip 3 - regulate (R)A → aB sau A → a, unde A,B ∈ VN , B ∈ VN s, i a ∈ V +

T

Observat, ie: (R) ⊆ (IDC) ⊆ (DC) ⊆ (0).

Probleme propuse

1. Se dă gramatica G = {VT , VN , S, P}, unde VT = {a, b}, VN = {S,A,B,C}

s, i P:

S→ aA|bB|bA→ aS|bCB→ aC|bSC→ aB|bA|a

Ce limbaj generează gramatică?

2. Se dă gramatica G = {VT , VN , S, P}, unde VT = {a, b}, VN = {S, S1, S2}

s, i P:

S→ S1S2|λS1 → aS1b|λS2 → bS2c|λ


1

3. Se dă gramatica G = {VT , VN , S, P}, unde VT = {b, c}, VN = {S,B,C}

s, i P:

S→ aSBC|abCCB→ BCbB→ bbbC→ bccC→ cc


4. Să se afle gramatica peste alfabetul V = {a, b} care generează limbajulcu următoarele proprietăt, i:

a. Na = 2k s, i Nb = 2k, k ∈ N

b. Na = 2k + 1 s, i Nb = 2k, k ∈ N

c. Na = 2k s, i Nb = 2k + 1, k ∈ N

d. Na = 2k + 1 s, i Nb = 2k + 1, k ∈ N

5. Să se construiască gramaticile care generează limbajele:

a. L< = {aibj , i, j > 0, i < j}

b. L> = {aibj , i, j > 0, i > j}

c. L = {aibj , i, j > 0, i 6= j}

Să se construiască gramaticile care generează limbajele:

6. L = {ambn, n < m sau n > 2m,n,m > 0}

7. V = {a, b, c} tot, i simboli a apar înainte de tot, i simboli b s, i tot, i simbolib apar înainte de tot, i simboli c.

8. L = {xx−1|x ∈ {a, b}∗}

9. Să se determine gramatica care generează mult, imea numerelor naturale,mult, imea numerelor întregi s, i mult, imea numerelor reale.

10. Să se scrie un program care afis,ează cont, inutul unui fis, ier text. Cautăprima aparit, ie a unui cuvânt dat de la tastatură. La cerere (apăsareaunei taste) căutarea se continuă cu următoarele aparit, ii ale cuvântuluidat.

2


Transformări de gramatici de tip II (Indepen-dente de context)

1. Eliminarea λ-product, iilor

2. Eliminarea recursivităt, ii stânga

3. Eliminarea simbolurilor neterminale neutilizate

4. Substitut, ia de începuturi

1 Eliminarea λ product, iilor

O gramatică se numes,te λ-free, dacă satisface următoarele condit, ii:

- @ product, ie care să aibă în partea dreaptă s, irul vid, adică λ.

- Avem o singură except, ie, din simbolul de start putem deduce λ, adicăS → λ este permis.

Algoritmul de transformare a unei gramatici în gramatică λ-free:

1. Se construies,te mult, imea neterminalelor care pot fi transformate în λdirect sau indirect.

2. După ce se obt, ine ultima mult, ime Nn, atunci simbolurile aflate înmult, ime pot fi substituite cu λ.

1

Exemplu

Fie gramatica G = ({a, b, }, {S,A,B,C}, S, P ), unde P:

S→ ABCA→ BB|λB→ CC|aC→ AA|b

Primul neterminal înlocuibil direct cu λ este A.3.⇒ N0 = {A}. Dacă A poate

fi înlocuit cu λ atunci s, i C poate fi înlocuit cu λ.N0 = {A}N1 = {A,C}N2 = {A,C,B}N3 = {A,C,B, S}Dacă S ∈ N3 atunci se introduce o nouă product, ie S ′ → S|λ. S ′ va fi noulsimbol de start.Se rescriu product, iile, astfel încât fiecare neterminal aflat în mult, imea N3 săfie înlocuit pe rând cu λ. Obt, inem setul de reguli:S ′ → S|λS→ ABC|BC|AC|AB|A|B|CA→ BB|BB→ CC|C|aC→ AA|A|b

2 Eliminare simbolurilor neterminale neutilizate

O gramatică poate să cont, ină simboluri neterminale în plus, care pot fi eli-minate fără a afecta gramatica.

- Un simbol neterminal este în plus, dacă din el nu ajungem niciodatăla un cuvânt (o formă finală care să cont, ină doar terminale). Acestsimbol se numes,te neterminal nefinalizat.

- Un simbol neterminal este redundant, dacă pornind de la S folosindorice regulă posibilă pe parcursul derivării nu apare niciodată acel sim-bol. Acest simbol se numes,te neterminal inaccesibil.

Eliminarea neterminalelor neutilizate atrage după sine eliminarea netermi-nalelor nefinalizate s, i inaccesibile.

2

Exemplu

S→ aA|bBA→ cA|dA|CAB→ bB|bC→ eaC|eD→ dBd|ede

Pasul I:

Pormind de la VT construim mult, imile T . T0 = {a, b, c, d, e} Acestămult, ime se completează pas cu pas cu terminalele din care pot fi deduseelementele mult, imii anterioare.T1 = {a, b, c, d, e, B, C,D}T2 = {a, b, c, d, e, B, C,D, S}Mult, imea T2 nu poate fi completată cu alte neterminale. A /∈ T2, ⇒ Aeste un simbol nefinalizat (nu produce niciodată cuvânt).Product, iile care cont, in A pot fi eliminate.Obt, inem:S→ bBB→ bB|bC→ eaC|eD→ dBd|ede

Pasul II:

Pornind de la S construim mult, imile N. N0 = {S}.N1 = {S, b, B}. Simbolurile nu C,D nu pot fi deduse din elementelemult, imii N1, deci ele sunt inaccesibile, deci se elimină din gramatică:Gramatica finală fără simboluri neutilizate devine astfel:

G = ({b}, {S,B}, S, P ), unde P:

{S→ bBB→ bB|b

3 Eliminarea recursivităt, ii stânga

Se numes,te gramatică recursivă stânga o gramatică care cont, ine un netermi-nal A, astfel încât să existe relat, ia:

A+⇒ Aβ, unde β ∈ (VT ∪ VN )∗

Recursivitatea poate fi directă (evidentă): product, ia are forma A → Aβ, sauindirectă: pe parcursul derivării ajungem după k pas, i la o astfel de formă Aβ.

3

9.S→ Aa|aSbA→ Ac|λ

6


Automate finite

Un automat finit notat cu M = (Q, Σ, δ, q0, F ) este format din:

- Q mult, imea stărilor, o mult, ime finită s, i nevidă

- Σ : alfabet finit de intrare

- δ: o aplicat, ie numită funct, ie de tranzit, ie, care atas,ează unei stări s, i aunui simbol de intrare o nouă stare δ : Q × Σ → Q, adică trece dintr-o stare într-o altă stare, dacă pe banda de intrare automatul cites,tesimbolul corespunzător. Exemplu: δ(q0, a) = q1

- q0: starea init, ială

- F ⊂ Q mult, imea stărilor finale

Automatul analizează fiecare cuvânt (cites,te literele cuvântului) de la stângala dreapta.

Cuvânt acceptat : Un cuvânt este acceptat/recunoscut de automat, dacă auto-matul pornind din starea init, ială se va opri într-o stare finală după prelucra-rea întregului cuvânt. În cazul în care nu există tranzit, ie dintr-o stare în cea-laltă cu ajutorul simbolului citit, atunci automatul se blochează. δ(qi, a) = ∅.

Limbaj acceptat : Limbajul acceptat de un automat finit este mult, imea tutu-ror cuvintelor acceptate de acel automat.

Configurat,ie instantanee : Numim configurat, ie instantanee perechea (q0, x),

1

adică starea actuală a automatului s, i s, irul de caractere din cuvântul rămasîncă necitit (neanalizat). Dacă un automat foloses,te tranzit, ia δ(q, a) = p,atunci notăm modificarea configurat, iei astfel (q, aα) ` (p, α).Un automat poate fi definit prin tabelul de tranzit, ie sau prin diagrama destare (diagrama de tranzit, ie).

Exemplu

Fie M = (Q, Σ, q0, F ), unde Q = {q0, q1, q2, q3} Σ = {a, b, c} s, i F = {q3}

δ a b cq0 q1

q1 q1 q2

q2 q2 q3

q3 q3 Diagrama corespunzătoare tabeluluide tranzit, ii

Simularea acceptării unui cuvânt: Fie cuvântul de intrare aaabbbbcc. Primaconfigurat, ie este δ(q0, aaabbbbcc). Cuvântul va fi acceptat, dacă automatuldupă prelucrarea completă a cuvântului se opres,te în configurat, ia δ(q3, λ).δ(q0, aaabbbbcc) ` δ(q1, aabbbbcc) ` δ(q1, abbbbcc) ` δ(q1, bbbbbcc) ` δ(q2, bbbcc)` δ(q2, bbcc) ` δ(q2, bcc) ` δ(q2, cc) ` δ(q3, c) ` δ(q3, λ).Cuvântul este acceptat întrucât am ajuns în starea finală s, i cuvântul a fostprelucrat în întregime.

Automat finit nedeterminist AFN : Un automat finit nedeterminist este for-mat din tranzact, ii prin care dintr-o stare cu acelas, i simbol citit se poateajunge în mai multe stări.Automat finit determinist AFD : Un automat finit determinist este formatdin tranzact, ii prin care dintr-o stare cu acelas, i simbol citit se poate ajungeîn cel mult o stare.

Teoremă 1 : Fie L limbajul acceptat de un AFN atunci există un AFD careacceptă L.

Teoremă 2 : Fie G = (VN , VT , S, P ) o gramatică de tip 3 (regulată),atunci există AFN M = (Q, σ, q0, F ) cu T(M)=L(G).

Teoremă 3 : Fie M = (Q, σ, q0, F ) AFN atunci există G = (VN , VT , S, P )o gramatică de tip 3 astfel încât L(G)=T(M).

2

Metoda de transformare a unui limbaj regulatîn automatul finit echivalent

Gramatică regulată dreaptaA → aB sau A → a

Gramatică Automat

VN neterminale Q stări ∪ F stare finalăVT terminale Σ (alfabet de intrare)

A → aB δ(A, a) = BA → a δ(A, a) = F (F stare finală)A → λ A va fi stare finală

S simbol de start S stare init,ială

Automat Gramatică

Q stări VN neterminaleΣ (alfabet de intrare) VT terminale

δ(A, a) = B A → aBδ(A, a) = F (stare finală) A → aPt. ∀ stare finală F F → λq0 stare init,ială S simbol de start

Gramatică regulată stângaA → Ba sau A → a

Gramatică Automat

VN neterminale Q stări ∪ q0 stare init,ialăVT terminale Σ (alfabet de intrare)

A → Ba δ(B, a) = aA → a δ(q0, a) = A (q0 stare init,ială)A → λ A va fi stare init,ială

S simbol de start S stare finală

3

Automat Gramatică

Q stări VN neterminaleΣ (alfabet de intrare) VT terminale

δ(B, a) = A A → Baδ(q0, a) = A (q0 stare init,ială) A → a

Pt. ∀ stare init,ială q0 q0 → λF stare finală S simbol de start

Limbajul regulat dreapta pentru automatul dat în exeplul precedent:q0 : Sq1 : Aq2 : Bq3 : CS → aAA → aA|bAB → bB|cCC → cCpt. δ(B, c) = C introducem B → C vezi linia 4 din tabelul 2.pt. q3 stare finală introducem C → λ vezi linia 5 din tabelul 2.

Probleme propuse

1. Se dă automatul:

4

Să se determine dacă cuvintele sunt acceptate: 1010, 0110, 010011.

2. Fie G=({S,B},{0,1},S,P) unde P:

{S→ 0BB→ 0B|1S|0

Să se construiască M care acceptă limbajul L generat de gramatica G.

3. Să se creeze automatul finit nedeterminist pentru problemele din Labo-ratorul2 (3,4,5,6,7,8), Laboratorul3 (1,3,4,5,6,7,8,9). Să se deducă câteun cuvânt acceptat s, i respins.

5


Transformarea unui AFN în AFD

Un automat finit determinist notat cu M = (Q, Σ, δ, q0, F ) este format din:



- δ: o aplicat, ie numită funct, ie de tranzit, ie δ, care atas,ează unei stări s, ia unui simbol de intrare o nouă stare δ : Q × Σ → Q, adică trecedintr-o stare într-o altă stare, dacă pe banda de intrare automatulcites,te simbolul corespunzător. Exemplu: δ(q0, a) = q1



Automat finit determinist AFD : Un automat finit determinist este formatdin tranzit, ii prin care dintr-o stare cu un anumit simbol citit se poate ajungeîn cel mult o stare.

Un automat finit nedeterminist notat cu M = (Q, Σ, δ, q0, F ) este formatdin:



1

- δ: o aplicat, ie numită funct, ie de tranzit, ie δ, care atas,ează unei stări s, i aunui simbol de intrare mai multe stări, o submult, ime de stări P(Q) ⊂ Q, adică δ : Q × Σ → P(Q), tranzit, ie dintr-o stare în mai multestări, dacă pe banda de intrare automatul cites,te un anumit simbolul.Exemplu: δ(q0, a) = q1, δ(q0, a) = q2



Automat finit nedeterminist AFN : Un automat finit nedeterminist este for-mat din tranzit, ii prin care dintr-o stare cu un anumit simbol citit se poateajunge în mai multe stări.

AFN poate accepta un cuvânt de intrare parcurgând mai multe secvent,ede tranzit, ii ale automtului. Pot exista mai multe drumuri (ramuri) care ac-ceptă acelas, i cuvânt. (Tipul de atribuire: unu la mai multe).Un AFN acceptă un cuvânt, dacă există cel put, in un drum de tranzit, ii astfelîncât după prelucrarea cuvântului automatul să fie într-o stare finală.

În cazul AFD unui cuvânt i se atribuie doar o sigură modalitate de acceptare(secvent,ă de tranzit, ii) . (Tipul de atribuire: 1 la 1).

Teoremă 1 Pentru orice AFN există un AFD echivalent cu acesta.

Algoritmul de transformare al unui AFN în AFD

- AFD foloses,te o singură stare init, ială care colectează toate stările init, ialedin AFN.

- O stare este finală în AFD dacă s, i numai dacă cont, ine cel put, in o starefinală din AFN. AFD poate să aibă mai multe stări finale.

- Se elimină nedeterminismul, dacă pentru fiecare tranzit, ie care dintr-ostare s, i un simbol citit ajunge în mai multe stări, comasăm stările t, intă.Exemplu : AFN δ(q0, a) = q1 s, i δ(q0, a) = q2 atunci în AFD vom aveaδ(q0, a) = {q1, q2}

not.= q1,2

2

Exemplu

Fie M = (Q, Σ, q0, F ), unde Q = {q0, q1} Σ = {0, 1} s, i F = {q1}

δ 0 1q0 {q0, q1} q1

q1 {q0, q1}

Diagrama corespunzătoare tabeluluide tranzit, ii

Determinalizat

δ 0 1q0 {q0, q1} q1

q1 {q0, q1}

{q0, q1} {q0, q1} {q0, q1}


Eliminarea λ-tranzit, iilor

O λ-tranzit, ie are forma δ(q0, λ) = q1, adică fără a citii un simbol de pe bandade intrare putem trece în starea următoare.λ-tranzit, ii reprezintă un nedeterminism, pentru că necitind simbol automatulpoate să rămână în starea curentă sau dacă există λ-tranzit, ie poate trece înstarea următoare. Adică δ(q0, λ) = q0 sau δ(q0, λ) = q1. Avem nedeterminismîntrucât cu ajutorul unui simbol λ ajungem în mai multe stări.

3

Algoritmul de eliminare a λ-tranzit, iilor

Starea de plecare a λ-tranzit, iei va fi comasată cu starea t, intă a tranzit, iei.Toate tranzit, iile care pornesc din starea t, intă vor porni s, i din starea coma-sată. Creem λ-închiderea pentru fiecare stare: q′ = λ({q})

Exemplu

δ a b c λq0 q1

q1 q1 q2

q2 q0


Determinalizat (λ-free)Determinăm λ-închiderea fiecărei stăriq′0 = λ(q0)=q0

q′1 = λ(q1)=q1

q′2 = λ(q2)={q2, q0}

δ a b cq′0 = q0 q1

q′1 = q1 q1 {q2, q0}

q′2 = {q2, q0} q1

Diagrama corespunzătoare ta-belului de tranzit, ii

4

Probleme propuse

Să se transforme AFN în AFD.

1.

2.

5

3.

4.

5.

6

6. Să se scrie un program care cites,te dintr-un fis, ier datele unui automatfinit determinist. (Prima linie cont, ine stările automatului separate prinspat, iu, a doua linie cont, ine alfabetul, a treia linie starea init, ială, a patralinie stările finale separate prin spat, iu, următoarele linii câte o tranzit, ie:stare literă stare). Se cere de la tastatură un cuvânt. Să se verifice dacăautomatul acceptă cuvântul dat.Indicat, ie: Printr-o matrice se va reprezenta tabelul de taranzit, ii δ(i, j) =m[i][j], unde i este indicele rândurilor, adică a stărilor, j este indicelecoloanelor, adică simbolul alfabetului, iar valoare m[i][j] va fi stareaurmătoare.

algoritmciclu parcugere s, ir

daca m[stare_actuala][sir[indice_litera_actuala]] 6= ∅ atuncistare_actuala= m[stare_actuala][sir[indice_litera_actuala]]incrementare indice_litera_acuala

altfel stop cuvânt inacceptatsf. daca

sf. ciclucuvânt acceptatsf. algoritm

7


Minimizarea unui AFD

Fiecărui AFD îi corespunde un AFD minim, care acceptă acelas, i limbaj, darcont, ine un număr minim de stări.Există două surse de minimizare:

1. elimiarea stărilor inaccesibile

2. comasarea stărilor care au acelas, i comportament, adică sunt echivalenteîntre ele.

Definit, ie 1 O stare este inaccesibilă, dacă nu există nicio secvent,ă de tranzit,iiprin care să ajungem din starea init,ială în această stare.

Definit, ie 2 Un AFD M = (Q, Σ, δ, q0, F ) s, i două stări q1 s, i q2 . Spunemcă un cuvânt x ∈ Σ∗ distige stările q1 s, i q2, dacă din q1 după citirea cuvântu-lui ajungem într-o stare q3 finală(nefinală) s, i din q2 după citirea cuvântuluiajungem într-o stare q4 nefinală(finală), adică:(q1, x) `∗ (q3, λ) s, i(q2, x) `∗ (q4, λ)unde q3 ∈ F s, i q4 /∈ F sau invers q3 /∈ F s, i q4 ∈ F .

1

Algoritmul de minimizare al unui AFD vezi exemplul

Exemplu

Fie automatul:

Primul pas grupăm stările în două grupe finale s, i nefinale.

1 ≡ 1 2q1 q2 q3 q4 q0 q5

a 1 1 1 1 2 2b 1 2 2 1 1 1

2 ≡ 1 2 3q1 q4 q2 q3 q0 q5

a 1 1 2 2 3 3b 2 2 3 3 1 1

Nicio clasă de echivalent,ă nu poate fi separată, deci q1 ≡ q4 s, i q2 ≡ q3 s, iq0 ≡ q5. Nou automat cont, ine 3 stări q0, q1 s, i q2.

2

Probleme propuse

Să se găsească AFD minim pentru următoarele AFD

1.

2.

3

3.

4.

4

5.

6.

5


Expresii regulate

Se numes,te expresie regulată o expresie care poate fi construită cu următoa-rele reguli:

− λ expresie regulată ce defines,te s, irul vid

− a ∈ VT expresie regulată ce descrie limbajul format dintr-un singurcuvânt de lungime 1. L = {a}

− e1 s, i e2 sunt expresii regulate indicând limbajele L1 s, i L2 atunci

• Alternare (sau) e1|e2 este o expresie regulată ce indică limbajulL1 ∪ L2

• Concatenare (s, i) e1e2 indicând limbajul produs L1 ∙ L2

• e∗ închiderea Kleene indicând limbajul L(e)∗, adică {λ, e, ee, eee, . . . }

Exemplu: (a|b)∗abb înseamnă a sau b de oricâte ori, dar cuvântul trebuie săse termine cu s, irul abb.

Expresii regulate s, i gramatici regulate

Definit, ie 1 O expresie regulată defines, te un limbaj, o gramatică genereazăun limbaj, dacă limbajul definit de expresia regulată coincide cu limbajul ge-nerat de gramatică, atunci expresia regulată este echivalentă cu gramatica.

Notat, ie: a+ = aa∗ (cel put, in un a)

1

Exemplu

1. Fie expresia regulată (a|b)∗abb. Să se determine gramatica regulată

echivalentă cu acesta.S → AaabA → aA|bA|λ

2. Variabilă în limbajul C: începe cu literă s, i cont, ine literă cifră s, i _ Ex-presia regulată corespunzătoare: <variabilă>=<literă>(<literă>|<cifră>|_) ∗

unde <literă>= a|b|c| . . . |z|A|B|C| . . . |Z s, i<cifră>= 0|1|2| . . . |9Gramatica corespunzătoare:<variabilă>→ a<literăcifrăbară>|b<literăcifrăbară>|. . . |Z<literăcifrăbară>

|a|. . .Z<literăcifrăbară>→ a<literăcifrăbară>|b<literăcifrăbară>|. . . |Z<literăcifrăbară>

0<literăcifrăbară>|2<literăcifrăbară>|. . . |9<literăcifrăbară>|a|. . .Z|0|1|. . . |9

Algoritm de transformare a unei expresii regu-late într-o gramatică regulată

Fie ecuat, ia X = αX|β are solut, ie unică X = α∗β

Exemplu (din gramatică obt, inem expresia regulată)

S→ aS

S→ aB

B→ bC

C→ aC

C→ a

Pasul 1. Regulile gramaticii se comasează, combinând regulile cu acelas, i mem-

bru stâng.

S→ aS|aB

B→ bC

C→ aC|c

2

Pasul 2. Săgeata → se transformă în egalitate =

S = aS|aB

B = bC

C = aC|c

Pasul 3. Se stabiles,te o relat, ie de ordine între neterminale.S ≤ B ≤ C0 1 2

Pasul 4. Se verifică forma intermediară a fiecărei ecuat, ii.În forma intermediară indicele membrului stâng trebuie să fie mai micsau egal cu indicele neterminalelor din membrul drept.Dacă această condit, ie nu este satisfăcută neterminalul mai mare înmembrul drept se înlocuies,te conform regulilor.

În cazul exemplului dat sistemul este în formă intermediară.

Pasul 5. Rezolvăm sistemul de jos în sus.C = aC|c ⇒ solut, ia C = a∗c.Acesta se va înlocui în product, ia anterioară.B = ba∗cAcesta se va înlocui în product, ia anterioară.S = aS|aba∗c ⇒ S = a∗aba∗c

Exemplu (din expresia regulată obt, inem gramatica)

Fie expresia regulată (0|1)0∗11∗0. Spargem expresia în α∗β, adică (0|1)∣∣∣0∗1

∣∣∣1∗0.

Prima parte 0|1 va fi o regulă de forma S → 0|1. Dar ca să continuăm curestul expresiei regula devine S → 0A|1AA doua parte 0∗1 va fi o regulă de forma A → 0A|1. Dar ca să continuăm cuceea ce a mai rămas din expresie regula devine A → 0A|1B.A treia parte va fi B → 1B|0.Deci gramatica echivalentă cu expresia regulată dată este:

G = ({S,A,B}, {0, 1}, S, P ). P:

S → 0A|1A

A → 0A|1B

B → 1B|0

3

Probleme propuse

Se dă gramatica regulată să se transforme în expresie regulată:

1.

S→ aA

S→ a

A→ aA

A→ bB

A→ a

B→ bB

B→ c

2.

S→ aA

A→ aA

A→ aB

B→ bC

C→ cB

C→ c

3.

S→ 0A

S→ 1S

A→ 0B

A→ 1S

B→ 0B

B→ 1B

B→ 0

4.

S → 0A|1S|1

A → 0B|1A

B → 0S|1B

5. Se dă sistemul de ecuat, ii cu expresii regulate:

{X = a1X + a2Y + a3

Y = b1X + b2Y + b3

Să se găsească expresiile regulate pentru X s, i Y.

4

Să se găsească gramaticile echivalente cu expresiile regulate:

6. (a|b)∗a(a|b)

7. (a|b)∗a(a|b)(a|b)∗

8. 00(00|1)∗101(11|(1|0)∗)∗001∗

9. Să se scrie un program care transformă AFN în AFD, comasând stă-rile s, î eliminând λ-tranzit, iile. (Prima linie cont, ine stările automatuluiseparate prin spat, iu, a doua linie cont, ine alfabetul, a treia linie stareainit, ială, a patra linie stările finale separate prin spat, iu, următoarelelinii câte o tranzit, ie: stare literă stare)

10. Să se scrie un program care transformă un AFD complet în AFD minim.

5


Expresii regulate s, i AF

Teoremă 1 Fiind dat o expresie regulată R există un cu AFN λ- tranzit,iicare acceptă limbajul generat de expresia regulată.

Transformarea unei expresii regulate în AFN

Expresia regulată trebuie să fie descompusă în expresii regulate elementare.

1. a (un singur simbol)

2. λ (expresia regulată vidă)

3. s|t s sau t

4. st s concatenat cu t

5. s∗ s de 0 sau de mai multe ori

Automatele finite corespunzătoare acestor expresii regulate elementare sunt:

1. a

1

2. λ

3. s|t

4. st

5. s∗

2

Exemplu

Fie expresia regulată (ab)∗bb(a|b)∗. Descompunem expresia în (ab)∗, b, b, (a|b)∗.

I. ab∗

II. (a|b)∗

Totul devine:

3


Gramatici independente de context

Gramatici de forma A → α unde A ∈ VN s, i α ∈ (VT ∪ VN )∗.

Forma normală Chomsky

Gramaticile care au doar următoarele tipuri de reguli

A → BC

A → a

S → λ

unde

A ∈ VN , B, C ∈ VN \ {S} s, i a ∈ VT sunt în FNC.

Transformarea unei gramatici în FNC

1. eliminarea λ-tranzit, iilor

2. eliminarea product, iilor unu la unu (A → B, înlocuim product, iile lui Bîn partea dreaptă )

3. eliminarea terminalelor în partea dreaptă înlocuindu-i cu noi netermi-nale (A′ → a)

4. gruparea neterminalelor în perechi de câte două

1

Probleme propuse

Să se transforme următoarele gramatici în FNC.

1.

S → AA

A → B|BB

B → abB|b|bb

2.

S → AaA|bA|B

A → AaA|AbA|λ

B → ab

3.

S → SS|A|B

A → SS|AS|a

B → λ

4.

S → AaA|BB|AB

A → b|λ

B → aA

5.

{S → aA|bS|ab|A

A → aA|a|λ

6.

S → aA|B|bab

A → B|λ

B → bb|bAb

7.

S → aB|Bbb|B

A → a|λ

B → aAB|bb|AAa

3


Automate Push Down (APD)

Automatele Push Down sunt o extensie a AFN cu λ tranzit, ii, dar mai au ladispozit, ie o stivă. Informat, iile din stivă pot fi accesate LIFO.

Definit, ie 1 Un automat push-down este format din M = (Q, Σ, Γ, δ, q0, F, Z).

− Q mult,ime finită de stări

− Σ simboluri de intrare

− Γ simboluri ale stivei

− q0 starea init,ială

− F stările finale

− Z simbol de start al stivei

− δ funct,ie de tranzit,ie δ : Q × (Σ ∪ λ) × Γ → P(Q × Γ∗)

δ(q0, a, AZ) = {(q1, B)}. Dacă suntem în starea q0, de pe banda de intrarecitim simbolul a iar capul stivei este A atunci trecem în starea q1 scoatemdin stivă A s, i punem în locul lui simbolul B.

Observat, ie 2 Init,ial stiva este vidă, adică cont,ine doar simbolul Z.

Definit, ie 3 Configurat,ie instantanee: Numim configurat,ie instantanee tri-pletul (q, x, z), adică starea actuală a automatului; s, irul de caractere din cu-vântul rămas încă necitit (neanalizat) s, i cont,inutul stivei (în pozit,ie orizon-tală).Configurat,a init,ială este (q0,cuvânt,Z).

1

Definit, ie 4 Limbaj acceptat prin stări finale: După prelucrarea cuvântuluiautomatul va fi într-una din stările finale. (Cont,inutul stivei nu este impor-tantă).

Definit, ie 5 Limbaj acceptat prin stivă vidă: După prelucrarea cuvântuluistiva este vidă, adică cont,ine doar Z (Starea în care râmâne automatul neeste importantă).

Exemplu

Să se creeze APD care acceptă limbajul: L = {ww̃|w̃ este simetricul lui w}.Orice cuvânt palindrom peste alfabetul Σ = {0, 1}.M = (Q = {q0, q1}, Σ = {0, 1}, Γ = {0, 1}, δ, q0, q3 ∈ F,Z)

δ(q0, 0, Z) = {(q0, 0Z)}

δ(q0, 1, Z) = {(q0, 1Z)}

δ(q0, 0, 1) = {(q0, 01)}

δ(q0, 0, 0) = {(q0, 00), (q1, λ)}

δ(q0, 1, 0) = {(q0, 10)}

δ(q0, 1, 1) = {(q0, 11), (q1, λ)}

δ(q1, 0, 0) = {(q1, λ)}

δ(q1, 1, 1) = {(q1, λ)}

δ(q1, λ, Z) = {(q1, λ)}

Fie cuvântul 001100. Să se verifice dacă cuvântul este acceptat de APDdefinit mai sus.(q0, 001100, Z) ` (q0, 01100, 0Z) ` (q0, 1100, 00Z) ` (q0, 100, 100Z) `(q1, 00, 00Z) ` (q1, 0, 0Z) ` (q1, λ, Z)

Observat, ie 6 APD se numes,te nedeterminist, dacă are mai multe obt,iunipentru a trece într-o nouă stare citind aceeas, i pereche(simbol de intrare,capulsitvei).

Probleme propuse

Să se determina APD care recunoas,te următoarele gramatici:

1. L = {anbn, n ≥ 0}

2

2. L = {|w|a > |w|b sau |w|b > |w|a}

3. L = {anbm, 1 ≤ m ≤ n ≤ 2m}

4. L = {aibjai, i, j > 0}

3


Automate Push Down (APD) s, i Gramatici inde-pendente de context (IDC)

Limbajele acceptate de automatele cu stivă ⇔ gramatici independente decontext, adică PDA⇔ IDC.

Transformarea unei gramatici IDC în PDA

Fie G = (VT , VN , S, P ) se caută PDA echivalent M = (Q, Σ, Γ, δ, q0, F, Z).

Gramatică APD

o singura stare qVT terminale δ(q, a, a) = (q, λ)

A → α δ(q, λ, A) = (q, α)

Exemplu

Să se transforme gramatica în APD

E → E + T |T

T → T ∗ F |F

F → (E)|aδ(q, a, a) = {(q, λ)}δ(q, +, +) = {(q, λ)}δ(q, ∗, ∗) = {(q, λ)}δ(q, (, () = {(q, λ)}δ(q, ), )) = {(q, λ)}δ(q, λ, E) = {(q, E + T )|(q, T )}

1

δ(q, λ, T ) = {(q, T ∗ F )|(q, F )}δ(q, λ, F ) = {(q, (E))|(q, a)}

Normalizarea unui PDA

1. Are o singură stare de acceptare

− Se introduce starea qfinal din fiecare stare finală originală se treceprin λ-tranzit, ii în această stare

2. Goles,te stiva înainte de acceptare

− Se introduce un nou simbol $ care se pune init, ial în stivă. Seînlocuies,te qfinal cu qtemporal. Dacă am ajuns în starea qtemporal

golim stiva (aplicând acele reguli), doar dacă singurul simbol ră-mas în stivă este $ atunci se introduce regula δ(qtemporal, λ, $) ={(qfinal, λ}

3. Fiecare regulă ori pune simbol în stivă ori scoate simbol din stivă,adică există doar reguli de forma δ(q, a, λ) = {(q, α)} sau δ(q, a, A) ={(q, λ)}.Din reguli de forma δ(q1, a, α) = {(q2, β)} vom crea δ(q1, a, α) = {(q′, λ)}s, i δ(q1, λ, λ) = {(q′, β)}

Transformarea unui PDA normalizat în gramatică IDC

Fie M = (Q, Σ, Γ, δ, q0, F, Z) se caută gramatica IDC echivalentăG = (VT , VN , S, P ).

APD Gramatică

S ′ → Ss

δ(q, a, α) = (q, λ) Sα → aδ(q, λ, α) = (q, λ) Sα → λδ(q, λ, A) = (q, α) SA → SiSjSk

unde SiSjSk corespund s, irului α

2

Exemplu

Să se transforme APD în gramtatică IDCδ(q, a, a) = {(q, λ)}δ(q, b, b) = {(q, λ)}δ(q, λ, S) = {(q, λ)}δ(q, λ, S) = {(q, ba)}δ(q, λ, S) = {(q, bAa)}δ(q, λ, A) = {(q, ba)}δ(q, λ, A) = {(q, bAa)}

Obt, inem gramatica:S→ Ss

Sa → aSb → bSs → λ|SbSa|SaSASb

SA → SbSa|SbSASa

Probleme propuse

1. Să se transforma gramatica data în APD.

S → AB

A → aAB|λ

B → cB|λ

3

lfa

Documents