LFA - Explicatii Exercitii, Algoritmi [SE 1-4]

Seminar LFA gr.141-144, 211

@ MN 2014-2015

- 1 -

Cuprins

~ Seminar 1 ~ .................................................................................................................. - 4 -

Automat Finit Determinist .......................................................................................... - 4 -

Automat Finit Nedeterminist ...................................................................................... - 4 -

EXEMPLE: ................................................................................................................. - 5 -

L1 = a* = {a

n, n 0} ............................................................................................... - 5 - L2 = a

+ = {a

n, n 1} ............................................................................................... - 5 - L3 = {a

2n, n 0} ..................................................................................................... - 5 - L4 = {a

2n+1, n 0}................................................................................................... - 5 - L5 = {a

2n, n 1} ..................................................................................................... - 5 - L6 = {a

2n+1, n 1}................................................................................................... - 6 - L7 = {a

2n b

3m, n 0, m 0} .................................................................................... - 6 - L8 = {a

2n b

3m, n 1, m 0} .................................................................................... - 7 - L9 = {a

2n b

3m, n 0, m 1} .................................................................................... - 7 - L10 = {a

2n b

3m, n 1, m 1} .................................................................................. - 7 - Operaii cu limbaje ...................................................................................................... - 8 -

Reuniune 21 LLL ............................................................................................ - 8 - Concatenare 21 LLL .......................................................................................... - 8 -

Stelare 0

1

*

1

n

nLLL ........................................................................................... - 8 -

Ridicare la putere nenul 1

11

n

nLLL ............................................................. - 8 -

Compunerea automatelor finite ............................................................................... - 9 - Reuniune ................................................................................................................. - 9 -

Concatenare............................................................................................................. - 9 -

Stelare ..................................................................................................................... - 9 -

Transformarea AFNAFD ........................................................................................ - 9 - EXEMPLU:........................................................................................................... - 10 -

Verificare acceptare cuvnt de ctre automat finit ................................................... - 12 -

~ Seminar 2 ~ ................................................................................................................ - 14 -

Automat Finit Nedeterminist cu tranziii .............................................................. - 14 - nchiderea unei stri .......................................................................................... - 14 - Verificare acceptare cuvnt de ctre automat AFN .......................................... - 14 - EXEMPLU:........................................................................................................... - 15 -

Transformarea AFN AFD ................................................................................ - 18 - EXEMPLU:........................................................................................................... - 19 -

Automatul minimal ................................................................................................... - 22 -

EXEMPLU:........................................................................................................... - 23 -

Condiii asupra numrului de apariii ale unui caracter ntr-un cuvnt .................... - 25 - EXEMPLE: ........................................................................................................... - 25 -

}||,||..}1,0{{ 101 imparwparwawL

........................................................ - 25 -

}0,0,23||,12||..},{{2 mnmwnwabawL ba ............................... - 26 -


@ MN 2014-2015

- 2 -

}..},{{3 wnaparnubbbiaaaabawL ....................................................... - 26 -

~ Seminar 3 ~ ................................................................................................................ - 27 -

Expresii regulate ....................................................................................................... - 27 -

Precedena operaiilor ,, ................................................................................ - 27 -

Transformarea expresie_regulat automat_finit .................................................. - 27 - Transformarea automat_finit expresie_regulat .................................................. - 28 -

Cteva formule utile .............................................................................................. - 29 -

EXEMPLU:........................................................................................................... - 29 -

Gramatici................................................................................................................... - 31 -

Gramatici independente de context (GIC) / Context-free grammars (CFG) ............ - 31 -

Gramatici liniare ................................................................................................... - 31 -

Gramatici liniare la dreapta ................................................................................... - 31 -

Gramatici liniare la stnga .................................................................................... - 31 -

Gramatici regulate ................................................................................................. - 31 -

EXEMPLE (gramatici regulate): .............................................................................. - 32 -

L1 = a* = {a

n, n 0} ............................................................................................. - 32 - L2 = a

+ = {a

n, n 1} ............................................................................................. - 32 - L3 = {a

2n, n 0} ................................................................................................... - 32 - L4 = {a

2n+1, n 0}................................................................................................. - 32 - L5 = {a

2n, n 1} ................................................................................................... - 32 - L6 = {a

2n+1, n 1}................................................................................................. - 32 - L7 = {a

2n b

3m, n 0, m 0} .................................................................................. - 32 - Analogia ntre automate finite i gramatici regulate ............................................. - 33 -

~ Seminar 4 ~ ................................................................................................................ - 34 -

EXEMPLE (gramatici independente de context): .................................................... - 34 -

L1 = {anb

n, n 0} ................................................................................................. - 34 - L2 = {a

nb

n, n 1} ................................................................................................. - 34 - L3 = {a

nb

2n, n 1} ................................................................................................ - 35 - L4 = {a

2nb

kc

3n, n 0, k 1} ................................................................................. - 35 - L5 = {a

2nb

kc

3n, n 1, k 1} ................................................................................. - 35 - L6 = {a

2nc

3nb

k, n 1, k 1} ................................................................................. - 36 - Verificare generare cuvnt de ctre gramatic ...................................................... - 36 - L7 = {a

n b

k c

2k d

n, n 1, k 0} ............................................................................. - 38 - L8 = {a

n b

k c

2k d

n, n 0, k 1} ............................................................................. - 38 - L9 = {a

n b

2n c

2k d

k, n 0, k 1} ............................................................................ - 39 - L10 = {a

n b

2n c

k d

m e

3k, n,k,m 0} ......................................................................... - 39 - Transformarea GIC gramatic n F.N. Chomsky ................................................. - 40 - Automatul Push-Down (APD) / Automatul Stiv .................................................... - 43 -

Modaliti de acceptare a unui cuvnt de ctre un APD ....................................... - 44 - EXEMPLE (automate push-down): .......................................................................... - 45 -

L1 = {anb

n, n 1} ................................................................................................. - 45 - L2 = {a

nb

2n, n 0} ................................................................................................ - 46 - L3 = {a

2n b

k c

3k d

n, n 1, k 1} ............................................................................ - 47 - Verificare acceptare cuvnt de ctre un APD ....................................................... - 48 -


@ MN 2014-2015

- 3 -

L4 = {a2n

b3n

c2k

dk, n 1, k 1} ........................................................................... - 48 -


@ MN 2014-2015

- 4 -

~ Seminar 1 ~ (AFD; AFN; Operaii cu limbaje; Compunere automate; Transformarea AFNAFD)

Automat Finit Determinist

AFD = (Q, , q0, , F) Q mulimea de stri alfabetul de intrare q0Q starea iniial

FQ mulimea de stri finale

QQ : funcia de tranziie (delta)

Pentru a verifica dac un cuvnt este sau nu acceptat de un automat AFD: - se pornete din starea iniial q0 - ct timp este posibil:

- avnd starea curent i caracterul curent din cuvnt, aplicm funcia pentru a determina noua stare - repetm pentru noua stare i caracterul urmtor din cuvnt

- algoritmul se termin n 3 cazuri: - chiar dac nu s-a citit complet tot cuvntul,

dar automatul s-a blocat pentru c funcia de tranziie nu era definit pentru starea curent i caracterul curent cuvnt neacceptat - dac ntreg cuvntul a fost citit, dar automatul a ajuns ntr-o stare care nu este final (adic din mulimea Q\F) cuvnt neacceptat - dac ntreg cuvntul a fost citit, iar automatul a ajuns ntr-o stare care este final (adic din mulimea F) cuvnt acceptat

Automat Finit Nedeterminist

AFN = (Q, , q0, , F) Q mulimea de stri alfabetul de intrare q0Q starea iniial

FQ mulimea de stri finale QQ 2: funcia de tranziie (delta)

Diferena dintre AFD i AFN const n modul n care este definit funcia de tranziie. La AFD: pentru orice pereche de o stare i un caracter, avem cel mult o stare de continuare (putem s nu avem niciuna, adic funcia s fie nedefinit pentru acele valori). La AFN: pentru orice pereche de o stare i un caracter, avem ca posibilitate de continuare o submulime a mulimii de stri Q (putem s nu avem niciuna dac funcia este nedefinit; putem s avem o singur stare de continuare; sau putem s avem mai multe stri de continuare, aici apare nedeterminismul).


@ MN 2014-2015

- 5 -

Pentru a verifica dac un cuvnt este sau nu acceptat de un automat AFN: Se procedeaz analog ca n cazul AFD-ului, excepia fiind c la fiecare aplicare a funciei delta trebuie s reinem toate posibilitile de stri de continuare, iar la pasul urmtor s reaplicm delta pentru toate acestea mpreun cu caracterul curent.

EXEMPLE:

L1 = a* = {a

n, n 0} = {=a0, a=a1, aa=a2, aaa=a3, aaaa=a4, }

Ambele soluii sunt AFD-uri. Obs: De fiecare dat cnd (cuvntul vid) trebuie s fie recunoscut de un AFD sau de un AFN (simplu, adic AFN fr -tranziii), trebuie ca starea iniial q0 s fie i stare final.

L2 = a+ = {a

n, n 1} = {a=a1, aa=a2, aaa=a3, aaaa=a4, }

Diferena fa de exemplul anterior? Aici nu trebuie acceptat, deci starea iniial q0 trebuie s nu fie stare final.

L3 = {a2n, n 0} = {=a0, aa=a2, aaaa=a4, aaaaaa=a6, }

L4 = {a2n+1, n 0} = {a=a1, aaa=a3, aaaaa=a5, }

Cele dou automate au aceleai stri i aceleai tranziii. Difer doar mulimea strilor finale. Dac setm q0 final, atunci vor fi acceptate cuvintele de lungime par (inclusiv zero), iar dac setm n schimb q1 final, atunci vor fi acceptate cuvintele de lungime impar.

Obs: De fiecare dat cnd la putere apare un coeficient, nseamn c vom avea un circuit de lungime egal cu acest coeficient (sau lungime proporional cu el, n cazul n care puterea era aplicat unui cuvnt, nu doar unei litere).

L5 = {a2n, n 1} = {aa=a2, aaaa=a4, aaaaaa=a6, }


@ MN 2014-2015

- 6 -

n primul rnd trebuie s ne asigurm c obligm automatul s citeasc cei doi de a (cel mai mic cuvnt din limbaj) i c nu accept ceva mai scurt de att. Pentru asta, adugm cele trei stri i tranziiile de la q0 spre q1 i de la q1 spre q2, iar apoi setm q2 s fie stare final. Apoi vedem c avem coeficientul 2 la putere, deci trebuie s avem un circuit de lungime 2. Avem dou variante: fie adugm tranziie de la q2 spre q1, fie adugm tranziie de la q1 spre q0. Ambele automate recunosc acelai limbaj (dar primul este AFD, iar al doilea este AFN pentru c din q1 cu a putem ajunge i n q0 i n q2).

L6 = {a2n+1, n 1} = {aaa=a3, aaaaa=a5, aaaaaaa=a7, }

La fel ca la exemplul anterior, ne vom asigura nti c automatul nu accept nimic mai scurt dect cel mai mic cuvnt din limbaj, adic aaa. Deci vom aduga cele 4 stri i tranziiile ctre dreapta i vom seta starea q3 final. Apoi pentru a avea circuitul de lungime 2 (egal cu coeficientul lui n), avem cele trei variante. Dac adugm tranziia de la q3 spre q2 vom obine un AFD, iar dac alegem una din celelalte dou variante vom obine un AFN.

L7 = {a2n

b3m, n 0, m 0}

= {, a2, a4, a6, a8, , b3, b6, b9, b12, , a2b3, a2b6, a4b3,a4b6, a6b3, a6b6, }

n primul rnd vedem c cel mai mic cuvnt ce trebuie acceptat este , deci setm starea iniial q0 s fie i stare final. Apoi facem circuit de lungime 2 cu litera a. Dup ce citim un numr par de a-uri (inclusiv zero), ajungem n starea q0, deci de aici trebuie s pornim cu citirea b-urilor. Adugm q2, q3 i cele dou tranziii cu b. tim c va trebui s avem un circuit de lungime 3 cu b-uri, dar trebuie s fim de asemenea ateni c literele de a i de b nu pot fi amestecate ntre ele, dup ce am citit primul b nu mai avem voie s citim niciun a. Deci nu putem avea muchie de ntoarcere de la q3 ctre q0 pentru c n q0 se pot citi a-uri. nseamn c avem nevoie de a nou stare, aa c adugm q4 i tranziii de la q3 spre q4 i de la q4 spre q2 pentru a nchide circuitul.


@ MN 2014-2015

- 7 -

L8 = {a2n

b3m

, n 1, m 0}

= {a2, a

4, a

6, a

8, , a2b3, a2b6, a4b3,a4b6, a6b3, a6b6, } n acest caz, cuvintele conin obligatoriu a-uri, b-urile putnd s apar sau nu.

Trebuie s obligm automatul s citeasc numr par de a-uri, dar cel puin dou, deci nu se mai poate ntoarce din q1 n q0 cu al doilea a, ci trebuie s continue spre q2 i setm q2 ca stare final. Apoi ncepnd din q2 citim doi de b, dar pentru al treilea nu putem nchide circuitul ntorcndu-ne n q2 dac am ales ca muchie de ntoarcere pentru a-uri de la starea q2 spre starea q1. Deci trebuie s adugm i starea q5 care va fi i ea final i cele dou tranziii de la q4 spre q5 i de la q5 spre q3.

Dar dac am fi ales ca muchie de ntoarcere pentru a-uri de la q1 spre q0? Atunci nu am mai fi avut nevoie de starea q5, pentru c puteam s nchidem circuitul b-urilor de la q4 spre q2 i am fi avut doar starea q2 final. Doar c n acest caz am fi obinut un AFN (din cauza lui q1).

L9 = {a2n

b3m, n 0, m 1}

= {b3, b

6, b

9, b

12, , a2b3, a2b6, a4b3,a4b6, a6b3, a6b6, } n acest caz, cuvintele conin obligatoriu b-uri, a-urile putnd s apar sau nu.

Observm c automatul este foarte asemntor cu cel pentru limbajul L7. Diferena este c acum starea q0 nu mai este stare final, ceea ce nseamn c putem sau nu s trecem prin circuitul de a-uri, dar sigur suntem obligai s citim b-uri nainte de a ajunge ntr-o stare final.

L10 = {a2n

b3m, n 1, m 1}

= {a2b

3, a

2b

6, a

4b

3,a

4b

6, a

6b

3, a

6b

6, } n acest caz, cuvintele conin obligatoriu i a-urile, i b-urile.


@ MN 2014-2015

- 8 -

Acest automat seamn cu cel pentru L8 (prima variant), unde eram obligai s avem a-uri. n plus, pentru c acum trebuie s avem i b-uri, starea q2 nu va mai fi stare final.

Operaii cu limbaje

Reuniune 21 LLL }|{ 21 LwsauLwwL

Exemplu:

L1 = {a, ab, abc}

L2 = {a, bd, cd}

L = {a, ab, abc, bd, cd}

Concatenare 21 LLL

}|{ 21 LwiLwwwL jiji

Exemplu:

L1 = {a, ab, abc}

L2 = {a, bd, cd}

L = {aa, abd, acd, aba, abbd, abcd, abca, abcbd, abccd}

Stelare 0

1

*

1

n

nLLL

}1|...{ 1211 nioricepentruLwwwwL inn

Exemplu:

L1 = {a, ab, abc}

(L1)* = { ; a, ab, abc ; aa, aab, aabc, aba, abab, ababc, abca, abcab, abcabc ; }

Obs: Cuvntul vid va aparine limbajului stelat, indiferent dac nainte aparinea sau nu limbajului iniial.

Ridicare la putere nenul 1

11

n

nLLL

La fel ca la stelare, doar c nu mai exist cuvntul vid. }{\* LL


@ MN 2014-2015

- 9 -

Obs: Atenie la ridicarea la putere a cuvintelor! (S nu distribuii puterea ca la nmulire, ci concatenai cuvntul cu el nsui de cte ori spune puterea.) (abc)

2 = abcabc ; (abc)

2 aabbcc = a2b2c2

Compunerea automatelor finite

Reuniune

Dac avem deja construite dou automate finite (avnd strile iniiale q01 i q02 i mulimile strilor finale F1 i F2) care accept respectiv limbajele L1 i L2 i dorim s

obinem un automat finit care s accepte limbajul 21 LLL : - introducem o nou stare q0 care va fi noua stare iniial - adugm dou -tranziii de la q0 spre q01 i de la q0 spre q02

- noua mulime de stri finale va fi 21 FFF

Concatenare

Dac avem deja construite dou automate finite (avnd strile iniiale q01 i q02 i mulimile strilor finale F1 i F2) care accept respectiv limbajele L1 i L2 i dorim s

obinem un automat finit care s accepte limbajul 21 LLL :

- noua stare iniial va fi q01, starea iniial a primului automat - adugm -tranziii de la fiecare stare final din F1 spre q02 - noua mulime de stri finale va fi F = F2

Stelare

Dac avem deja construit un automat finit (avnd starea iniial q01 i mulimea strilor finale F1) care accept limbajul L1 i dorim s obinem un automat finit care s accepte

limbajul *

1LL :

- introducem o nou stare q0 care va fi noua stare iniial - adugm o -tranziie de la q0 spre q01 - adugm -tranziii de la fiecare stare final din F1 spre q0

- noua mulime de stri finale va fi F = {q0} (sau putem lsa 10 FqF )

Transformarea AFNAFD Avnd dat un AFN (reprezentat sub form de graf), vom calcula funcia delta completnd un tabel astfel:

La capetele de linie vom pune numele strilor AFN-ului (elementele mulimii Q): q0, q1, ..., q|Q|-1

La capetele de coloan vom pune caracterele alfabetului AFN-ului (elementele mulimii )

Calculm coninutul primelor |Q| linii astfel: elementul aflat pe linia li i coloana cj reprezint mulimea de stri n care se poate ajunge n AFN dac pornim din starea de pe linia li (n cazul acesta: qi-1 dac numerotm liniile ncepnd cu 1) i citim caracterul de pe coloana cj. Pentru a afla aceast mulime, ne uitm la graful


@ MN 2014-2015

- 10 -

care reprezint AFN-ul, cutm starea de la linia li i pentru fiecare tranziie cu litera de la coloana cj care pornete din aceast stare, adugm starea destinaie a tranziiei la mulimea curent din tabel.

Apoi trebuie s calculm aceast funcie delta i pentru noile mulimi de stri obinute la paii anteriori (aceste calcule se fac cel mai simplu folosind doar liniile din tabel calculate la pasul anterior, nu i graful automatului AFN) (a) fie alegem s facem calculele pentru toate noile mulimi de stri, i abia apoi

s vedem care dintre ele vor aprea n AFD-ul obinut (tot fcnd parcurgerea n adncime descris mai jos).

(b) fie alegem s facem calculele doar pentru noile mulimi de stri care vor aprea n AFD: pentru a decide care vor fi acestea, facem un fel de parcurgere n adncime a grafului care va reprezenta AFD-ul. Adic pornim cu starea q0 care va fi starea iniial a AFD-ului, apoi parcurgem prima linie a tabelului (care conine calculele tranziiilor ce pleac din q0) i adugm la noul automat toate aceste tranziii mpreun cu strile-destinaie calculate n tabel. Apoi pentru toate aceste stri-destinaie, dac nu au deja n tabel un capt de linie care s le corespund, l vom aduga i vom calcula acea linie astfel: - fie noua stare-mulime {qk1, qk2, , qkp}. Pentru fiecare coloan cj,

calculm elementul din tabel fcnd reuniunea elementelor aflate pe aceeai coloan cj i pe liniile corespunztoare strilor qk1, qk2, , qkp.

Apoi revenim la desenarea grafului AFD-ului, i adugm tranziiile proaspt calculate mpreun cu strile-destinaie. Relum procedeul pn nu mai apar stri noi.

Strile finale ale noului AFD obinut, vor fi acele stri-mulime (pot avea i un singur element, nu neaprat mai multe) care conin cel puin una din strile care erau finale pentru AFN-ul iniial.

EXEMPLU:

Se d AFN-ul urmtor:

Calculm tabelul pentru funcia delta: nti primele 3 linii folosind graful AFN-ului, apoi urmtoarele linii folosind aceste prime 3 linii ale tabelului.

Vom avea dou coloane, pentru c alfabetul automatului iniial este = {a, b}.

a b q0 {q0, q1} q0 q1 {q1, q2} q1 q2 q2 q2


@ MN 2014-2015

- 11 -

Alegem varianta (b), adic s calculm doar acele stri care vor aprea n AFD.

(1) Pornim cu starea q0 i i adugm cele dou tranziii i strile-destinaie necesare, adic {q0, q1} = q01 (prin notaie).

(2) Observm c a aprut noua stare q01 pentru care nu avem o linie n tabel, aa c o adugm i o calculm pentru cele dou coloane.

0122102110

10

1001

},,{},{},{

)},({)},({

)},,({),(

qqqqqqqq

aqaq

aqqaq

011010

10

1001

},{}{}{

)},({)},({

)},,({),(

qqqqq

bqbq

bqqbq

a b q0 {q0, q1} = q01 q0 q1 {q1, q2} = q12 q1 q2 q2 q2 q01 {q0, q1, q2} = q012 {q0, q1} = q01

(3) Revenim la desenul AFD-ului i adugm tranziiile care lipsesc, adic cele care pleac din starea q01, mpreun cu strile-destinaie care lipsesc, adic q012.

(4) Pentru noua stare aprut, q012, i adugm linia n tabel i o calculm.

01221022110

210

210012

},,{}{},{},{

)},({)},({)},({

)},,,({),(

qqqqqqqqq

aqaqaq

aqqqaq

012210210

210

210012

},,{}{}{}{

)},({)},({)},({

)},,,({),(

qqqqqqq

bqbqbq

bqqqbq


@ MN 2014-2015

- 12 -

a b q0 {q0, q1} = q01 q0 q1 {q1, q2} = q12 q1 q2 q2 q2 q01 {q0, q1, q2} = q012 {q0, q1} = q01

q012 {q0, q1, q2} = q012 {q0, q1, q2} = q012

(5) Revenim la graf i adugm tranziiile care pleac din starea q012.

(6) Observm c nu ne-a mai aprut nicio stare nou, deci nu ne-a rmas dect s marcm strile finale i am obinul AFD-ul cerut. n AFN-ul iniial stare final era doar q2. Orice stare-mulime din AFD-ul nostru care l conine pe q2 va fi stare final. Exist una singur: q012.

Obs: Dac am fi ales varianta (a), atunci am fi calculat n tabel i linia corespunztoare strii q12, ns observm c nici ea, dar nici strile q1 i q2 nu apar n AFD.

Verificare acceptare cuvnt de ctre automat finit

Folosim configuraii (sau descrieri instantanee) ale automatului, adic perechi formate din starea curent i ct a mai rmas de citit din cuvntul de intrare, i aplicm funcia delta ct timp este posibil (ne oprim fie cnd nu mai exist tranziie definit, fie cnd se termin cuvntul). Dac la final ajungem n stare final, cuvntul va fi acceptat.

Pentru AFD:

(q0, bba) (q0, ba) (q0, a) (q01, ) Am terminat de citit cuvntul i am ajuns n starea q01, care nu este final, deci rezult c automatul nu accept acest cuvnt.

(q0, babbaba) (q0, abbaba) (q01, bbaba) (q01, baba) (q01, aba) (q012, ba) (q012, a) (q012, )


@ MN 2014-2015

- 13 -

Am terminat de citit cuvntul i am ajuns n starea q012, care este final, deci rezult c automatul accept acest cuvnt.

Pentru AFN:

(q0, bba) (q0, ba) (q0, a) {(q0, ), (q1, )}

Am terminat de citit cuvntul i am avut dou drumuri posibile, care ne-au adus n strile q0 i q1. Nici una din ele nu este stare final, deci cuvntul nu este acceptat.

(q0, babbaba) (q0, abbaba)

{(q0, bbaba), (q1, bbaba)}

{(q0, baba), (q1, baba)}

{(q0, aba), (q1, aba)}

{(q0, ba), (q1, ba), (q2, ba)}

{(q0, a), (q1, a), (q2, a)}

{(q0, ), (q1, ), (q2, )}

Am terminat de citit cuvntul i am avut apte drumuri posibile, care ne-au adus n strile q0, q1 i q2. Exist printre ele o stare care este final, q2, deci cuvntul este acceptat.


@ MN 2014-2015

- 14 -

~ Seminar 2 ~ (AFN; Transformarea AFN AFD; Automatul minimal; Condiii asupra numrului de apariii ale unui caracter ntr-un cuvnt)

Automat Finit Nedeterminist cu tranziii

AFN = (Q, , q0, , F) Q mulimea de stri alfabetul de intrare q0Q starea iniial

FQ mulimea de stri finale QQ 2}){(: funcia de tranziie (delta)

Diferena fa de AFN-ul simplu este c suntem ntr-o stare i putem citi fie un caracter din alfabetul , fie cuvntul vid . Deci se poate ntmpla s ajungem ntr-o stare nou fr s fi citit nicio liter nou din cuvntul de intrare, ci doar aplicnd tranziii.

nchiderea unei stri

Mulimea de stri n care se poate ajunge plecnd din starea q i aplicnd zero sau mai multe tranziii se numete nchiderea strii q i se noteaz cu .

Obs: Orice stare face parte din propria nchidere (pentru c qq ),( 0 ; practic putem

presupune c orice stare are o tranziie implicit ctre ea nsi).

0

)},(|{

k

kqrrq

...)},(|{)},(|{}{ 21 qqqqqqqq ijijii

Observm c mulimile se pot calcula inductiv dup puterea lui :

)},(),,(|{)},(|{ 112 iijiijijij qqqqqqqq .

Sau n general )},(),,(|{)},(|{11 srqsrqrr kk .

Verificare acceptare cuvnt de ctre automat AFN

Pentru a verifica dac un cuvnt este sau nu acceptat de un automat AFN: Se procedeaz analog ca n cazul AFN-ului, doar c nainte de a cuta toate strile posibile de continuare cu tranziii cu caracterul curent, trebuie s facem nchiderea mulimii curente de stri. Iar dup ce a fost citit tot cuvntul de intrare, trebuie s facem o ultim nchidere a strilor curente, pentru a obine mulimea final de stri n care poate ajunge automatul pentru cuvntul dat.


@ MN 2014-2015

- 15 -

Obs: nchiderea unei mulimi de stri este egal cu reuniunea nchiderilor acelor stri.

iniiinii qqqqqq ...}...,,,{ 2121

EXEMPLU:

Se d urmtorul AFN:

Calculm nchiderile tuturor strilor.

},,,,,{

)},({),(

},{},{}{)},({)},({),(

},{}{}{)},({)},({),(

},{),(

}{),(

6543200

6

4

0

26262654

3

0

545432

2

0

32

1

0

0

0

0

qqqqqqq

qq

nchiderendejaeraqdarqqqqqqqq

qqqqqqq

qqq

qq

},,,{

)},({),(

}{)},({),(

}{)},({),(

}{),(

}{),(

64211

6

4

1

64

3

1

42

2

1

2

1

1

1

0

1

qqqqq

qq

qqq

qqq

qq

qq

},,{

)},({),(

}{)},({),(

}{),(

}{),(

6422

6

3

2

64

2

2

4

1

2

2

0

2

qqqq

qq

qqq

qq

qq


@ MN 2014-2015

- 16 -

},,,,{

}{)},({),(

}{}{)},({)},({),(

},{)},({),(

}{),(

}{),(

654323

664

4

3

4462

3

3

625

2

3

5

1

3

3

0

3

qqqqqq

nchiderendejaeraqdarqqq

qqqqq

qqqq

qq

qq

},{

)},({),(

}{),(

}{),(

644

6

2

4

6

1

4

4

0

4

qqq

qq

qq

qq

},,,{

}{)},({),(

}{}{)},({)},({),(

},{),(

}{),(

65425

664

3

5

4462

2

5

62

1

5

5

0

5

qqqqq

nchiderendejaeraqdarqqq

qqqqq

qqq

qq

}{

),(

}{),(

66

1

6

6

0

6

qq

q

qq

Verificm dac un cuvnt este sau nu acceptat de automatul AFN dat. pas 0: Pornim de la perechea (q0, abbaa).

pas 1a: Facem nchiderea mulimii curente de stri pentru a obine noua mulime de stri. = {q0, q2, q3, q4, q5, q6}

pas 1b: n fiecare stare din mulimea curent ncercm s citim simbolul curent din cuvnt i obinem o nou mulime de stri.

),(

}{),(

}{),(

}{),(

}{),(

},{),(

6

65

64

63

32

100

aq

qaq

qaq

qaq

qaq

qqaq

Deci noua mulime de stri este {q0, q1, q3, q6}, iar cuvntul rmas este bbaa.


@ MN 2014-2015

- 17 -

pas 2a: Facem nchiderea mulimii curente de stri pentru a obine noua mulime de stri.

},,,,,,{

}{},,,,{},,,{},,,,,{

,,,

6543210

6654326421654320

63106310

qqqqqqq

qqqqqqqqqqqqqqqq

qqqqqqqq


}{),(

}{),(

}{),(

},{),(

),(

),(

}{),(

66

25

54

633

2

1

20

qbq

qbq

qbq

qqbq

bq

bq

qbq

Deci noua mulime de stri este {q2, q3, q5, q6}, iar cuvntul rmas este baa.


},,,,{

}6{},,,{},,,,{},,{

,,,

65432

6654265432642

65326532

qqqqq

qqqqqqqqqqqq

qqqqqqqq


}{),(

}{),(

}{),(

},{),(

),(

66

25

54

633

2

qbq

qbq

qbq

qqbq

bq

Deci noua mulime de stri este {q2, q3, q5, q6}, iar cuvntul rmas este aa.


},,,,{

}{},,,{},,,,{},,{

,,,

65432

6654265432642

65326532

qqqqq

qqqqqqqqqqqqq

qqqqqqqq



@ MN 2014-2015

- 18 -

),(

}{),(

}{),(

}{),(

}{),(

6

65

64

63

32

aq

qaq

qaq

qaq

qaq

Deci noua mulime de stri este {q3, q6}, iar cuvntul rmas este a.


},,,,{

}{},,,,{

,

65432

665432

6363

qqqqq

qqqqqq

qqqq


),(

}{),(

}{),(

}{),(

}{),(

6

65

64

63

32

aq

qaq

qaq

qaq

qaq

Deci noua mulime de stri este {q3, q6}, iar cuvntul a fost citit n ntregime.

pas 6: Facem ultima nchidere a mulimii curente de stri pentru a obine mulimea final de stri.

},,,,{

}{},,,,{

,

65432

665432

6363

qqqqq

qqqqqq

qqqq

pas 7: Verificm dac printre strile n care am ajuns este vreo una final.

},{},{},,,,{},,,,{ 62626543265432 qqqqqqqqqFqqqqq

Deci cuvntul abbaa este acceptat de automatul AFN dat.

Transformarea AFN AFD Avnd dat un AFN (reprezentat sub form de graf), vom calcula funcia delta completnd un tabel asemntor cu cel de la algoritmul de transformare AFN AFD. La acest algoritm, capetele de coloan vor fi caracterele din alfabet, dar concatenate

la stnga i la dreapta cu *.

Pentru a calcula primele |Q| linii ale tabelului - facem nchiderea strii de la captul de linie curent - apoi n toate strile obinute ncercm s citim caracterul de pe coloana curent i

obinem o nou mulime de stri - facem nchiderea acestei mulimi i ceea ce obinem scriem n tabel


@ MN 2014-2015

- 19 -

Pentru a calcula urmtoarele linii (corespunztoare noilor stri-mulime care apar), procedm la fel ca la cellalt algoritm, adic reunim ce gsim n tabel pe aceeai coloan i pe liniile potrivite strilor componente din starea-mulime.

Strile finale ale noului AFD obinut, vor fi acele stri-mulime (pot avea i un singur element, nu neaprat mai multe) care conin cel puin una din strile care erau finale pentru AFN-ul iniial. n plus, trebuie s verificm daca automatul iniial accepta

cuvntul vid (adic dac AFNFq0 ). Dac da, atunci starea iniial ()

va fi i stare final.

EXEMPLU:

Plecm de la acelai automat de mai sus.

nti trebuie calculate nchiderile tuturor strilor automatului iniial. (Am fcut asta mai sus, deci doar rescriu ce am obinut.)

}{

},,,{

},{

},,,,{

},,{

},,,{

},,,,,{

66

65425

644

654323

6422

64211

6543200

qq

qqqqq

qqq

qqqqqq

qqqq

qqqqq

qqqqqqq

Avem tabelul pentru primele 7 linii obinut dup cum urmeaz:

* a * * b * q0 {q0, q1, q2, q3, q4, q5, q6} {q2, q3, q4, q5, q6} q1 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q2 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q3 {q2, q3, q4, q5, q6} {q2, q3, q4, q5, q6} q4 {q6} {q2, q4, q5, q6} q5 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q6 {q6}


@ MN 2014-2015

- 20 -

},,,,,,{}{},,,,{},,,{},,,,,{

},,,{}{}{}{}{},{

)},({)},({)},({)},({)},({)},({

)},,,,,,({),(

65432106654326421654320

6310

6310666310

654320

6543200

qqqqqqqqqqqqqqqqqqqqqqq

qqqq

qqqqqqqqqq

aqaqaqaqaqaq

aqqqqqqaq

},,,,{}{},,,{},,,,{},,{

},,,{}{}{}{},{}{

)},({)},({)},({)},({)},({)},({

)},,,,,,({),(

654326654265432642

6532

6532625632

654320

6543200

qqqqqqqqqqqqqqqqqq

qqqq

qqqqqqqqqq

bqbqbqbqbqbq

bqqqqqqbq

},,,,{}{},,,,{

},{}{}{

)},({)},({)},({)},({

)},,,,({),(

65432665432

63

6363

6421

64211

qqqqqqqqqqq

qq

qqqq

aqaqaqaq

aqqqqaq

},,,{}{},,,{

},{}{}{

)},({)},({)},({)},({

)},,,,({),(

654266542

65

6565

6421

64211

qqqqqqqqq

qq

qqqq

bqbqbqbq

bqqqqbq

},,,,{}{},,,,{

},{}{}{

)},({)},({)},({

)},,,({),(

65432665432

63

6363

642

6422

qqqqqqqqqqq

qq

qqqq

aqaqaq

aqqqaq

},,,{}{},,,{

},{}{}{

)},({)},({)},({

)},,,({),(

654266542

65

6565

642

6422

qqqqqqqqq

qq

qqqq

bqbqbq

bqqqbq


@ MN 2014-2015

- 21 -

},,,,{}{},,,,{

},{}{}{}{}{

)},({)},({)},({)},({)},({

)},,,,,({),(

65432665432

63

636663

65432

654323

qqqqqqqqqqq

qq

qqqqqq

aqaqaqaqaq

aqqqqqaq

},,,,{}{},,,{},,,,{},,{

},,,{}{}{}{},{

)},({)},({)},({)},({)},({

)},,,,,({),(

654326654265432642

6532

653262563

65432

654323

qqqqqqqqqqqqqqqqqq

qqqq

qqqqqqqqq

bqbqbqbqbq

bqqqqqbq

}{}{}{

)},({)},({)},,({),(

6666

64644

qqqq

aqaqaqqaq

},,,{}{},,,{},{}{}{

)},({)},({)},,({),(

654266542656565

64644

qqqqqqqqqqqqqqq

bqbqbqqbq

},,,,{}{},,,,{

},{}{}{}{

)},({)},({)},({)},({

)},,,,({),(

65432665432

63

63663

6542

65425

qqqqqqqqqqq

qq

qqqqq

aqaqaqaq

aqqqqaq

},,,{}{},,,{},,{

},,{}{}{}{

)},({)},({)},({)},({

)},,,,({),(

654266542642

652

652625

6542

65425

qqqqqqqqqqqq

qqq

qqqqqq

bqbqbqbq

bqqqqbq

)},({)},({),( 666 aqaqaq

}{}{)},({)},({),( 666666 qqqbqbqbq


@ MN 2014-2015

- 22 -

Apoi calculm liniile urmtoare, corespunztoare noilor stri-mulime, pe msur ce ele apar n automat. ncepem cu starea iniial, = q023456.

* a * * b * q0 {q0, q1, q2, q3, q4, q5, q6} {q2, q3, q4, q5, q6} q1 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q2 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q3 {q2, q3, q4, q5, q6} {q2, q3, q4, q5, q6} q4 {q6} {q2, q4, q5, q6} q5 {q2, q3, q4, q5, q6} {q2, q4, q5, q6} q6 {q6}

q023456 q0123456 q23456

q0123456 q0123456 q23456

q23456 q23456 q23456

Vom obine n final automatul AFD urmtor.

Automatul iniial avea strile finale FAFN = {q2, q6}, deci n noul automat vom avea strile finale FAFD = { q023456, q0123456, q23456}.

Obs: Limbajul acceptat de acest automat este L = {a,b}*, adic orice cuvinte formate cu

literele a i b n orice ordine, cuvinte de orice lungime, inclusiv zero.

Obs: Cred c la seminar am uitat s punem i tranziia de la q5 la q2 cu b, aa c pot exista mici diferene la calculele intermediare, dar rezultatul final este acelai.

Automatul minimal

Se pornete de la un AFD complet definit (adic pentru orice stare din mulimea Q i pentru orice caracter din alfabetul , funcia este definit).

Ideea algoritmului este de a gsi acele stri care au comportament echivalent, pentru a le grupa i a obine o unic stare nou n locul acestora.

- Dou stri sunt echivalente dac pentru orice cuvnt am alege, plecnd din cele dou stri, fie ajungem n dou stri finale, fie ajungem n dou stri nefinale.

],,,[,, * FwqFwpwqpQqp - Dou stri sunt separabile dac exist un cuvnt pentru care plecnd din cele

dou stri ajungem ntr-o stare final i ntr-una nefinal.

],,,[,, * FwqFwpwqpQqp w


@ MN 2014-2015

- 23 -

Vom construi un tabel, pe linii i pe coloane avnd strile automatului iniial. Vom completa tabelul pentru fiecare pereche de stri (qi, qj), avnd i > j, cu un cuvnt prin care cele dou stri sunt separabile. Dac nu vom gsi un astfel de cuvnt atunci acele stri sunt echivalente.

Vom completa tabelul cutnd cuvintele recursiv, n ordinea cresctoare a lungimii lor. Cuvintele de lungime k le vom obine cu ajutorul celor de lungime k1 calculate anterior. Obs: Dou stri sunt separabile prin cuvntul vid (de lungime zero), dac una din ele este final i cealalt este nefinal n automatul iniial.

EXEMPLU:

Fie automatul AFD complet definit:

Pas 0: Cutm perechile de stri separabile prin cuvntul de lungime zero. Avem o singur stare final n acest exemplu, deci ea va fi separabil prin de toate celelalte stri, care sunt nefinale. Completm n tabel, pentru toate perechile (q6, qi), 0 i 5.

q0 q1 q2 q3 q4 q5 q6

q0

q1

q2

q3

q4

q5

q6

Pas 1: Cutm cuvinte de lungime 1.

Avem FqaqFqaqFqaq

FqaqFqaqFqaq

656463

323110

),(;),(;),(

;),(;),(;),(

Rezult c orice stare din mulimea {q0, q1, q2} va fi separabil de orice stare din mulimea {q3, q4, q5} prin cuvntul a. (Observm c toate tranziiile cu b merg ctre stri nefinale, deci nu va exista nicio pereche de stri care s fie separabile prin cuvntul b.)


@ MN 2014-2015

- 24 -

Obs: E posibil s fie separabile i prin altceva, dar este suficient s gsim un singur cuvnt.

q0 q1 q2 q3 q4 q5 q6

q0

q1

q2

q3 a a a

q4 a a a

q5 a a a

q6

Pas 2: Cutm cuvinte de lungime 2. - Perechea (q1, q0) cu caracterul a ajunge n perechea (q3, q1). Dar q3 i q1 erau

separabile prin a. Rezult c strile q1 i q0 vor fi separabile prin cuvntul aa (obinut prin concatenarea caracterului ncercat i a fostului cuvnt calculat n tabel).

- Perechea (q2, q0) cu caracterul a ajunge n perechea (q3, q1). Dar q3 i q1 erau separabile prin a. Rezult c strile q1 i q0 vor fi separabile prin cuvntul aa.

- Perechea (q2, q1) cu caracterul a ajunge n perechea (q3, q3), iar cu caracterul b ajunge n perechea (q2, q2). Observm c dac dup citirea primului caracter (indiferent dac este a sau b), ambele drumuri pornesc din acelai loc, nu au cum s se mai ramifice n continuare. Rezult c aceste dou stri, q2 i q1, sunt echivalente.

- Perechea (q4, q3) cu caracterul a ajunge n perechea (q6, q6), iar cu caracterul b ajunge n perechea (q5, q5). Cu aceeai observaie ca mai devreme, rezult c strile q4 i q3 sunt echivalente.

- Perechea (q5, q3) cu caracterul a ajunge n perechea (q6, q6), dar cu caracterul b ajunge n perechea (q2, q5). Perechea (q2, q5) era separabil prin a. Rezult, prin concatenare, c strile q5 i q3 sunt separabile prin ba.

- Perechea (q5, q4) cu caracterul a ajunge n perechea (q6, q6), dar cu caracterul b ajunge n perechea (q2, q5). Perechea (q2, q5) era separabil prin a. Rezult, prin concatenare, c strile q5 i q4 sunt separabile prin ba.

q0 q1 q2 q3 q4 q5 q6

q0

q1 aa

q2 aa

q3 a a a

q4 a a a

q5 a a a ba ba

q6

Am terminat de completat tabelul i am obinut stri echivalente: 4321 qqiqq .


@ MN 2014-2015

- 25 -

Automatul AFD minimal obinut va avea Q = {q0, q12, q34, q5, q6} i F = {q6}. Tranziiile le desenm conform automatului iniial, dar innd cont de aceast grupare a strilor.

Condiii asupra numrului de apariii ale unui caracter ntr-un cuvnt

Notm cu |w|a numrul de apariii ale caracterului a n cuvntul w.

Obs: n general, cnd avem limbaje definite cu astfel de condiii asupra numrului de apariii ale unui caracter, sugestia pentru a putea construi mai uor automatul este s folosim nite indici la stri pentru o codificare ct mai intuitiv a cuvintelor din limbaj.

Atenie! Nu confundai exemplele urmtoare cu cele din primul seminar, n sensul de a ncerca s descriei limbajele acestea cu expresii asemntoare cu acelea cu puteri. Acolo existau n plus restricii asupra poziiei literelor n cuvnt (de exemplu toate a-urile la nceput i apoi toate b-urile). Aici nu conteaz ordinea literelor, ci doar numrul lor.

EXEMPLE:

}||,||..}1,0{{ 101 imparwparwawL

Ideea de rezolvare este ca fiecare stare s aib doi indici, egali cu restul mpririi la 2 a numrului de apariii ale caracterului 0, respectiv ale caracterului 1.

Starea final va fi q01 pentru c ea codific numrul par de 0-uri i impar de 1-uri.

Obs: Pentru c nu exist nicio alt restricie asupra formei cuvntului, automatul va fi complet definit, adic n orice stare am fi trebuie s avem tranziii cu toate caracterele din alfabet.


@ MN 2014-2015

- 26 -

}0,0,23||,12||..},{{2 mnmwnwabawL ba

Obs:

- Fiecare stare va avea doi indici pentru c alfabetul are dou elemente i ambele au condiii ataate.

- Primul indice, corespunztor caracterului a, va lua valori n mulimea resturilor mpririi la 2, deoarece coeficientul necunoscutei n este 2. Al doilea indice, corespunztor caracterului b, va lua valori n mulimea resturilor mpririi la 3, deoarece coeficientul necunoscutei m este 3.

- Numrul de stri va fi egal cu produsul numerelor ce reprezint cardinalele mulimilor n care iau valori indicii, n cazul acesta 23=6.

Starea final va fi q12, deoarece termenii liberi sunt + 1 i + 2.

}..},{{3 wnaparnubbbiaaaabawL

Obs: Acest limbaj ar mai putea fi scris i },,{}),{},({},,{3 aaabbbaaabbbL

.

Suntei de acord c e adevrat? tii s explicai cum am ajuns la acea expresie ?


@ MN 2014-2015

- 27 -

~ Seminar 3 ~ (Expresii regulate; Transformarea expresie_regulat automat_finit Transformarea automat_finit expresie_regulat ; Gramatici ; Gramatici regulate)

Expresii regulate

Se numete familia expresiilor regulate peste i se noteaz REX() mulimea de

cuvinte peste alfabetul },,,,),{(, definit recursiv astfel:

i) apentruREXaREX ;,

ii) REXeeREXee )(, 2121

iii) REXeeREXee )(, 2121

iv) REXeREXe *)(

Precedena operaiilor ,,

Obs: Atenie la ordinea n care se evalueaz operaiile: nti stelarea, apoi concatenarea i apoi reuniunea. (Dac vrei s fii siguri c nu le ncurcai, putei s facei o analogie cu operaiile aritmetice, unde se evalueaz nti ridicarea la putere, apoi nmulirea i apoi adunarea.)

Transformarea expresie_regulat automat_finit

Expresie

regulat Limbaj Automat finit

,},{ 0 FqQ

}{ },{},{ 00 qFqQ

a aa},{ 10110 ),(},{},,{ qaqqFqqQ

21 ee )()(

)(

21

21

eLeL

eeL

}},{),({

;;};{

0201021

2121021

qqq

VVVFFFqQQQ

21 ee )()(

)(

21

21

eLeL

eeL

},),({

;;;,

1102121

21201021

Fqpentruqq

VVVFFqqQQQ

ff

)( 1e ))(()( 11 eLeL },),({}),({

;};{};{

11010101

1001

Fqpentruqqqq

VVqFqQQ

ff

Descrierea n cuvinte a ultimelor trei linii ale tabelului o gsii n acest document la pagina 9 (compunerea automatelor finite).


@ MN 2014-2015

- 28 -

Obs: La construirea automatelor compuse se ine cont de precedena operaiilor (nti stelarea, apoi concatenarea, apoi reuniunea) i de parantezele din expresie.

Transformarea automat_finit expresie_regulat

Se numete EFA (automat finit extins), ),,,,( 0 FqetQM , unde, la fel ca la celelalte

automate finite, Q este mulimea strilor, este alfabetul, q0 este starea iniial, F este

mulimea strilor finale. Aici avem funcia de etichetare )(: REXQQet .

Notm ),( qpet prin pqe .

Ideea algoritmului este de a transforma automatul finit ntr-un automat finit extins, i apoi a elimina una cte una strile pn ajungem la o expresie regulat echivalent cu automatul iniial.

(a) Dac exist tranziii care ajung n starea iniial, atunci se adaug la automat o nou stare care va fi iniial i va avea o tranziie ctre fosta stare iniial.

(b) Dac exist mai multe stri finale, atunci se adaug la automat o nou stare care va fi singura final i va avea tranziii din toate fostele stri finale ctre ea.

(c) Se elimin pe rnd, una cte una, toate strile n afar de cea iniial i cea final. Presupunem c vrem s eliminm starea qk i c exist etichetele

),(),,( jkki qqetqqet i eventual bucla ),( kk qqet . Atunci obinem noua etichet

ntre strile qi i qj reunind (fosta etichet direct de la qi la qj) cu (eticheta de la qi la qk concatenat cu stelarea etichetei buclei de la qk la qk concatenat cu eticheta de la qk la qj).

(d) Atunci cnd rmn doar dou stri, se elimin bucla strii finale, dac exist. Concatennd (expresia obinut ntre starea iniial i cea final) cu (stelarea expresiei de pe bucla strii finale) obinem rspunsul final.

n practic, vom calcula etichetele folosind un tabel cu numrul de coloane complete egal cu numrul de stri ale automatului, i cu numrul de linii egal cu ptratul numrului de stri ale automatului. Obs: Atenie, strile automatului vor fi numerotate ncepnd de la q1 (care va fi starea iniial).

Notm cu kjiR expresia regulat ce se obine plecnd din starea qi, ajungnd n starea qj i

avnd ca stri intermediare primele k stri (adic q1, q2, ..., qk).

Tabelul va conine la capete de linii toate perechile posibile (qi, qj) cu i i j ntre 1 i |Q|, iar la capete de coloan toi k, cu k de la 0 la |Q| 1. Tabelul va fi calculat coloan cu coloan, pentru c valorile coloanei curente se calculeaz n funcie de valori aflate pe coloana precedent. Prima coloan se calculeaz astfel:

jidacqaqVa

jidacqaqVaR

ji

ji

ji },),(|{}{

},),(|{0


@ MN 2014-2015

- 29 -

Urmtoarele coloane se calculeaz astfel: (coloana curent k+1 n funcie de coloana precedent k)

)()( 11111 k

jk

k

kk

k

ki

k

ji

k

ji RRRRR

Rspunsul final, expresia regulat cutat, va fi obinut calculnd Ff

Q

fR

||

1 , adic

reuniunea etichetelor de la starea iniial la toate strile finale, avnd ca stri intermediare toate strile automatului.

Cteva formule utile

(A) ee ; ( este pentru concatenare cum este 0 pentru nmulire)

(B) eeee ; ( este pentru concatenare cum este 1 pentru nmulire)

(C) eeeeee ;

(D) )()(},{ 212121 eeeeee (formul valabil pentru oricte expresii, nu doar 2)

(E) )()()(;)()()( 32313213121321 eeeeeeeeeeeeee

EXEMPLU:

Se d automatul finit urmtor i se dorete obinerea expresiei regulate care i corespunde, folosind tabelul descris anterior.

Avem dou stri, deci tabelul va avea 22 = 4 linii i 2 coloane complete (plus eventual una incomplet pentru rspunsul final).

1k

jiR k+1 = 0 k+1 = 1 k+1 = 2

rij = r11 1 +

rij = r12 0

rij = r21

rij = r22

(a) Calculm prima coloan, pentru k+1 = 0. - Dac indicii i i j sunt diferii, atunci cutm tranziiile de la qi la qj i scriem n tabel (pe linia corespunztoare lui rij) expresia obinut prin reuniunea acelor caractere de pe tranziii.

Deci 0021 R , 0

12R .

- Dac indicii i i j sunt egali, cutm buclele strii qi=qj i scriem n tabel expresia obinut prin reuniunea acelor caractere de pe bucle i a caracterului .

Deci 1011R , 0

22R .


@ MN 2014-2015

- 30 -

(b) Calculm a doua coloan, pentru k+1 = 1.

)1()1()1()1()( 0110

11

0

11

0

11

1

11 RRRRR

Dac notm )1( cu b,

avem )1(}1|{}2|{1 bnbnbbbbbb nn

Putem aplica formula (C) i avem )1()1()1(

Apoi putem aplica formula (D) pentru prima parte i obinem )1()1(

Dar i conform formulei (B) prima parantez este egal cu 1*, deci vom avea

)1(1)1()1( . Aplicm formula (E) (si apoi (C) i (B)) i obinem 1}0|1{}0|1{}1|1{11)1()11( nnn nnn pe care l trecem n

tabel.

0)1()1(0)( 0210

11

0

11

0

21

1

21 RRRRR

Aplicm formula (C) i obinem 0)1(0 , care este echivalent dup cum am aflat

mai sus cu 010)1(010010010

)1()1()( 0110

11

0

12

0

12

1

12 RRRRR

Aplicm formula (A) i avem

0)1()( 0210

11

0

12

0

22

1

22 RRRRR

1k

jiR k+1 = 0 k+1 = 1 k+1 = 2

rij = r11 1 + 1*

rij = r12 0 01 01

rij = r21

rij = r22

(c) Calculm ultima coloan, cea incomplet, pentru k+1 = 2.

Singura stare final este q2, deci avem de calculat doar eticheta de la starea q1 (cea iniiala) la starea q2. (Dac aveam mai multe stri finale, calculam pentru fiecare cte o expresie i apoi le reuneam.)

01)01()01()01()01()( 1 221

22

1

21

1

21

2

21 RRRRR

Deci expresia regulat corespunztoare automatului dat este 01 .


@ MN 2014-2015

- 31 -

Gramatici

G = (N, T, S, P)

N = {A, B, C, } mulimea de simboluri neterminale T = {a, b, c, ...} mulimea de simboluri terminale S N simbolul de start

P mulimea de producii (sau reguli de producie)

Modul n care este definit funcia P determin diferite tipuri de gramatici.

Gramatici independente de context (GIC) /

Context-free grammars (CFG) )( TNNP

Cazuri particulare de gramatici independente de context:

Gramatici liniare

Au producii de tipurile NBAiTyxcuxByA

NAiTxcuxA

,,,

,

Gramatici liniare la dreapta

Au producii de tipurile NBAiTxcuxBA

NAiTxcuxA

,,

,

Gramatici liniare la stnga

Au producii de tipurile NBAiTxcuBxA

NAiTxcuxA

,,

,

Gramatici regulate

O gramatic se numete regulat dac este liniar la dreapta sau liniar la stnga. Dar pentru c gramaticile liniare la dreapta i cele liniare la stnga definesc acelai set de limbaje, atunci n general ne referim la cele liniare la dreapta.

Deci gramaticile regulate au producii de tipurile

NBAiTacuaBA

aA

A

,,

Obs: Putem grupa mai multe producii care au acelai membru stng i putem scrie pe

scurt NBAiTacuaBaA ,,||


@ MN 2014-2015

- 32 -

EXEMPLE (gramatici regulate):

Vom relua acele exemple din primul seminar pentru care am construit automate finite

(pagina 5 din acest document), pentru a vedea corespondena strns dintre automate finite si gramatici regulate (dintre stri i neterminale; tranziii i producii).

Obs: Vom scrie pe scurt, doar produciile, acolo unde nu exist risc de confuzii (adic se nelege clar c literele mari sunt neterminale, literele mici sunt terminale, iar simbolul de start este S).

L1 = a* = {a

n, n 0} = {=a0, a=a1, aa=a2, aaa=a3, aaaa=a4, } |aSS

L2 = a+ = {a

n, n 1} = {a=a1, aa=a2, aaa=a3, aaaa=a4, } aaSS |

L3 = {a2n, n 0} = {=a0, aa=a2, aaaa=a4, aaaaaa=a6, }

aSA

aAS

|

L4 = {a2n+1, n 0} = {a=a1, aaa=a3, aaaaa=a5, }

aSA

aaAS

| sau

|aSA

aAS

L5 = {a2n, n 1} = {aa=a2, aaaa=a4, aaaaaa=a6, }

aaSA

aAS

|

sau

aAB

aaBA

aAS

| sau

|aAB

aBA

aAS

L6 = {a2n+1, n 1} = {aaa=a3, aaaaa=a5, aaaaaaa=a7, }

aaAB

aBA

aAS

|

sau

aB

aBaSA

aAS

|

L7 = {a2n

b3m, n 0, m 0}

= {, a2, a4, a6, a8, , b3, b6, b9, b12, , a2b3, a2b6, a4b3,a4b6, a6b3, a6b6, }

|

||

bBD

bDC

bCB

aSA

bBaAS

sau

bBD

bbDC

bCB

aSA

bBaAS

|

||


@ MN 2014-2015

- 33 -

Analogia ntre automate finite i gramatici regulate

i) La limbajele L1 i L2, unde avem cuvinte de forma an: - la automate avem bucl (adic tranziie de la o stare ctre ea nsi) - la gramatici avem o producie n care acelai neterminal apare i n membrul stng i

n cel drept al produciei

ii) La limbajele L3 L10, unde la putere avem i un coeficient numr natural (2 pentru a-uri i 3 pentru b-uri):

- la automate avem circuit de lungime egal cu coeficientul ntre stri diferite - la gramatici avem circuit de lungime egal cu coeficientul ntre neterminale diferite

iii) Dar ce se ntmpl dac avem limbaje definite folosind condiii asupra numrului de apariii ale caracterelor n cuvinte ?

- la automate ideea era s folosim indici la stri, cte unul pentru fiecare condiie - la gramatici ideea este s folosim indici la neterminale, cte unul pentru fiecare

condiie


@ MN 2014-2015

- 34 -

~ Seminar 4 ~ (Exemple cu gramatici independente de context GIC ;

Transformarea GIC gramatic n F.N. Chomsky ; Automatul Push-Down / Automatul Stiv)

EXEMPLE (gramatici independente de context):

n general, trebuie s lucrm cu gramatici independente de context, pentru c nu putem cu gramatici regulate (respectiv, trebuie s lucrm cu automate push-down, pentru c nu putem cu automate finite), atunci cnd limbajul conine cuvinte n care numrul de litere dintr-o parte a cuvntului depinde de numrul de litere din alt parte a cuvntului i deci avem nevoie s controlm cumva acest numr de litere.

L1 = {anb

n, n 0} = {=a0b0, ab=a1b1, aabb=a2b2, aaabbb=a3b3, aaaabbbb=a4b4, }

)2()1(

| aSbS sau )4()3(

)2()1(

|

|

aAbA

aAbS

Ideea acestei gramatici este de a genera cuvntul dinspre margini spre mijlocui lui, astfel

pentru fiecare aplicare a produciei (1) vor aprea un a i un b, iar ntre ele va rmne S-ul pentru a continua generarea. La final, se aplic producia (2) pentru a nu mai avea neterminal n cuvntul obinut. Cel mai mic cuvnd este ntr-adevr cuvntul vid, pentru c putem aplica direct a doua producie fr s o aplicm deloc pe prima.

L2 = {anb

n, n 1} = {ab=a

1b

1, aabb=a

2b

2, aaabbb=a

3b

3, aaaabbbb=a

4b

4, }

)2()1(

| abaSbS sau )3()2(

)1(

| aAbA

aAbS

Aici, cel mai mic cuvnt trebuie s fie ab, deci observm c din ambele gramatici de la exemplul anterior au disprut produciile S. n prima soluie avem ca pas se oprire cuvntul ab, iar n a doua soluie suntem obligai s generm cel puin un a i un b (prin prima producie) nainte de a ne opri (cu a treia producie).


@ MN 2014-2015

- 35 -

L3 = {anb

2n, n 1}

= {abb=a1b

2, aabbbb=a

2b

4, aaabbbbbb=a

3b

6, }

)2()1(

| abbaSbbS

Pentru fiecare a din prima parte a cuvntului trebuie s avem doi de b n a doua parte a cuvntului.

Deoarece avem n 1, pasul de oprire, a doua producie este cu abb n membrul drept.

Dac era n 0, atunci a doua producie ar fi avut ca membru drept cuvntul vid.

L4 = {a2n

bkc

3n, n 0, k 1} = { b=b

1, bb=b

2, bbb=b

3, bbbb=b

4, , aabccc=a

2b

1c

3, aabbccc=a

2b

2c

3, aabbbccc=a

2b

3c

3, aabbbbccc=a

2b

4c3, , aaaabcccccc=a

4b

1c

6, aaaabbcccccc=a

4b

2c

6, aaaabbbcccccc=a

4b

3c

6, ... }

)4()3(

)2()1(

|

|

bAA

bAaaScccS

Pentru fiecare aa de la nceputul cuvntului trebuie s avem ccc la finalul lui, iar ntre ele vom avea b-uri. Deci aici vom folosi nti neterminalul S pentru a genera a-urile i c-urile, iar apoi vom trece n alt neterminal cu ajutorul cruia vom genera b-urile. Observm c avem n 0, deci nu trebuie s-l obligm s aib a-uri i c-uri, ci trebuie s l lsm s treac direct la b-uri. Cel mai mic cuvnt este b: aplicm producia (2) i apoi pe (4).

L5 = {a2n

bkc

3n, n 1, k 1} = { aabccc=a

2b

1c

3, aabbccc=a

2b

2c

3, aabbbccc=a

2b

3c

3, aabbbbccc=a

2b

4c

3, , aaaabcccccc=a

4b

1c

6, aaaabbcccccc=a

4b

2c

6, aaaabbbcccccc=a

4b

3c

6, ... }

)4()3(

)2()1(

|

|

bbAA

aaAcccaaScccS

sau

)4()3(

)2()1(

|

|

bAA

aaAbcccaaScccS

sau

)4()3(

)2()1(

|

|

bAA

aabAcccaaScccS

Diferena fa de exemplul anterior este c aici i n este strict pozitiv, de aceea trebuie ca nainte de a trece la neterminalul A s generm obligatoriu minim doi de a i trei de c (producia a doua). Apoi n neterminalul A s generm cel puin un b (de aceea observm c s-a modificat i producia a patra). Cel mai mic cuvnt este aabccc: aplicm producia (2) i apoi (4).


@ MN 2014-2015

- 36 -

L6 = {a2n

c3n

bk, n 1, k 1}

= { aacccb=a2c

3b

1, aacccbb=a

2c

3b

2, aacccbbb=a

2c

3b

3, aacccbbbb=a

2c

3b

4, , aaaabccccccb=a

4c

6b

1, aaaaccccccbb=a

4c

6b

2, aaaaccccccbbb= a

4c

6b

3, ... }

)5()4(

)3()2(

)1(

|

|

bbBB

aacccaaAcccA

ABS

Observm c nu ntotdeauna putem genera cuvintele dinspre exterior spre centru, avnd maxim un singur neterminal n membrul drept al produciilor. Uneori este necesar s generm cuvintele pe buci, folosind pentru fiecare parte un neterminal separat. Aici, vom folosi neterminalul A pentru a genera a-urile i c-urile spre centru simultan cte doi de a i cte trei de c, iar din neterminalul B vom genera b-urile. Dac am fi avut condiia n 0, atunci producia (3) ar fi fost A, iar dac am fi avut condiia k 0, atunci producia (5) ar fi fost B.

Verificare generare cuvnt de ctre gramatic

Obs: Atenie la terminologia folosit: - automatul accept un (cuvnt din) limbaj - cuvntul / limbajul este acceptat de automat - gramatica genereaz un (cuvnt din) limbaj - cuvntul / limbajul este generat de gramatic

Pentru a verifica dac un cuvnt este sau nu generat de o gramatic, se folosesc arborii de derivare, care au ca rdcin simbolul de start al gramaticii (adic S, dac nu se specific altul). Pentru a trece de la un nod la altul al arborelui, ne alegem un neterminal care face parte

din cuvntul curent, cutm acele producii care l au ca membru stng, alegem una dintre ele i obinem noul cuvnt curent prin nlocuirea neterminalului cu membrul drept al acelei producii. - Fie ne oprim cnd am gsit un drum prin care am ajuns s generm cuvntul verificat (deci suntem ntr-o frunz a arborelui, nu mai avem neterminale n cuvnt). - Fie ne oprim cnd toate drumurile posibile au creat cuvinte mai lungi dect cel verificat,

dar fr s ntlnim frunza corect (deci nu are rost s continum pentru c vom gsi cuvinte din ce n ce mai lungi, deci diferite de cel verificat)

(a) Fie i reprezentm chiar sub form de arbore, de sus n jos ncepnd cu rdcina, etichetnd nodurile cu cuvntul curent, iar muchiile cu numrul produciei pe care am aplicat-o pentru a ajunge din nodul-tat n nodul-fiu.

(b) Fie i reprezentm de la stnga la dreapta cu aceeai convenie pentru etichetele nodurilor i muchiilor. n acest caz, ori decidem s urmm toate ramificaiile posibile, ori


@ MN 2014-2015

- 37 -

scriem direct doar drumul care ne duce la rezultat (fiind cuvinte scurte i gramatici destul de mici, putem vedea drumul far prea mare greutate). Preferabil alegem a doua variant cnd avem de verificat un singur cuvnt.

Obs: Uneori se poate ntmpla ca pentru un cuvnt s existe mai muli arbori de derivare distinci. (i) Dac gramatica este regulat, asta poate nsemna c n gramatic exist unele producii redundante (care ar putea fi eliminate fr s apar probleme, adic dup eliminare s se obin o gramatic echivalent cu cea iniial). (ii) Iar dac gramatica este independent de context i are cel puin o producie n al crei membru drept apar mai multe neterminale, atunci apar mai muli arbori pentru un cuvnt care conine la un moment dat mai multe neterminale, pentru c nu este obligatoriu s ncercm s rescriem doar neterminalul cel mai din stnga/dreapta, ci putem s le alegem n orice ordine.

EXEMPLU:

Pentru gramatica anterioar, vom verifica dac genereaz cuvntul 6364 Lbca .

)5()4(

)3()2(

)1(

|

|

bbBB

aacccaaAcccA

ABS

(a) Avei aici (http://bit.ly/arbore_derivare) poza arborelui de derivare pentru a gsi toate drumurile posibile prin care poate fi obinut cuvntul dat. n desen, muchiile sunt etichetate cu numrul produciei care a fost aplicat, iar nodurile interioare cu neterminalul care a fost rescris (n interiorul cercului) i cu noul cuvnt obinut (n dreptunghiul de sub cerc). Avem mai multe tipuri de noduri fr fii:

- Cele marcate cu -- reprezint nceputul unor subarbori care mai pot fi extini, dar n care nu vom mai gsi soluii pentru cuvntul dat. Acest lucru se poate ntmpla din dou motive: fie am aplicat de prea multe ori una dintre produciile recursive (2 sau 4), fie am aplicat producia pentru pasul de oprire (3 sau 5) nainte de a o aplica de suficiente ori pe cea recursiv.

- Cele marcate cu cerc dublu reprezint frunze ale arborelui, adic sfritul drumurilor n urma crora am obinut cuvinte fr neterminale, adic unele dintre cuvintele care sunt generate de gramatic.

- Cel marcate cu cerc dublu n care este scris OK reprezint toate drumurile prin care putem genera cuvntul dat.

Observm (direct din cuvnt i din structura gramaticii) c produciile pe care trebuie s le aplicm sunt: o dat (1), apoi o dat (2), o dat (3) (dar numai dup ce a fost aplicat 2), de dou ori (4), o dat (5) (dar numai dup ce a fost aplicat 4 de dou ori). Dar ordinea pentru 2,3,4,5 poate fi oricare n afara restriciilor menionate. De aceea vom obine cele 10 soluii: 23445, 24345, 24435, 24453, 42345, 42435, 42453, 44235, 44253, 44523.


@ MN 2014-2015

- 38 -

(b) A doua variant, scriem direct pe scurt un drum prin care tim c vom obine cuvntul dat. l vom alege pe primul, n care vom rescrie mereu cel mai din stnga neterminal.

364)5(

264)4(

64)4(

64)3()2()1(

bcaBbcaBbcaBcacccBAaaBAS

Obs: Dac cerina este doar de a verifica pentru un anumit cuvnt dac este sau nu generat de gramatic, atunci este preferabil varianta (b). Dar dac cerina este s se afle toate cuvintele generate de o gramatic, pentru o lungime de cuvnt dat sau pentru un numr maxim de aplicri ale produciilor, atunci trebuie folosit varianta (a) cu extinderea mai multor drumuri.

Continum cu exemplele de gramatici independente de context.

Dac avem cuvinte formate din 4 poriuni (a, b, c, d) i vrem ca lungimile poriunilor (puterile la care sunt literele) s depind unele de altele grupate dou cte dou atunci avem doar dou posibiliti de grupare: prima cu a patra (i a doua cu a treia) sau prima cu a doua (i a treia cu a patra). Deci nu vom putea s avem grupe intersectate (prima cu a treia; a doua cu a patra)!

L7 = {an

bk

c2k

dn, n 1, k 0}

= { ad, a2d

2, a

3d

3, a

4d

4, ..., abc

2d, ab

2c

4d, ab

3c

6d, ..., a

2bc

2d

2, a

2b

2c

4d

2, a

2b

3c

6d

2, ... }

)4()3(

)2()1(

|

|

bAccA

aAdaSdS

sau

)5()4(

)3()2()1(

|

||

bAccA

aAdadaSdS

(n a doua soluie, producia (2) este redundant pentru c poate fi obinut aplicnd (3) i apoi (5))

Aici avem grupate poriunile 1-4 i 2-3, deci vom genera cuvintele dinspre exterior spre centru, nti a-urile simultan cu d-urile, iar apoi b-urile simultan cu c-urile. Atenie, trebuie s folosim neterminale diferite, pentru c altfel s-ar genera i cuvinte cu literele amestecate (a i b ntre ele i c i d ntre ele). Avem k 0, deci b-urile i c-urile pot lipsi, de aceea avem producia (4) pe care o aplicm pentru cazurile cnd avem k = 0. Avem n 1, deci producia (2), pentru c trebuie s ne asigurm c avem cel puin un a i un d nainte de a trece la neterminalul A pentru a genera mijlocul cuvntului.

Dac am fi avut k 1, atunci producia (4) s-ar fi transformat n Abcc.

L8 = {an

bk

c2k

dn, n 0, k 1}

= { bc2, b

2c

4, b

3c

6, ..., abc

2d, ab

2c

4d, ab

3c

6d, ..., a

2bc

2d

2, a

2b

2c

4d

2, a

2b

3c

6d

2, ... }


@ MN 2014-2015

- 39 -

)4()3(

)2()1(

|

|

bAccA

bAccaSdS

Structura cuvintelor este aceeai ca la exemplul anterior, s-au schimbat doar condiiile. Avem n 0, deci a-urile i d-urile pot lipsi, dar mijlocul nu. De aceea avem producia (2) n care folosim direct bcc-ul pentru a trece la neterminalul A. Avem k 1, dar deja am citit un bcc cu neterminalul S, deci pasul de oprire pentru A va fi cu cuvntul vid.

Dac am fi avut k 0, nseamn c i mijlocul (b-urile i c-urile) ar fi putut lipsi, deci am fi avut n plus producia S.

L9 = {an

b2n

c2k

dk, n 0, k 1}

= { c2d, c

4d

2, c

6d

3, ..., ab

2c

2d, ab

2c

4d

2, ab

2c

6d

3, ..., a

2b

4c

2d, a

2b

4c

4d

2, a

2b

4c

6d

3, ... }

)5()4(

)3()2(

)1(

|

|

ccdccBdB

aAbbA

ABS

Aici avem grupate poriunile 1-2 i 3-4, deci din simbolul de start S ne vom ramifica n dou pri disjuncte: vom folosi un neterminal A pentru a genera dinspre exterior spre interior poriunea cu a-uri i b-uri, iar separat vom folosi un neterminal B pentru a genera dinspre exterior spre interior poriunea cu c-uri i d-uri. Avem n 0, deci pasul de oprire pentru A va fi cuvntul vid. Avem k 1, deci pasul de oprire pentru B va fi ccd.

L10 = {an

b2n

ck

dm

e3k, n,k,m 0}

)9()8(

)7()6()5(

)4()3(

)2()1(

|

||

|

|

dCC

dCcBeeeB

aAbbA

ABS

(producia (2) este reduntant pentru c poate fi obinut din 1, 4, 6)

Vom folosi neterminaul A pentru a genera spre interior a-urile i b-urile. Separat, vom folosi neterminalul B pentru a genera spre interior c-urile i e-urile, iar apoi ntre ele d-urile.


@ MN 2014-2015

- 40 -

Pentru n 0 avem producia (4). Pentru m 0 avem producia (6). Pentru k 0 avem producia (7) (n care trecem direct cu d mai departe fr s fi citit ceee) sau producia (6) (atunci cnd avem i m = 0).

Transformarea GIC gramatic n F.N. Chomsky

O gramatic este (scris) n forma normal Chomsky dac are doar producii care au n membrul stng un neterminal, iar n membrul drept fie un terminal, fie dou neterminale.

BCA

aA

EXEMPLU:

Avem urmtoarea gramatic independent de context:

)11(

)10()9(

)8(

)7()6(

)5()4(

)3()2()1(

|

|

|

||

H

gfG

GF

dD

bB

HBcHFaBcDeFS

Pasul 1 Eliminarea produciilor Vrem s nu mai avem n gramatic producii care au ca membru drept cuvntul vid. Pot exista dou situaii:

(i) Dac neterminalul care are o producie NU are i alte producii, atunci - va fi eliminat producia lui - toate produciile care au ca membru drept un cuvnt de lungime minim 2 n care

apare acest neterminal vor fi nlocuite prin eliminarea neterminalului din cuvinte - dac membrul drept avea lungime 1 (adic era doar acest neterminal), atunci se

nlocuiete cu (dar i aceast producie va fi ulterior eliminat tot la pasul 1)

n EXEMPLU:

Neterminalul H este singurul de acest gen, avnd doar producia (11), care va fi eliminat. n plus, producia (2) va fi nlocuit cu SF (12), iar producia (3) va fi nlocuit cu SBc (13).


@ MN 2014-2015

- 41 -

)10()9(

)8(

)7()6(

)5()4(

)13()12()1(

|

|

|

||

gfG

GF

dD

bB

BcFaBcDeFS

(ii) Dac neterminalul care are o producie are i alte producii, atunci - va fi eliminat doar producia lui - toate produciile care au ca membru drept un cuvnt de lungime minim 2 n care

apare acest neterminal vor fi nlocuite att de varianta n care cuvntul conine neterminalul, ct i de varianta n care neterminalul este eliminat din cuvnt

- dac membrul drept avea lungime 1 (adic era doar acest neterminal), atunci aceast producie este o redenumire i va fi eliminat la pasul 2

n EXEMPLU:

Neterminalele B i D au mai multe producii printre care i cte o producie. Deci (5) i (7) vor fi eliminate.

n producia (13) apare doar B, deci va fi nlocuit cu SBc (14) i Sc (15). n producia (1) apar i B i D, deci va fi nlocuit de toate variaiile posibile: -- B i D prezente: SaBcDeF (16) -- B lips, D prezent: SacDeF (17) -- B prezent, D lips: SaBceF (18) -- B i D lips: SaceF (19)

)10()9()8()6()4(

)15()14()11()19()18()17()16(

|;;;

||||||

gfGGFdDbB

cBcFaceFaBceFacDeFaBcDeFS

Pasul 2 Eliminarea redenumirilor Vrem s nu mai avem n gramatic producii care au ca membru drept un neterminal.

nlocuim neterminalul din dreapta cu toate cuvintele care sunt membru drept n

produciile sale. Verificm dac acest neterminal din dreapta mai apare n dreapta n cadrul altor producii

- Daca nu, atunci eliminm toate produciile pe care le avea. - Dac mai apare n cuvinte de lungime minim 2, arunci trebuie s i le pstrm - Dac apare n cuvnt de lungime 1, nseamn c este tot o redenumire i va fi

eliminat tot la pasul 2

n EXEMPLU:

Avem dou iruri de redenumiri: F G (8) f (9) | g (10) Producia (8) va fi nlocuit cu Ff (20) i Fg (21).


@ MN 2014-2015

- 42 -

Neterminalul G nu mai apare nicieri n dreapta, deci vom elimina (9) i (10). S F (11) f (20) | g (21) Producia (11) va fi nlocuit cu Sf (22) i Sg (23). Dar neterminalul F mai apare n dreapta n produciile 1619, deci NU vom

elimina produciile lui F.

)21()20()6()4(

)15()14()23()22()19()18()17()16(

|;;

|||||||

gfFdDbB

cBcgfaceFaBceFacDeFaBcDeFS

Pasul 3 Adugare neterminale noi pentru terminalele din cuvinte Vrem ca terminalele s apar doar singure n membrul drept. De aceea, peste tot unde apar n componena unui cuvnt de lungime minim 2, le vom nlocui cu un neterminal nou i vom aduga producia de la neterminalul nou la terminalul pe care l-a nlocuit.

n EXEMPLU:

Produciile 22, 23, 15, 4, 6, 20, 21 au deja forma dorit. Producia (16) va fi nlocuit cu S Xa B Xc D Xe F (24). Producia (17) va fi nlocuit cu S Xa Xc D Xe F (25). Producia (18) va fi nlocuit cu S Xa B Xc Xe F (26). Producia (19) va fi nlocuit cu S Xa Xc Xe F (27). Producia (14) va fi nlocuit cu S B Xc (28). n plus, vom avea Xaa (29); Xcc (30); Xee (31).

)31()30()29(

)21()20()6()4(

)15()28()23()22()27()26()25()24(

;;

|;;

|||||||

eXcXaX

gfFdDbB

cXBgfFXXXFXXBXFXDXXFXDXBXS

eca

cecaecaecaeca

Pasul 4 Adugare neterminale noi pentru spargerea cuvintelor lungi (>2) Vrem ca n dreapta s avem cuvinte formate din exact dou neterminale. De aceea, unde avem cuvinte mai lungi, pstrm doar primul neterminal din cuvnt i i alipim un neterminal nou, iar noul neterminal va avea o producie cu membrul drept cuvntul pe care l-a nlocuit. Relum procedeul pn cnd toate cuvintele ajung la lungimea 2.

Obs: Fiecare producie care avea un cuvnt de lungime k va fi nlocuit de k1 producii cu cuvinte de lungime 2.

n EXEMPLU:

Producia (24) va deveni SXa Y1 (32), iar Y1 ~ B Xc D Xe F. Apoi Y1B Y2 (33), iar Y2 ~ Xc D Xe F. Apoi Y2Xc Y3 (34), iar Y3 ~ D Xe F. Apoi Y3D Y4 (35), iar Y4~ Xe F. n final Y4 Xe F (36).

Observm c putem avea sufixe comune ale cuvintelor i atunci am putea folosi neterminale deja adugate anterior.


@ MN 2014-2015

- 43 -

Producia (25) va deveni SXa Y2 (37), pentru c aveam Y2 ~ Xc D Xe F. Producia (26) va deveni SXa Y5 (38), iar Y5 ~ B Xc Xe F. Apoi Y5B Y6 (39), iar Y6 ~ Xc Xe F. Apoi Y6Xc Y4 (40), pentru c aveam Y4~ Xe F. Producia (27) va deveni SXa Y6 (41), pentru c aveam Y6 ~ Xc Xe F.

)40(

46

)39(

65

)36(

4

)35(

43

)34(

32

)33(

21

)31()30()29(

)21()20()6()4(

)15()28()23()22()41(

6

)38(

5

)37(

2

)32(

1

;;;;;

;;

|;;

|||||||

YXYYBYFXYYDYYXYYBY

eXcXaX

gfFdDbB

cXBgfYXYXYXYXS

cec

eca

caaaa

Automatul Push-Down (APD) / Automatul Stiv

APD = (Q, , q0, F, , , Z0) Q mulimea de stri alfabetul de intrare q0Q starea iniial

FQ mulimea de stri finale

alfabetul stivei (gamma) Z0 simbolul iniial al stivei

QQ: funcia de tranziie (delta)

Modul n care funcioneaz tranziiile pentru un APD - La intrare avem nevoie de 3 parametri:

- starea curent (element din mulimea Q) - caracterul curent din cuvntul de intrare (element din mulimea ) - simbolul aflat n vrful stivei (element din mulimea ) - La ieire vom avea 2 parametri: - starea n care ajungem (element din mulimea Q) - cuvntul cu care nlocuim simbolul din vrful stivei (element din mulimea *)

Atenie! Simbolul din vrful stivei este mereu eliminat din stiv, nainte de a se aduga noul cuvnt n locul lui.

Deci avem mai multe variante pentru aceast nlocuire: - Dac scriem n stiv, nseamn c doar am ters simbolul din vrful stivei fr

a aduga nimic n locul lui. - Dac scriem acelai caracter n stiv (cel care fusese eliminat), nseamn c dorim

s pstrm stiva nemodificat. - Dac scriem n stiv un cuvnt de lungime minim 2 avem dou cazuri:


@ MN 2014-2015

- 44 -

-- dac dorim s pstrm i caracterul care era deja n stiv, atunci cuvntul introdus va avea ultima liter exact cea care fusese eliminat (deci partea de nceput, din stnga, a cuvntului reprezint vrful stivei). -- dac nu dorim s pstrm caracterul care era n vrful stivei, ci chiar s-l nlocuim, atunci cuvntul se poate termina cu alt caracter dect cel eliminat.

Obs: La fel ca automatele finite, i automatele push-down pot fi: - deterministe (definite anterior, dar sunt acceptate i tranziiile! Dar dac ntre

dou stri avem tranziie, nu putem avea tranziie i cu un caracter din .) - nedeterministe (cnd avem mai multe posibiliti de continuare: fie ajungnd n

stri diferite, fie scriind pe stiv cuvinte diferite, fie ambele (ajungnd n stri diferite i scriind pe stiv cuvinte diferite))

- nedeterministe cu tranziii (cnd ntre dou stri avem voie s avem tranziii i cu i cu caractere din i n plus avem nedeterminismul descris anterior)

Modaliti de acceptare a unui cuvnt de ctre un APD

(a) cu stri finale

},),,,(),,(|{)(*

00

FppZwqwAPDLF

(Obs: semnul cu stelu deasupra ar trebui s fie doar T-ul ntors, fr sgeat n dreapta, dar nu am gsit simbolul potrivit...)

Citim: Cuvntul w este acceptat de automat dac pornind din configuraia avnd starea q0, cuvntul de intrare w i pe stiv simbolul iniial Z0, dup ce aplicm un numr oarecare de tranziii ajungem n configuraia final.

n acest caz (a) ne intereseaz: - prima component s fie o stare final; - a doua component s fie cuvntul vid (adic s fi terminat de parcurs tot cuvntul

de intrare)

n acest caz (a) NU ne intereseaz a treia component (coninutul stivei): poate s fie vid sau poate s conin un cuvnt cu simboluri din alfabetul .

(b) cu vidarea stivei

}),,,(),,(|{)(*

00 QppZwqwAPDL

n acest caz (b) ne intereseaz: - a doua component s fie cuvntul vid (adic s fi terminat de parcurs tot cuvntul

de intrare)

- a treia component s fie cuvntul vid (adic stiva s fie vid) n acest caz (b) NU ne intereseaz prima component: starea n care ajungem poate s fie final sau poate s fie nefinal.


@ MN 2014-2015

- 45 -

Obs: Atenie, dac tergei tot coninutul stivei, automatul i oprete funcionarea, pentru c nu poate aplica funcia delta dac nu mai are parametrul al treilea (simbolul din vrful stivei). Deci asigurai-v c nu se va ntmpla asta nainte de a fi citit tot cuvntul de intrare. n general e bine s-l pstrm pe Z0 la nceput i s-l eliminm abia la final (eventual folosind o tranziie).

(c) cu stri finale i cu vidarea stivei n unele cri apare i acest al treilea caz, care este de fapt intersecia primelor dou.

}),,,(),,(|{)(*

00& FppZwqwAPDLF

n acest caz (c) ne intereseaz: - prima component s fie o stare final; - a doua component s fie cuvntul vid (adic s fi terminat de parcurs tot cuvntul

de intrare)

- a treia component s fie cuvntul vid (adic stiva s fie vid)

EXEMPLE (automate push-down):

De fiecare dat vom scrie n cuvinte modul n care vom folosi stiva. Adic pentru un caracter anume citit din cuvntul de intrare ce dorim s se ntmple pe stiv:

- s eliminm de tot vrful stivei sau s-l pstrm? - s scriem i ceva n plus sau s lsm stiva exact cum era nainte?

Putem reprezenta automatul push-down n dou moduri: (i) Fie alegem s scriem lista cu cazurile n care definim funcia de tranziie i menionm dac avem stri finale care sunt ele. (ii) Fie alegem s facem ca la automatele finite, s desenm sub form de graf cu nodurile stri i muchiile tranziii.

Obs: Avantajul alegerii variantei (i) ar fi faptul c putem pune comentarii n dreptul rndurilor pentru a urmri mai uor logica automatului, iar dac greim ceva cnd scriem pe foaie e mult mai uor de corectat prin tierea/adugarea unui rnd (mai ales pentru c nu conteaz ordinea n care sunt scrise rndurile) dect modificarea pe desen. Totui, pentru unele limbaje se poate s vi se par mai intuitiv varianta cu graful i atunci o putei folosi.

L1 = {anb

n, n 1} Vrem ca numrul de a-uri s fie egal cu numrul de b-uri, deci vom reine acest numr cu ajutorul stivei astfel:

- pentru fiecare a citit din cuvntul de intrare, vom aduga un A n stiv; - pentru fiecare b citit vom terge un A din stiv;


@ MN 2014-2015

- 46 -

Trebuie s ne asigurm c citim cel puin un a i un b (pentru c n 1) i c literele nu sunt amestecate. De aceea, dup ce citim primul b va trebui s schimbm starea.

),(),,( 0000 AZqZaq // citim primul a, mereu iniial l gsim pe Z0 n stiv

// vrem s scriem A, dar s-l pstrm i pe Z0, deci scriem AZ0

),(),,( 00 AAqAaq // citim oricare alt a i avem A n stiv (introdus anterior),

// vrem s scriem A, dar fr s-l tergem pe anteriorul, deci scriem AA

),(),,( 10 qAbq // citim primul b, gsim A n stiv

// schimbm starea, vrem s-l tergem pe A, deci scriem n locul lui

),(),,( 11 qAbq // citim oricare alt b, gsim sigur A n stiv; scriem pe stiv

Pentru a termina execuia i a accepta cuvintele prin cele 3 metode: (a) cu stri finale:

Adugm ),(),,( 0201 ZqZq sau ),(),,( 201 qZq .

Avem }{ 2qF stare final. Putem s-l pstrm pe Z0 pe stiv sau s-l tergem.

(b) cu vidarea stivei:

Adugm ),(),,( 101 qZq sau ),(),,( 201 qZq .

Putem avea FqFq 21 , . Ne intereseaz doar s avem pe stiv.

(c) cu stri finale i cu vidarea stivei:

Adugm ),(),,( 201 qZq .

Avem }{ 2qF stare final i stiva vid.

Aceeai soluie (c), sub form de graf:

Obs: Tranziiile se reprezint cu structura urmtoare: caracterul citit la intrare, apoi virgul, apoi caracterul care va fi eliminat din vrful stivei, apoi punct i virgul (sau slash / ), apoi cuvntul care va fi scris n stiv (cu aceeai convenie, prima liter din cuvnt este cea care va fi n vrful stivei dup adugarea cuvntului).

L2 = {anb

2n, n 0} Pentru fiecare a citit, vom aduga doi de A n stiv (adic AA). Pentru fiecare b citit, vom terge un A din stiv. Astfel ne asigurm c numrul de b-uri este dublul celui de a-uri. Schimbm starea dup ce citim primul b, pentru a nu amesteca literele. Trebui s ne asigurm c acceptm i cuvntul vid (pentru c avem n 0).


@ MN 2014-2015

- 47 -

}{

,//),(),,(

,//),(),,(

""//),(),,(

""//),(),,(

""//),(),,(

""//),(),,(

2

200

201

11

10

00

0000

qF

vidastivasif inalastarevidcuvantulacceptamqZq

vidastivasif inalastarecuvantulgataqZq

boricarepentruAunstergemqAbq

bprimulpentruAunstergemqAbq

aoricarepentruAAadaugamAAAqAaq

aprimulpentruAAadaugamAAZqZaq

Aceeai soluie, sub form de graf:

L3 = {a2n

bk

c3k

dn, n 1, k 1}

Pentru fiecare aa de la nceputul cuvntului trebuie s avem d la finalul cuvntului. (Obs: Dac am vrea s adugm cte un A pentru fiecare a, atunci ar trebui ca pentru fiecare d s dispar doi de A; nu putem face asta direct, ci ar trebui un circuit de lungime 2 ntre dou stri, cu o muchie se elimin un A pentru d-ul citit, iar cu muchia de ntoarcele se elimin un A fcnd o tranziie) Cel mai simplu, pentru pentru fiecare aa citii, vom scrie n stiv un singur A (pentru primul a din pereche se adaug A, pentru al doilea a nu se modific stiva). Avem nevoie de circuit de lungime 2 pentru a controla ca numrul de a-uri s fie par. La mijlocul cuvntului, pentru fiecare b din stnga trebuie s avem ccc n dreapta. Deasupra A-urilor din stiv, pentru fiecare b vom aduga cte 3 de B. Apoi pentru fiecare c vom terge cte un B din stiv. (Obs: Pentru c-uri nu vom avea nevoie de circuit de lungime 3 ntre stri pentru c n stiv avem deja un numr de B-uri multiplu de 3.) La final, pentru fiecare d vom terge cte un A.

),(),,( 0100 AZqZaq // pentru primul a, adugm un A

),(),,( 01 AqAaq // pentru a-ul al 2-lea (4-lea, 6-lea, ...) nu modificm stiva

),(),,( 10 AAqAaq // pentru a-ul al 3-lea (5-lea, 7-lea, ...) adugm un A

),(),,( 20 BBBAqAbq // pentru primul b schimbm starea, adugm BBB

),(),,( 22 BBBBqBbq // pentru orice alt b, adugm BBB

),(),,( 32 qBcq // pentru primul c schimbm starea, tergem un B

),(),,( 33 qBcq // pentru orice alt c, tergem un B

),(),,( 33 qAdq // pentru orice d, tergem un A


@ MN 2014-2015

- 48 -

),(),,( 403 qZq // am terminat cuvntul, stare final i stiv vid

}{ 4qF

Obs: Cnd am nceput s citim d-urile nu a fost neaprat necesar s schimbm starea fa de cea n care am citit c-urile, deoarece nu exist problema amestecrii lor. Putem citi c-uri doar att timp ct gsim B-uri n stiv, iar

LFA - Explicatii Exercitii, Algoritmi [SE 1-4]

Documents

Transcript of LFA - Explicatii Exercitii, Algoritmi [SE 1-4]