Complemente de matematic a pentru Computer …mcrasm/depozit/Comp_BOOK.pdfCursul 1 Monoidul...

Complemente de matematicapentru

Computer Science

Mircea Crasmareanu

Cuprins

1 Monoidul cuvintelor unui alfabet 1

2 Limbaje formale 7

3 Expresii regulate 15

4 Varietati de monoizi 21

5 Automate 29

6 Automate echivalente 33

7 Automat minimal 39

8 Actiuni 45

9 Gramatici si limbaje generate. Ierarhia Chomsky 53

10 Problema cuvintelor 57

11 Functii recursive 61

12 Multimi si limbaje recursiv enumerabile 67

13 Entropia, energia si corelatia surselor de informatie 71

14 Compilatoare 1: Analiza lexicala 77

Bibliografie 81

Index 83

iii

iv CUPRINS

Cursul 1

Monoidul cuvintelor unuialfabet

In acest curs se defineste una din notiunile de baza ale ıntregului curs.

Definitia 1.1 Numim alfabet o multime nevida Σ ale carei elemente lenumim simboluri sau litere.

Exemple 1.2 i) Σ = B = {0, 1} este alfabetul binar iar Σ = {0, ..., 9}este alfabetul zecimal. Alfabetul {A, ..., Z} are 26 de litere.ii) Alfabetul ASCII (American Standard Code for Information Interchange)contine 128 de simboluri pentru majoritatea computer languages.

In general vom utiliza alfabete finite dar exista si aspecte teoretice demare importanta ce apeleaza la alfabete infinite, de cardinal alef zero=car-dinalul multimii numerelor naturale N adica alfabete infinit numarabile.

Definitia 1.3 Numim cuvant nevid peste Σ o aplicatie w : Nk :={1, ..., k} → Σ cu k numar natural nenul numit lungimea cuvantului w sinotat l(w) sau |w|. Fie Σ+ multimea cuvintelor nevide.

Vom nota w = w(1)w(2)...w(k). Din motive tehnice se considera sicuvantul vid dat de functia vida ∅ → Σ si notat ε (sau λ) avand l(ε) = 0.Multimea tuturor cuvintelor (stringurilor) peste Σ o notam Σ∗ si va avea unrol important ın cele ce urmeaza. Deci Σ∗ = Σ+ ∪ {ε}.

Fie Σk multimea cuvintelor de lungime k; deci Σ0 = {ε} si Σ1 = Σ.Avem Σ∗ = ∪k≥0Σ

k. Elementele lui Σk le mai numim k-cuvinte.

Exemple 1.4 i) Dat a ∈ Σ definim ak prin a0 = ε respectiv ak = a...aunde ın membrul drept a apare de k ori. Deci ak ∈ Σk.ii) Pentru alfabetul binar avem Σ2 = {00, 01, 10, 11} si

1

2 M. Crasmareanu

Σ3 = {000, 001, 010, 100, 011, 101, 110, 111}.iii) Exemplul precedent sugereaza ca daca cardΣ = n atunci cardΣk = nk.

Definitia 1.5 Cuvintele w1, w2 ∈ Σ∗ le numim egale si scriem w1 = w2

daca apartin uneia din situatiile urmatoare:I) l(w1) = l(w2) = 0 adica w1 = w2 = ε,II) l(w1) = l(w2) = k ≥ 1 ın care caz cerem ca pentru orice i ∈ Nk sa avemw1(i) = w2(i).

Dupa cum era de asteptat avem:

Propozitia 1.6 Egalitatea este o relatie de echivalenta pe Σ∗.Demonstratia Se verifica (la Seminar) reflexivitatea, simetria si tranzi-

tivitatea. �Vrem sa structuram multimea tuturor cuvintelor si introducem ın acest

scop:

Definitia 1.7 Numim concatenare sau juxtapunere pe Σ aplicatia · :Σ∗ × Σ∗ → Σ∗, (w1, w2)→ w1w2 data de:I) εε = ε si εw = wε = w,II) w1w2 : N|w1|+|w2| → Σ este definita prin:II1) w1w2(i) = w1(i) daca i ∈ N|w1|,II2) w1w2(i) = w2(i− |w1|) altfel.

Reamintim ca numim semigrup o pereche (S, ·) cu S multime nevida si”·” o lege de compozitie asociativa pe S iar un monoid este un semigrupavand un element neutru.

Exemple 1.8 i) Multimea drumurilor ınchise (loop-uri) dintr-un varffixat al unui graf formeaza ımpreuna cu operatia de concatenare un monoidın care element neutru este drumul nul. Din acest exemplu si Exemplul1.4iii) rezulta ca anumite metode combinatoriale si de teoria grafurilor vorfi utile ın continuare.ii) Alte exemple vor fi discutate la Seminar.

Obtinem astfel structuri remarcabile pe multimi de cuvinte:

Teorema 1.9 i) (Σ+, ·) este semigrup.ii) (Σ∗, ·, ε) este monoid.iii) l : (Σ∗, ·, ε) → (N,+, 0) este morfism de monoizi: l(w1w2) = l(w1) +l(w2).

Observatii 1.10 i) Daca cardΣ ≥ 2 atunci Σ+ si Σ∗ sunt necomutative.In adevar, pentru alfabetul binar fie w1 = 10 si w2 = 0; avem w1w2 = 100 =w2w1 = 010.

Cursul 1 3

ii) Pentru simplificarea scrierii, la concatenarea unor cuvinte se pot utilizaputeri pentru stringuri ce se repeta. De asemeni, paranteze pentru stringuride lungime mai mare ca 1 ce se repeta. Atentie, puterea a doua a lui 01, i.e.0101, se scrie (01)2 si nu 012 care este 011.

Un motiv pentru care structura algebrica a acestor multimi de cuvinteeste bogata ın proprietati este acela ca sunt liber generate.

Definitia 1.11 i) Semigrup S se numeste generat de multimea finitaX ⊂ S daca orice element din S se scrie ca produs de elemente din X:pentru orice a ∈ S exista x1, ..., xk ∈ X asa ıncat a = x1...xk. Spunemdespre X ca este multime de generatori pentru S. Monoidul (M, ·, e) senumeste generat daca semigrupul SM =M \ {e} este generat.ii) S se numeste liber daca exista o multime de generatori X pentru caredescompunerea oricarui element a ∈ S ca mai sus este unica. M este liberdaca SM este liber.

Teorema 1.12 Σ+ si Σ∗ sunt liber generate de Σ.

Exemple 1.13 i) Monoidul cu un singur element (cel neutru) se con-sidera, prin definitie, generat de multimea vida. Tot prin conventie, acestmonoid este liber.ii) N este liber cu generatorul {1}. Pana la un izomorfism, {e} si N suntsingurii monoizi liberi comutativi.iii) Z este generat de {−1,+1} dar nu este liber deoarece, spre exemplu,2 = (+1) + (+1) = (+1) + (−1) + (+1) + (+1).iv) Este posibil ca multimea de generatori ai unui monoid sa nu fie unica.Astfel, pentru Z avem si generatorii {−2, 3}. Dar daca M este liber atuncimultimea generatorilor este unica.

Un rezultat foarte important pentru cele ce urmeaza este Proprietateade universalitate a monoizilor liberi care exprima faptul ca monoiziiliberi sunt obiecte initiale ın categoria monoizilor:

Teorema 1.14 Fie M liber generat de GM , M ′ un monoid oarecare sif : GM →M ′. Atunci exista si este unic F :M →M ′ morfism de monoizice extinde pe f .

Demonstratie Fie a ∈ M oarecare si descompunerea sa unica a =x1...xk. Definim F (a) = f(x1)...f(xk). �

Incheiem lista proprietatilor importante ale monoizilor liberi cu:

Propozitia 1.15 Dat monoidul liber M exista o multime finita Σ si unmorfism surjectiv de monoizi f : Σ∗ →M .

4 M. Crasmareanu

Demonstratie Fie Σ ce genereaza liber peM si incluziunea f : Σ→M .Aplicam proprietatea de universalitate. �

O alta proprietate remarcabila a monoizilor liberi este data de regulilede simplificare pe care o exemplificam direct pe monoidul cuvintelor. Fiedeci x, y, z, t ∈ Σ∗ cu xy = zt:1) daca l(x) = l(z) atunci y = t,2) daca l(x) < l(z) atunci exista m ∈M asa ıncat z = xm si y = mt,3) daca l(x) > l(z) atunci exista m ∈M astfel ca x = zm si t = my.

Definitia 1.16 Dat a ∈ Σ si w ∈ Σ∗ notam |w|a numarul de litere a dincuvantul w.

Exemple 1.17 |aba|a = 2, |aba|b = 1, |aba|c = 0; l(w) = Σa∈Σ|w|a.Definitia 1.18 i) Fie (S, ·) un semigrup si T ⊂ S submultime nevida.

Spunem ca T este subsemigrup al lui S daca T 2 ⊂ T i.e. pentru orice x, y ∈ Tavem xy ∈ T . Daca S este monoid cu elementul neutru 1 spunem ca T estesubmonoid daca este subsemigrup si 1 ∈ T .ii) Un semisubgrup al lui S ce este grup (ın sine ınsusi) se va numi subgrupal semigrupului (monoidului) S.

Pagini Web cu o parte din notiunile acestui curs:1) http://en.wikipedia.org/wiki/Monoid2) http://en.wikipedia.org/wiki/Initial and terminal objects3) http://en.wikipedia.org/wiki/Universal property

SEMINARUL 1

S1.1 i) Sa se arate ca elementul neutru al unui monoid M este unic.ii) Sa se arate ca x ∈M oarecare admite cel mult un invers.

Rezolvare i) Fie e si e′ elemente neutre. Deoarece e este neutru aveme′ = ee′ iar deoarece e′ este neutru avem e = ee′.ii) Fie x′ si x′′ inverse pentru x. Avem x′ = ex′ = (x′′x)x′ = x′′(xx′) =x′′e = x′′.

S1.2 Sa se arate ca G(M) = {x ∈ M ;x admite invers x−1} este grup;numit grupul unitatilor lui M .

Rezolvare Avem ca e ∈ G(M) deoarece e = ee = ee adica e−1 = e.Daca x ∈ G(M) atunci si x−1 ∈ G(M) cu (x−1)−1 = x.

S1.3 Fie S o multime nevida. Sa se arate ca F (S) = {f : S → S}este monoid relativ la compunerea functiilor. Cine este grupul unitatilor luiF (S)?

Cursul 1 5

Rezolvare Stim ca operatia de compunere a functiilor este asociativaiar element neutru este 1S functia identica. Avem ca G(F (S)) = Bij(S) ={f : S → S; f bijectie}.

S1.4 Se cer a, b ∈ N asa ıncat legea de compozitie liniara x∗y = ax+ bysa determine pe N o structura de monoid comutativ.

Rezolvare Din comutativitatea x ∗ y = y ∗ x avem ax + by = ay + bxceea ce ınseamna (a − b)(x − y) = 0 pentru orice x, y numere naturale;alegand x = y rezulta a = b si deci x ∗ y = a(x + y). Asociativitateaa[a(x+ y) + z] = a[x+ a(y+ z)] conduce la a2 = a. Cazul a = 0 este trivialsi-l eliminam; rezulta a = 1. In concluzie, avem (N,+, e = 0) ca unicalege de compozitie liniara ce da structura de monoid comutativ pe multimeanumerelor naturale.

S1.5 Fie (M, ∗) si (N, ◦) doua multimi ınzestrate cu legi de compozitiesi f : M → N o surjectie. Sa se arate ca daca M este monoid (abelian)atunci N este monoid (abelian).

S1.6 ! Sa se arate ca este posibila existenta unui subsemigrup T aleunui monoid M asa ıncat T este monoid fara a fi submonoid al lui M .

Rezolvare Fie M = N4 = {1, 2, 3, 4} cu legea xy = max{x, y}. Avemimediat ca (M, ·, 1) este monoid. Fie T = {2, 3, 4}; T este subsemigrup allui M dar nu este submonoid deoarece 1 nu apartine lui T . Pe de alta parte(T, ·, 2) este monoid.

S1.7 Elementul e al semigrupului S se numeste idempotent daca e2 = e.Definim pentru idempotentul e multimea He = {x ∈ S;xe = ex = x,∃y ∈S xy = yx = e}.i) Sa se arate ca He este multime nevida.ii) Sa se arate ca He este subsemigroup al lui S.iii) Sa se arate ca He este grup.iv) Se cer idempotentii si grupurile corespunzatoare He pentru monoidul dela exercitiul precedent.v) Sa se arate ca un semigrup finit S admite idempotenti.

Rezolvare i) e ∈ He.ii) Fie a, b ∈ He cu elementele corespunzatoare a′, b′. Avem: (ab)e = a(be) =ae = e si e(ab) = (ea)b = eb = e respectiv (ab)(b′a′) = a(bb′)a′ = aea′ =aa′ = e si (b′a′)(ab) = b′(a′a)b = b′eb = b′b = e.iii) Fie a ∈ He cu corespondentul a′ si sa consideram a−1 = ea′e. Avem:aa−1 = (ae)a′e = aa′e = ee = e si a−1a = ea′(ea) = ea′a = ee = e. Mai

6 M. Crasmareanu

trebuie aratat ca a−1 ∈ He: a−1e = ea′ee = a−1 si ea−1 = eea′e = a−1.

iv) Orice element e ∈ N4 este idempotent si He = {e}.

S1.8 Fie ∼ o relatie de echivalenta pe semigrupul (monoidul) S. Spunemca ∼ este o congruenta pe S daca a ∼ b si s ∈ S implica sa ∼ sb si as ∼ bs.Sa se arate ca ın acest caz S/ ∼ este un semigrup (monoid).

Rezolvare Definim [a][b] := [ab] si trebuie aratata buna definire. Dacaa ∼ c si b ∼ d atunci ab ∼ cb si cb ∼ cd de unde rezulta ab ∼ cd. Faptul caS/ ∼ este semigrup (monoid cu identitatea [1]) este imediat.

Exemplu Egalitatea pe monoidul cuvintelor este o congruenta.

S1.9 i) Sa se arate ca un morfism de semigrupuri f : S → T induce ocongruenta pe S.ii) Invers, data congruenta ∼ pe S avem ca π : S → S/ ∼, π(a) = [a] estemorfism de semigrupuri.In concluzie, exista o corespondenta naturala ıntre congruente si morfismede semigrupuri.

Rezolvare i) Definim ∼ pe S prin: a ∼ b daca f(a) = f(b). Cumegalitatea este o echivalenta avem ca ∼ este o echivalenta pe S. Fie s ∈ Soarecare. Cum f este morfism avem: f(as) = f(a)f(s) = f(b)f(s) = f(bs)si f(sa) = f(s)f(a) = f(s)f(b) = f(sb); deci ∼ este o congruenta pe S.ii) π(ab) = [ab] = [a][b] = π(a)π(b).

S1.10 Fie f : S → T morfism surjectiv de semigrupuri si ∼ relatia deechivalenta indusa de f . Atunci f∗ : S/ ∼→ T, f∗([a]) = f(a) este unmorfism bijectiv (i.e. izomorfism) de semigrupuri si notam S/ ∼≃ T .

Rezolvare Sa aratam buna definire: [a] = [b] implica f(a) = f(b) i.e.f∗([a]) = f∗([b]). Fie t ∈ T ; cum f este surjectiv˘ a exista s ∈ S asaıncat f(s) = t, rezulta f∗([s]) = t i.e. f∗ este surjectiva. Daca f∗([a]) =f∗([b]) atunci f(a) = f(b) i.e. [a] = [b], deci f∗ este injectiva. Avemsi f∗([a][b]) = f∗([ab]) = f(ab) = f(a)f(b) = f∗([a])f∗([b]) i.e. f∗ estemorfism de semigrupuri.

S1.11 Fie Σ o multime nevida, T un semigrup si aplicatia f : Σ → T .Atunci exista un unic morfism de semigrupuri g : Σ+ → T ce extinde pe fi.e. g(s) = f(s) pentru orice s ∈ S.

Rezolvare Fie w ∈ Σ+ cu expresia w = w(1)w(2)...w(k). Definimg(w) = f(w(1))...f(w(k)). Avem imediat ca g extinde pe f si ca este morfismde semigrupuri. Unicitatea rezulta din modul de constructie.

Cursul 2

Limbaje formale

Fixam alfabetul (finit) Σ.

Definitia 2.1 Numim limbaj (formal) peste Σ o submultime L ⊂ Σ∗ i.e.L este un element din multimea partilor lui Σ∗ i.e. L ∈P(Σ∗). Un elementdin L ıl numim propozitie sau afirmatie (statement ın engleza). Daca Leste multime finita spunem ca avem un limbaj finit; ın caz contrar avem unlimbaj infinit. Prin conventie, multimea vida ∅ se accepta ca limbajul vidpeste orice alfabet la fel ca si {ε}.

Observatii 2.2 i) ∅ = {ε}; astfel, primul limbaj n-are cuvinte ın timpce al doilea limbaj are un cuvant.ii) Limbajele de programare (e.q. Pascal, C, Java) sunt peste alfabetulASCII si sunt infinite.iii) Trebuie avuta o mare grija la modul (regula) de definire a unui lim-baj. Astfel, avem limbajele peste alfabetul binar L1 = {0n1n;n ∈ N} siL2 = {cuvinte cu acelasi numar de 0 si 1} care difera deoarece:L1 = {ε, 01, 0011, 000111, ...}, L2 = {ε, 01, 10, 0011, 1001, 1010, 1100, 0101, ...}.

Observatia 2.3 Dat limbajul nevid L consideram multimea alph(L) ={a ∈ Σ;∃u, v ∈ Σ∗ a. ı uav ∈ L}. Avem ca alph(L) este alfabetul minimalpeste care poate fi definit limbajul L.I) Sa aratam ca alph(L) este nevida.I1) ε ∈ L; atunci considerand u = v = ε rezulta ca a = ε ∈ alph(L).I2) Fie w ∈ L, w = ε. Luand u = ε si v = w(2)...w(|w|) daca |w| > 1respectiv v = ε daca |w| = 1 obtinem ca a = w(1) ∈ alph(L).II) Cum alph(L) ⊂ Σ si Σ este finita rezulta ca alph(L) este multime finita.Deci alph(L) este un alfabet.III) Faptul ca L ⊂ (alph(L))∗ este imediat folosind rationamente de tipul

7

8 M. Crasmareanu

celor de la I.IV) Faptul ca alph(L) este minimal cu proprietatea III ıl propunem ca Tema.

Operatii booleene cu limbaje 2.4: din teoria generala a multimiloravem ca date limbajele L1 si L2 sunt atunci limbaje:i) reuniunea L1 + L2 := L1 ∪ L2, ii) intersectia L1 ∩ L2,iii) complementara L1 := Σ∗ \ L1.Datorita structurii algebrice a lui Σ∗ putem defini si produsul L1L2 ={uv;u ∈ L1, v ∈ L2} care este evident un limbaj. Este avantajoasa notatiaexponentiala; astfel pentru limbajul L avem limbajele L0 = {ε}, Ln =Ln−1L pentru numarul natural nenul n.

Definitia 2.5 Limbajul L se numeste independent la concatenare dacaL ∩ ∪n≥2L

n = ∅.

Exemple 2.6 i) Pentru alfabetul binar si limbajul L = {01, 110} avem:L2 = {0101, 01110, 11001, 110110},L3 = {010101, 0111001, 1100101, 11011001, 0101110, 01110110, 11001110,110110110}.ii) Produsul limbajelor este necomutativ. Pentru L1 = {ε, 101} si L2 ={0, 0101} avem L1L2 = {1010, 1010101, 0, 0101} = {0101, 0101101, 0} =L2L1.

Exemplul 2.7 Fie Σ = {1, 2, 3}. L = {21, 213, 1, 2222, 3} este unlimbaj peste Σ si 213222213 ∈ L4 ∩ L5 deoarece 213, 2222, 1, 3 ∈ L iar21, 3, 2222, 1, 3 ∈ L. Totodata 213222213 ∈ Σ9.M = {2, 13, 222} este limbaj peste Σ si 213222213 ∈ L4∩L5∩M5∩M7 desiL ∩M = ∅.

Definitia 2.8 Dat limbajul L definim L+ = ∪n≥1Ln numit ınchiderea

pozitiva respectiv L∗ = ∪n≥0Ln numit ınchiderea star sau Kleene lui L. (A se

vedea http://en.wikipedia.org/wiki/Stephen Cole Kleene pentru opera sa.)

Observatia 2.9 i) Notatia anterioara provine din faptul ca pentru L = Σavem L+ = Σ+ si L∗ = Σ∗.ii) Pentru limbajul L oarecare avem ca L+ este subsemigrup ın Σ+ iar L∗

este submonoid ın Σ∗.

Propozitia 2.10 i) ε ∈ L∗, L+ = L∗L = LL∗, L∗ = LL∗ + {ε}ii) ε ∈ L+ daca si numai daca ε ∈ L,iii) L∗

1 + L∗2 ⊆ (L1 + L2)

∗, (L1 ∩ L2)∗ ⊆ L∗

1 ∩ L∗2,

iii) L1(L2L1)∗ = (L1L2)

∗L1,

Cursul 2 9

iv) L∗1(L2L

∗1)

∗ = (L1 ∪ L2)∗,

v) L3(L1 ∪ L2L3)∗L2 = (L3L

∗1L2)

+.

Definitia 2.11 Limbajul L se numeste regulat daca este vid sau se poateconstrui din elementele lui Σ folosind doar operatiile de produs, + si ∗.

Exemple 2.12 i) L = {numere binare nenule} este regulat peste alfa-betul binar deoarece L = 1(0 + 1)∗; orice numar binar nenul ıncepe cu cifra1 si se continua cu un sir (posibil vid) de 0 si 1. Aici si ın cele ce urmeaza,pentru simplificarea scrierii am renuntat la acolade.ii) Z se scrie 0 + (ε + m)d(0 + d)∗ peste Σ = {0, ..., 9,m = −} unded = 1 + 2 + ...+ 9.iii) Q = 0+ (ε+m)d(0+ d)∗ +(ε+m)(0+ (d(0+ d)∗))p(0+ d)∗d peste Σ ={0, ..., 9,m, p = .} unde ”.” este punctul (ın notatia anglo-saxona)=virgulazecimala.iv) Numerele binare cu blocuri de 1 avand lungime para=(0 + 11)∗.v) Numerele binare continand 1011=(0 + 1)∗1011(0 + 1)∗.

Teorema 2.13 i) Un limbaj finit este regulat.ii) Daca L1 si L2 sunt regulate atunci L1 ∩ L2 este regulat.iii) Daca L este regulat atunci L este regulat.

Definitia 2.14 Date cuvintele w, v ∈ Σ∗ spunem ca v este subcuvant allui w daca exista x, y ∈ Σ∗ asa ıncat w = xvy. Daca ın plus, x sau y diferade ε spunem ca v este subcuvant propriu al lui w. x ıl numim prefix sauinitial al lui w respectiv prefix propriu daca difera de ε; analog y este sufixsau terminal al lui w respectiv sufix propriu daca difera de ε.

O generalizare a Exemplului 2.3 este urmatoarea: pentru w ∈ Σ∗ fieSubP (w) multimea subcuvintelor proprii ale lui w. Avem ca SubP (w) esteun limbaj peste Σ. Analog, pornind cu limbajul L obtinem limbajul P (L) =∪w∈LSubP (W ).Spre exemplu, pentru L = {0, 010, 111} avem P (L) = {0, 1, 01, 10, 11}.

Definitia 2.15([12, p. 55]) Relatia de echivalenta R pe monoidul Σ∗ onumim cvasicongruenta daca odata cu uRv avem si xuyRxvy pentru oricex, y ∈ Σ. Daca ın plus, R are un numar finit de clase de echivalenta spunemca R este de index finit.

Exemple 2.16 i) Orice congruenta este cvasicongruenta.ii) Fixam limbajul L si definim uRLv daca pentru orice x, y ∈ Σ∗ cu l(x) =l(y) din xuy ∈ L rezulta xvy ∈ L si invers. Avem imediat ca RL este o elatiede echivalenta pe Σ∗.

Propozitia 2.17 RL este o cvasicongruenta.

10 M. Crasmareanu

Demonstratie Fie u, v, a, b ∈ Σ∗ cu l(a) = l(b) si uRLv. Deci aub ∈ Ldaca si numai daca avb ∈ L. Fie a = a′x si b = yb′ cu x, y ∈ Σ. Avema′xuyb′ ∈ L daca si numai daca a′xvybl ∈ L cu l(a′) = l(b′). RezultaxuyRLxvy pentru orice x, y ∈ Σ. �

Propozitia 2.18 Limbajul L este saturat de RL adica L este reuniuneaclaselor de echivalenta relativ la RL.

Demonstratie Din definitie cu x = y = ε avem ca uRLv daca avemechivalenta: u ∈ L daca si numai daca v ∈ L, ceea ce spune ca orice clasade echivalenta relativ la RL este inclusa ın L. �

Propozitia 2.19 Orice cvasicongruenta ce satureaza pe L este o rafinarea lui RL.

Pagini Web utile:1) http://en.wikipedia.org/wiki/Formal language2) http://mathworld.wolfram.com/FormalLanguage.html3) http://planetmath.org/encyclopedia/ImproperLanguage.html

SEMINARUL 2

S2.1 Fie Σ = {1, 2, 3, 4} si limbajele L = {12, 4}, M = {ε, 3}. Se cer:i) LM , ML, L2M , L2M2,ii) LM2L, M+, LM+, M∗.

Rezolvare i) LM = {12, 3, 123, 43}, ML = {12, 4, 312, 34}, L2M ={1212, 44, 12123, 443}, L2M2 = {1212, 44, 121233, 44333}.ii) LM2L = {1212, 44, 123312, 4334}, M+ = {ε, 3, 33, 333, ...}, LM+ ={12, 4, 123, 43, 1233, 433, ...}, M+ =M∗ deoarece ε ∈M .

S2.2 Pentru Σ anterior cate elemente din Σ4 ıncep cu 22?

Rezolvare Avem 4 cifre ın Σ ce trebuie aranjate ın perechi pentru aforma ultimele doua cifre ale elementelor cerute=4·4 = 16. Multimea cerutaeste {2211, 2222, 2233, 2244, 2212, 2221, 2213, 2231, 2214, 2241, 2223, 2232,2224, 2242, 2234, 2243}.

S2.3 Pentru Σ = {1, 2, 3, 4, 5} se cer:i) numarul elementelor lui Σ0 +Σ2,ii) numarul elementelor lui Σ6 ce ıncep cu 22 si sfarsesc cu 1.

Rezolvare i) |Σ0 +Σ2| = 1 + 52 = 26. ii) 53 = 125.

S2.4 Fie Σ de la Ex. 2.1.i) Cate cuvinte sunt ın Σ+ de lungime strict mai mica de 5?

Cursul 2 11

ii) Cate cuvinte sunt ın Σ∗ de lungime strict mai mica de 5?iii) Cate cuvinte sunt ın Σ+ ıncepand cu 12 si de lungime strict mai micade 5?

Rezolvare i) |Σ1 + ... + Σ4| = 4 + 42 + 43 + 44 = 4 + 16 + 64 + 256 =4(1 + 4 + 16 + 64) = 4 · 85 = 340.ii) |Σ0 + ...+Σ4| = 1 + 340 = 341.iii) 40+41+42 = 1+4+16 = 21 deoarece multimea ceruta este {12, 12x, 12xy;x, y ∈ Σ}.

S2.5 Se da limbajul L continand pe ε si alte 8 elemente diferite. Cateelemente are L2?

Rezolvare L2 = L+{xy;x, y ∈ L\{ε}}; deci |L2| = 9+82 = 9+64 = 73.

S2.6 Pentru Σ = {0, 1, 2} sa se decida daca afirmatiile urmatoare apartinlimbajului L = (0 + 1)∗2(0 + 1)∗22(0 + 1)∗:i) 120120210, ii) 1222011, iii) 22210101.

Rezolvare i) Nu, deoarece un element din L contine obligatoriu 22 cenu apare ın afirmatia data.ii) Da, scriind (1)2(ε)22(011).iii) Nu, deoarece un element din L ıncepe cu 0 sau 1 iar afirmatia data ıncepecu 2.

S2.7 Aceeasi problema pentru Σ = {0, 1, 2, 3},L = (0+1)∗2(0+1)+22(0+1+3)∗ si: i) 120122, ii) 1222011, iii) 3202210101.

Rezolvare i) Da, scriind (1)2(01)22(ε).ii) Nu, caci a treia cifra poate fi doar 0 sau 1 ori se ıncepe cu 2 iar afirmatiadata nu satisface niciuna din aceste conditii.iii) Nu, caci un element din L ıncepe cu 0, 1 sau 2.

S2.8 Aceeasi problema pentru Σ de la Ex. 2.6, L = (0+1)∗(102)(1+2)∗

si: i) 012102112, ii) 1110221212, iii) 10211111, iv) 102, v) 001102102.

Rezolvare i) Nu, deoarece ınaintea lui 102 apare 012 ∈ (0 + 1)∗.ii) Da, scriind 11(102)21212.iii) Da, scriind ε(102)11111.iv) Da, scriind ε(102)ε.v) Nu, deoarece dupa 102 apare 102 ce nu apartine lui (1 + 2)∗.

S2.9 Pentru Σ de la Ex. 2.7 se cere scrierea urmatoarelor limbaje:i) L = {afirmatiile ce contin o singura data cifra 2},ii) L = {afirmatiile ce contin de trei ori cifra 2},iii) L = {afirmatiile ce contin cifra 2},

12 M. Crasmareanu

iv) L = {afirmatiile ce contin cuvantul 2112},v) L = {afirmatiile ce contin cifra 2 ın cuvinte de lungime 3}.

Rezolvare i) L = (0 + 1 + 3)∗2(0 + 1 + 3)∗,ii) L = (0 + 1 + 3)∗2(0 + 1 + 3)∗2(0 + 1 + 3)∗2(0 + 1 + 3)∗,iii) L = (0 + 1 + 3)∗2+(0 + 1 + 3)∗,iv) L = (0 + 1 + 2 + 3)∗2112(0 + 1 + 2 + 3)∗,v) L = ((0 + 1 + 3)∗23)+.

S2.10 (Program C) Darea de la tastatura a unui caracter, afisareaacestuia, a predecesorului si succesorului si a codurilor ASCII aferente.

//predecesorul si succesorul unui caracter si codurile lor ASCII

#include<iostream.h>

void main ()

{char w, w1;

cout<< ”Dati litera:= ”;

cin>>w;

w1=w;

cout<< ”Codul ASCII al literei ” <<w<< ” este: ” <<hex<<int(w)<<” ” <<dec<<int(w)<<endl;

cout<< ”Codul ASCII al literei ” << −−w<< ” este: ” <<hex<<int(w-1)<< ” ” <<dec<<int(w-1)<<endl;

cout<< ”Codul ASCII al literei ” <<++w1<< ” este: ” <<hex<<int(w1+1)<< ” ” <<dec<<int(w1+1)<<endl;

}

Exemplu:

Dati litera:= H <Enter>

Codul ASCII al literei H este: 48 72

Codul ASCII al literei G este: 47 71

Codul ASCII al literei I este: 49 73

(Pe prima coloana apare codul hexazecimal iar pe a doua coloana celzecimal.)

Tema Scrieti varianta Pascal a problemei.

S2.11 (Program C) Sa se afiseze codurile, ın hexazecimal si zecimal,ale tuturor literelor.

//codurile ASCII ale tuturor literelor majuscule si minuscule


Cursul 2 13

void main ()

{char lit;

int i;

for (lit=’A’; lit<=’z’; lit++)

{i=lit;

cout<< ”Codul ASCII al literei ” <<lit<< ” este: ” <<hex<<i<<”” <<dec<<i<< endl ;

}}


S2.12 (Program C) Dat un numar natural se cere caracterul cores-punzator.

//conversia din ıntreg ın caracter


void main ()

{int n;

cout<< ” Dati numarul natural n:= ”;

cin>>n;

cout<< ” Caracterul corespunzator lui ” <<n<< ” este:= ” <<char(n)<<endl;

}

Exemplu:

Dati numarul natural n:= 321 <Enter>

Caracterul corespunzator lui 321 este:= A

(Un caracter ocupa un singur octet spre deosebire de un ıntreg care ocupa2 octeti. De aceea se calculeaza numarul dat modulo 28=256, ın exemplulnostru este 65 iar 65 este codul ın zecimal al lui A.)


S2.13 (Distanta Hamming pe k-cuvinte) Pentru k ∈ N definimdH : Σk × Σk → R+, dH(a, b) = |{i; a(i) = b(i)}|; deci dH(a, b) contorizeazanumarul simbolurilor diferite din a si b. Sa se arate ca dH este o metrica peΣk:I) (pozitiva definire) dH(a, b) ≥ 0; dH(a, b) = 0 daca si numai daca a = b,

14 M. Crasmareanu

II) (simetria) dH(a, b) = dH(b, a),III) (inegalitatea triunghiului) dH(a, c) ≤ dH(a, b) + dH(b, c).

S2.14 Se da limbajul L nevid ce satisface L2 = L. Sa se arate ca:i) daca L are un singur element atunci L = {ε},ii) daca L are mai mult de un element atunci exista w ∈ L cu w = ε si astfelca pentru orice v = ε avem l(w) ≤ l(v). Sa se deduca de aici ca ε ∈ L,iii) L∗ = L.

Rezolvare i) Fie L = {w} si k = l(w). Avem L2 = {w2} cu l(w2) = 2k.Din ipoteza rezulta 2k = k i.e. k = 0.iii) Avem L3 = L2 = L si analog pentru orice n ≥ 1 avem Ln = L; deciL+ = L. Cum ε ∈ L rezulta ca L∗ = L+ + ε = L+ ε = L.

S2.15 In Matlab, fie caracter (char) este reprezentat intern printr-ovaloare numerica corespondenta. astfel, ın locul accesarii acestor valori, sepoate lucra cu caractere, asa cum apar acestea pe ecran. Un sir de carac-tere (string) eset, deci, un vector ale carui elemente sunt codurile numericecorespunzatoare caracterelor de pe ecran.

Valorile de tip caracter se definesc folosind apostrofuri. De exemplu, sedefineste variabila x, cu valoare de tip caracter si se verifica cu functia classtipul acesteia:

>> x=’a’;>> class(x)ans =char

Similar pentru siruri de caractere:

>> y=’abcd’;>> whos yName Size Bytes Classy 1x4 8 char arrayGrand total is 4 elements using 8 bytes

Cursul 3

Expresii regulate

Ca si ın cursul precedent fixam de la bun ınceput un alfabet (finit) Σ.

Definitia 3.1 Consideram simbolurile ), (,+, ∗ ce nu apartin lui Σ. Nu-mim expresie regulata un cuvant w al alfabetului Σ∪{ε, (, ),+, ∗} avand unadin formele urmatoare:i) w ∈ Σ sau w = ε,ii) w = (xy) cu x, y expresii regulate,iii) w = x+ y cu x, y expresii regulate,iv) w = x∗ cu x expresie regulata.Fie Rex(Σ) multimea expresiilor regulate.

Observatii 3.2 i) Modul de definire al expresiilor regulate este inductiv.ii) Ca si ın cursul precedent uneori vom renunta la parantezele redundanteatunci cand contextul de lucru este evident.iii) Prin conventie, ∗ are prioritatea maxima, urmeaza concatenarea si apoi+. Astfel, ((((xx) + y)∗ + ((xy))x)) este (xx+ y)∗ + xyx.

Definitia 3.3 Aplicatia K : Rex(Σ)→P(Σ∗) definita prin:a) K(ε) = ∅, K(x) = {x} daca x ∈ Σ,b) K(xy) = K(x)K(y), K(x+ y) = K(x) +K(y),c) K(x∗) = (K(x))∗,o numim interpretare.

Teorema 3.4 (Kleene) Limbajul L ∈P(Σ∗) este regulat daca si numaidaca apartine imaginii aplicatiei de interpretare K i.e. exista o expresieregulata w ∈ Rex(Σ) asa ıncat L = K(w).

Exemple 3.5 i) Fie x, y ∈ Σ. AvemK((x+y)(x+y)) = {xx, xy, yx, yy}.ii) K(ε+ (x+ y)∗(yx+ xyx)) = {x, y}∗{yx, xyx}.

15

16 M. Crasmareanu

Definitia 3.6 Expresiile regulate w1, w2 ∈ Rex(Σ) se numesc echivalentedaca K(w1) = K(w2). Notam w1 = w2.

Exemple 3.7 i) w1 + w2 = w2 + w1 si ε+ w = w + ε = w pentru oricew1, w2, w ∈ Rex(Σ).ii) xx∗y + y = x∗y.

Propozitia 3.8 Notand cu E diverse expresii regulate avem urmatoareleproprietati de echivalenta:i) (E∗)∗ = E∗, E∗

1E∗2 = (E1 + E2)

∗,ii)(asociativitate) E1(E2E3) = (E1E2)E3, E1+(E2+E3) = (E1+E2)+E3,iii)(distributivitate) E1(E2 + E3) = E1E2 + E1E3, (E1 + E2)E3 = E1E3 +E2E3.

Definitia 3.9 Expresia regulata E ∈ Rex(Σ) se numeste ambigua dacaexista o afirmatie ın K(E) care se poate descrie ın doua moduri diferite (farautilizarea cuvantului vid la concatenare!).

Exemplu 3.10 E = (xy)∗ + (x+ y)∗ este ambigua deoarece xy ∈ K(E)se poate scrie xy + ε si ca element din ε+ (x+ y)∗.

In scrierea unor limbaje de programare gasim expresii de tipul:

< litera >::= A|B|...|Z, < cifra >::= 0|1|...|9,

< identificator >::=< litera > (< litera > | < cifra >)

ce sunt exact expresii regulate avand variabilele < litera >, < cifra > si< identificator > iar simbolul | joaca rolul lui +.

Pentru limbajul fixat L definim relatia: σL = {(w, z) ∈ Σ∗ × Σ∗;uwv ∈L ⇔ uzv ∈ L,∀u, v ∈ Σ∗}. Deoarece echivalenta logica este o relatie deechivalenta avem ca σL este o relatie de echivalenta. Sa aratam ca este ocongruenta. Fie (w, z) ∈ σL si x ∈ Σ∗ oarecare. Avem ca (xw, xz) ∈ σL si(wx, zx) ∈ σL ın mod evident datorita regulilor de simplificare din monoidulΣ∗. σL o numim congruenta sintactica asociata limbajului L iar monoidulcat Syn(L) = Σ∗/σL se numeste monoidul sintactic al lui L.

Definitia 3.11 Limbajul L este recunoscut de monoidul M daca existaun morfism de monoizi φ : Σ∗ →M si P ⊂M asa ıncat L = φ−1(P ).

Propozitia 3.12 L este recunoscut de monoidul sintactic Syn(L).Demonstratie Aplicatia de proiectie π : Σ∗ → Syn(L) este morfism de

monoizi si consideram P = π(L). Avem evident L = π−1(P ). �Utilitatea monoidului sintactic este data de:

Cursul 3 17

Teorema 3.13 Urmatoarele afirmatii sunt echivalente:i) L este regulat.ii) Syn(L) este finit; adica σL are indice finit.iii) L este recunoscut de un monoid finit.

Definitia 3.14 i) Dat cuvantul w = x1...xn ∈ Σ∗ numim reversul saucuvantul wR = xn...x1. Se noteaza si Mi(w) din engleza: mirror = oglinda.ii) Un cuvant w ıl numim palindrom daca wR = w. Fie Pal(Σ) multimeaacestor cuvinte simetrice.iii) Dat limbajul L definim reversul sau limbajul LR = {wR;w ∈ L}.

Exemplul 3.15 Daca Σ are doua litere distincte a, b atunci {anban;n ∈N∗} ⊂ Pal(Σ).

Propozitia 3.16 i) (L1 + L2)R = LR

1 + LR2 , (L1L2)

R = LR2 L

R1 , (L

∗)R =(LR)∗.ii) L este regulat daca si numai daca LR este regulat.

Inainte de a parasi subiectul limbaje vom cita opiniile deosebit de in-teresante ale fizicianului Fritjof Capra din [1, p. 87-88]: ”... limbajul esteun sistem de comunicare simbolica. Simbolurile sale-cuvinte, gesturi si altesemne-servesc ca indicii pentru coordonarea lingvistica a actiunilor. Aceastala randul ei, creeaza notiunea de obiecte, si astfel simbolurile devin asociatecu imaginile noastre mentale ale obiectelor”. In aceeasi carte, la paginile92-94, este prezentat ASL-American Sign Language ca exemplu de limbajutilizat ın dialogul cu persoanele surde dar si cu cimpanzeii. La pagina 94ıncepe sectiunea Originile limbajului uman ce prezinta o foarte interesantateorie ce pune vorbirea ın conexiune cu miscarile mainilor ca fiind ”contro-late de aceeasi regiune motoare a creierului” (pag. 95). Citam de la pagina97: ”Aparitia cuvintelor ın comunicarea stramosilor nostri a adus avantajeimediate. Cei care comunicau vocal, o puteau face si cand aveau mainileocupate, sau cand interlocutorul era ıntors cu spatele. In cele din urma,aceste avantaje evolutive vor aduce schimbarile anatomice necesare vorbiriiarticulate desavarsite. Timp de zeci de mii de ani, pe masura evolutieitraiectului nostru vocal, oamenii au comunicat printr-o combinatie de ges-turi pecise si cuvinte vorbite pana cand, ın final, vorbirea a surclasat semnelesi a devenit forma dominanta de comunicare umana. Chiar si azi, folosimgesturile atunci cand limbajul vorbit nu ne serveste.”

Pagini Web utile:1) http://en.wikipedia.org/wiki/Regular language2) http://mathworld.wolfram.com/RegularExpression.html3) http://planetmath.org/encyclopedia/RegularLanguage.html

18 M. Crasmareanu

SEMINARUL 3

S3.1 Dati exemple de palindroame din limba romana.

Rezolvare 1) cu 3 litere: apa, ara, aba, ata, asa, bob, coc, ere, mim,rar, pop, sas, tot.2) cu 4 litere: ?.3) cu 5 litere: anina, caiac, capac, cojoc, etate, minim, soios, potop, reper,rotor, tivit. In DEX’98, exista ın jur de 35 de palindroame de 5 litere.4) 9 litere: aerisirea.5) 7 litere: rotitor, elevele, atacata, rotator, rolelor, atasata, Elenele, etajate,ala-bala, etalate, aerarea.

S3.2 Propozitii si expresii palindromice:ELE NE SEDUC CU DESENELE.ICRE, PUI, CIUPERCI.ELE FAC CAFELE.ENE PURTA PATRU PENE.O RAMA MARO.ERA O TIPA RAPITOARE !NOI VOTAM, MA, TOV. ION.

Dialoguri palindromice:- EREMIA, AI MERE?- O, N-AM, ANO!-ACU, DUDUCA!- IZA, CAZI ?- DA, CAD!- A... DA !

Scrisoare palindromica :DRAGA ILEANA, ACI M-A ATACAT RADA CU LUCA, DAR TAC. ATA AMICA, ANA-ELIA GARD.

S3.3 (Program C): Dat un numar nr se cer numarul sau de cifre,suma cifrelor sale, produsul cifrelor nenule, cifra de ordin k (cu k dat de latastatura) si inversatul sau.

//operatii cu cifrele unui numar#include<iostream.h>#include<math.h>void main(){

int n,k, nr, N=0, cifra, rasturnat=0;

Cursul 3 19

int suma=0, prod=1, cifrak;cout<<”dati numarul nr:= ”;cin>>nr;cout<<”dati ordinul cifrei k:= ”;cin>>k;n=nr;while (n!=0){cifra=n%10;N++;suma+=cifra;if (cifra!=0) prod*=cifra;if (N==k) cifrak=cifra;rasturnat=rasturnat*10+cifra;n=n/10;}

cout<<”numarul are:= ”<<N<<” cifre”<<endl;cout<<”suma cifrelor este:= ”<<suma<<endl;cout<<”produsul cifrelor nenule este:= ”<<prod<<endl;cout<<”cifra de ordin ”<<k<<” este:= ”<<cifrak<<endl;cout<<”numarul rasturnat este:= ”<<rasturnat<<endl;

}

Exemplu:Dati numarul nr:= 987654321 <Enter>Dati ordinul cifrei k:= 3 <Enter>numarul are:= 9 cifresuma cifrelor este:= 45produsul cifrelor nenule este:= 362880cifra de ordin 3 este:= 3numarul rasturnat este:= 123456789


S3.4 (Program C) Se da un numar natural N mai mare strict ca 2.Se cere afisarea unui sir de lungime N cu primele N/2 elemente ın ordinecrescatoare iar ultimele N/2 elemente ın ordine descrecatoare.

/*pentru N se cere un sir de lungime N cu primele N/2 elemente cresca-toare si urmatoarele elemente descrescatoare*/

#include<iostream.h>void main ()

20 M. Crasmareanu

{int N, i;cout<<”Dati N(>2):= ”;cin>>N;for (i=1;i<=N/2;i++)

cout<<i<<” ”;for (i=(N+N%2)/2;i;i–)

cout<<i<<” ”;cout<<endl;

}Exemplu: Pentru N=7 apare 1 2 3 4 3 2 1, iar pentru N=8 apare 1 2 3

4 4 3 2 1.


S3.5 In Matlab funtia strcat(s1, s2,s3, ...) concateneaza pe orizon-talaa sirurile s1, s2, s3, .... Spatiile finale ale sirurilor care se concateneazasunt ignorate.

>> s1=’elemente ’;>> s2=’de baza in ’;>> s3=’Matlab’;>> strcat(s1, s2, s3)ans =elementede baza inMatlab

Tot pentru concatenare se poate utiliza operatorul [ ]. De aceasta data,ın sirul rezultat avem spatiile libere de la capatul sirurilor s1 si s2:

>> [s1 s2 s3]ans =elemente de baza in Matlab

Functia strcvcat(t1, t2, t3, ...) concateneaza pe verticala sirurile t1,t2, t3, ... constituind un tablou de caractere:

>> t1=’abc’;>> t2=’def’;>> t3=’ghi’;>> strvcat(t1, t2, t3)ans =abcdefghi

Cursul 4

Varietati de monoizi

Fie monoidul M si congruentele Ci, i ∈ I pe M . Rezulta imediat ca C =∩i∈ICi este o congruenta peM . Fie acum R o relatie oarecare peM ganditaca submultime ın M ×M si sa observam ca exista congruente ce o includ,ın sensul incluziunii de multimi; spre exemplu congruenta totala M ×M .Aplicand argumentul anterior exista intersectia tuturor congruentelor cecontin pe R si s-o notam R♯ conform [8, p. 197]; rezulta ca R♯ este ceamai mica (ın sensul relatiei de ordine data de incluziunea submultimilor luiM ×M) congruenta ce contine pe R: daca C este o congruenta si R ⊂ Catunci R♯ ⊆ C.

Definitia 4.1 R♯ se numeste congruenta generata de R.

Sa ne amintim ca pentru limbaje regulate eram interesati de congruentede index finit; ın acest sens dam:

Propozitia 4.2 Dat alfabetul Σ si C o congruenta pe Σ∗ de index finitexista o submultime finita T a lui Σ∗×Σ∗ asa ıncat C = T ♯. Cu alte cuvinte,orice congruenta de index finit pe monoidul cuvintelor unui alfabet este detip ”sharp”.

Demonstratie Fie w ∈ Σ∗ si clasa sa de echivalenta [w] relativ la C.Definim l : Σ∗/C → N prin l([w]) = min{|z|; z ∈ [w]}. Cum C este de indexfinit exista mC = max{l([w]; [w] ∈ Σ∗/C)}; fie kC = mC + 1. Rezulta capentru orice [w] ∈ Σ∗/C exista z ∈ [w] cu |z| < kC ; ın caz contrar am aveal([w]) ≥ kC ≥ 1 + l([w]), fals. Fie T = {(u, v) ∈ Σ∗ × Σ∗; (u, v) ∈ C, |u| ≤kC , |v| ≤ kC} si fie R congruenta T ♯. Deoarece T ⊂ ∪kCi=0Σ

i rezulta ca Teste multime finita.

Avem din modul de definire, T ⊂ C si deci R ⊂ C. Mai ramane de aratatca C ⊂ R. Vom proceda prin reducere la absurd. Fie deci (u, v) ∈ C cu

21

22 M. Crasmareanu

(u, v) /∈ R. Putem presupune, eventual schimband ordinea datorita simetrieirelatiei de echivalenta C, ca |u| ≥ |v|; de asemeni, putem considera u si v asaıncat |u|+ |v| este cea mai mica posibila. Nu putem avea |u| < kC deoarecear rezulta si |v| < kC ceea ce spune ca (u, v) ∈ R. Fie deci |u| ≥ kC ;prin urmare u = zu′ cu |u′| = kC . Exista v′ ∈ [u′] cu |v′| < kC . Deci,(u′, v′) ∈ T ⊂ R ⊂ C. Din [v] = [u] = [zu′] si [zu′] = [zv′] rezulta printranzitivitate ca [v] = [zv′]. Daca am presupune ca (v, zv′) ∈ R ar rezultadin aceasta relatie si u = zu′, (zu′, zv′) ∈ R ca (u, v) ∈ R ceea ce contrazicepresupunerea de plecare.

Prin urmare, (v, zv′) ∈ C, (v, zv′) /∈ R si |v|+ |zv′| < |v|+ |zu′| = |u|+ |v|ceea ce contrazice ipoteza de minimalitate de la care am plecat. �

Definitie 4.3 O submultime nevida I a monoidului M se numeste idealdaca din a ∈ I si s ∈M oarecare rezulta as ∈ I si sa ∈ I.

Idealele sunt o sursa importanta de congruente. Astfel, dat idealul Idefinim relatia CI pe M prin (a, b) ∈ CI daca sau a = b sau a si b apartinsimultan lui I. Se verifica imediat ca CI este o congruenta pe M avanddrept clase de echivalenta multimile singleton {a} pentru a ∈M \I respectivmultimea I. Monoidul cat M/CI se noteaza M/I si regulile de calcul sunt:I) {a}{b} := {ab} daca ab /∈ I respectiv I ın caz contrar,II) {a}I = I{a} = II = Isi deci I este un ”zerou” al lui M/I. Prin urmare, putem gandi M/I cafiind format din M \ I si un zerou iar produsul a doua elemente nenule {a}si {b} este fie elementul nenul {ab} daca acesta nu apartine lui I, fie zerouldat. Acest tip de congruente se numesc congruente Rees iar monoidul catM/I ıl numim monoid Rees dupa numele celui care le-a introdus.

Definitia 4.4 O clasa V de monoizi o numim varietate daca este ınchisala considerarea submonoizilor, monoizilor cat si a produselor directe.

Prin urmare, V este o varietate daca:V1) odata cu M ∈ V si S submonoid al lui M avem ca S ∈ V ,V2) odata cu M ∈ V si C congruenta pe M avem ca M/C ∈ V ,V3) odata cu Mi ∈ V , i ∈ I avem ca

∏i∈I Mi ∈ V .

Exemple 4.5 Sunt varietati urmatoarele clase:i) Clasa Com a monoizilor comutativi,ii) Clasa Bm monozilor banda ın care fiecare element este idempotent.Prin contrast, clasa grupurilor nu este varietate; spre exemplu luam grupulciclic infinit M =< a > iar submonoidul puterilor pozitive {1, a, a2, ...} numai este grup.

Cursul 4 23

Deoarece din acelasi motiv al limbajelor regulate suntem interesati ınfinitudine, putem introduce si:

Definitia 4.6 O clasa V de monoizi finiti o numim F-varietate dacasatisface V1, V2 si:V3F) odata cu Mi ∈ V , i ∈ {1, 2} avem ca M1 ×M2 ∈ V .

Observatia 4.7 Este evident ca ın loc de V3F putem lucra cu:V3Fn) odata cu Mi ∈ V , i ∈ {1, ..., n} avem ca M1 × ... ×Mn ∈ V pentruorice n ≥ 2.

Exemple 4.8 Sunt F-varietati:i) clasa tuturor monoizilor finiti, ın particular clasa tuturor monoizilor finitidintr-o varietate V .ii) clasa tuturor grupurilor finite.iii) Fie o colectie nevida Vi, i ∈ I de F-varietati. Atunci ∩i∈IVi este o F-varietate.iv) Fie M = {Mj , j ∈ J} o colectie nevida de monoizi finiti si V intersectiatuturor F-varietatilor ce contine pe M . Aceasta intersectie exista deoareceputem considera F-varietatea tuturor monoizilor finiti. Conform iii) avemca V este F-varietate, cea mai mica ın sensul incluziunii ce contine pe M .Spunem ca V este generata de M si o mai notam B(Mj ; j ∈ J).

Definitia 4.9 Fie u, v ∈ Σ∗. Spunem ca monoidul M satisface ecuatiau = v daca pentru orice morfism de monoizi φ : Σ∗ →M avem φ(u) = φ(v).Mai putem spune ca u = v este ecuatia lui M .

Exemple 4.10 i) Ecuatia monoidului comutativ este xy = yx.ii) Ecuatia monoidului banda este x2 = x.

Daca avem un sir (finit sau infinit) (un, vn) de perechi de elemente dinΣ∗ atunci putem considera clasa C a tuturor monoizilor avand ecuatiileun = vn, n ≥ 1. Se arata imediat ca C este o varietate si o notam V (un =vn, n ≥ 1). Spre exemplu, Com = V (xy = yx) si Bm = V (x2 = x). In1935, Birkhoff a demonstrat rezultatul reciproc (mai dificil) si anume caorice varietate este definita de ecuatii.

Sa fixam F-varietatea V si alfabetul Σ. Fie LV (Σ) multimea limbajelorpeste Σ al caror monoid sintactic apartine lui V . Orice limbaj din LV (Σ)este regulat avand monoidul sintactic asociat finit. Un criteriu util de testarea apartenentei la LV (Σ) este dat de:

Propozitia 4.11 Fie limbajul L peste Σ. Atunci L apartine lui LV (Σ)daca si numai daca L este recunoscut de un monoid din V .

24 M. Crasmareanu

Avem si:

Propozitia 4.12 Fie V si W doua F-varietati de monoizi. Atunci V ⊆W daca si numai daca LV (Σ) ⊆ LW (Σ) pentru orice alfabet finit Σ.

Prin urmare avem:

Corolarul 4.13 Fie V si W doua F -varietati. Avem V = W daca sinumai daca LV (Σ) = LW (Σ) pentru orice alfabet finit Σ.

Definitia 4.14 i) O aplicatie L ce asociaza unui alfabet finit Σ osubmultime L (Σ) a limbajelor regulate peste Σ o numim RL-functie.ii) O RL-functie L o numim VRL-functie daca:1) pentru orice alfabet Σ multimea L (Σ) este ınchisa la reuniune si luareacomplementarei,2) date alfabetele Σi, i = 1, 2 si morfismul de monoizi φ : Σ∗

1 → Σ∗2 avem ca

L ∈ L (Σ2) implica φ−1(L) ∈ L (Σ1),3) pentru orice alfabet Σ, orice a ∈ Σ si orice L ∈ L (Σ) avem ca a−1L siLa−1 sunt ın L (Σ) unde, prin definitie, w ∈ Σ∗ este element ın a−1L dacaaw ∈ L.

Observatii 4.15 Conditia 1) de mai sus implica faptul ca L (Σ) esteınchisa la operatiile boolene de reuniune, intersectie si complementare. Conditia3) implica, prin calcul inductiv dupa lungimea cuvantului u ∈ Σ∗ ca u−1Lsi Lu−1 sunt multimi din L (Σ).

Aplicatia LV introdusa anterior este o RL-funtie. Avem mai mult:

Propozitia 4.16 Daca V este o F-varietate atunci aplicatia LV este oVRL-functie.

Avem si reciproca, datorata lui Eilenberg (1975):

Propozitia 4.17 Fie L o VRL-functie. Atunci exista o F-varietate demonoizi V asa ıncat L = LV .

Exemple 4.18 1) Daca Mon este F-varietatea tuturor monoizilor finitiatunci VRL-functia corespunzatoare asociaza alfabetului Σ multimea tu-turor limbajelor regulate peste Σ.2) Fie Triv F-varietatea monoizilor triviali, constand ın monoidul single-ton {1}. Atunci LTriv(Σ) contine limbajele L avand monoidul sintacticSyn(L) = {1}; prin urmare congruenta sintactica este congruenta totala.In concluzie, LTriv(Σ) = {∅,Σ∗}.

Un alt caz ın care VRL-functia poate fi explicitata este cand V estegenerata de un singur monoid:

Cursul 4 25

Propozitia 4.19 Fie V = B < M > F-varietatea generata de monoidulfinit M si fie alfabetul Σ. Atunci LV (Σ) este algebra booleana generata delimbajele φ−1(z) pentru orice z ∈ M si orice morfism de monoizi φ : Σ∗ →M .

Exemplul 4.20 Fie M = {0, 1} cu ınmultirea 0 · 0 = 0 · 1 = 1 · 0 =0, 1 · 1 = 1. Avem ca M satisface ecuatiile x2 = x, xy = yx si deci B(M)este inclusa ın F-varietatea V (x2 = x, xy = yx). In fapt, se poate arata chiaregalitatea acestor F-varietati iar ultima este numita F-varietatea monoizilorsemilaticeali notata SL.

Propozitia 4.21 Pentru alfabetul Σ avem ca LSL(Σ) este algebra boo-leana generata de limbajele A∗ unde A ⊆ Σ.

Pagini Web utile:1) http://en.wikipedia.org/wiki/Special classes of semigroups2) http://en.wikipedia.org/wiki/Boolean algebra (structure)3) http://en.wikipedia.org/wiki/Semigroup with two elements.

SEMINARUL 4

S4.1 (Lema de pompare Bar-Hillel) Fie L un limbaj regulat. Atunciexista numarul natural nenul n = nL asa ıncat orice cuvant w ∈ L cu |w| ≥ nadmite descompunerea w = xyz avand proprietatile:i) 0 < |y| ≤ n,ii) |xz| ≤ n,iii) pentru orice k ∈ N avem xykz ∈ L.

http://en.wikipedia.org/wiki/Pumping lemma for regular languages

S4.2 Folosind lema de pompare sa se arate ca urmatoarele limbaje nusunt regulate:1) L = {anbn;n ≥ 0},2) L = {an2

;n ≥ 0},3) L = {a10n ;n ≥ 0},4) L = {a2n ;n ≥ 1}.

Rezolvare 1) Vom contrazice lema de pompare. Fie w = anbn ∈ L cu2n ≥ nL unde nL este dat de lema. Avem trei situatii:I) x = al, y = am, z = an−l−mbn cu m > 0 din i). Fie i = 0 ın iii) din lema;rezulta an−mbn ∈ L fals.II) x = al, y = bn−lbm, z = bn−m cu n > l si m ≥ 0 din i). Avem 3 subcazuri:II1) n = l; rezulta m > 0. Cu i = 0 ın iii) avem ca anbn−m ∈ L, fals.

26 M. Crasmareanu

II2) n > l si m = 0. Cu i = 0 avem albn ∈ L, fals.II3) n > l si m > 0. Cu i = 2 avem alan−lbman−lbmbn−m ∈ L, fals deoarecesimbolul a trebuie sa fie ınaintea lui b.III) x = anbm, y = bl, z = bn−l−m cu l > 0. Luam i = 0 si avem anbn−l ∈ Lfals.

S4.3 X ⊂ N se numete periodica daca este finita sau exista N0 ≤ 0 sip ≤ 1 asa ıncat daca x ≤ N0 atunci x ∈ X daca si numai daca x+ p ∈ X.1) Daca X este periodica sa se arate ca X = A ∪ B unde A = X ∩ {i; 0 ≤i < N0} iar B = ∪sj=1{g(j) + pi; i ≤ 0} iar g(1), ..., g(s) = X ∩ {i;N0 ≤ i <N0 + p}.2) L = {a}∗ este regulat daca si numai daca multimea X = {i; ai ∈ L} esteperiodica.

Pentru a compara ıntre ele siruri de caractere, se pot folosi operatorirelationali sau functii predefinite ın Matlab. Operatorii relationali (>,>=, <,<=,==,∼=) compara valorile corespunzatoare caracterelor din sir, com-paratia realizandu-se element cu element. De exemplu:

>> A=’abcd’;>> B=’xbyd’;>> A==Bans =0 1 0 1

Valoarea 1 reprezinta true iar 0 reprezinta false. Astfel, valorile 1 aratalocurile unde simbolul este acelasi iar 0 indica locurile cu elemente diferite.Avem si varianta:

>> B>Aans =1 0 1 0

Latici

Definitia 4.4 Fie L o multime nevida ınzestrata cu doua legi de compozitie∨ (”sau”), ∧ (”si”) : L × L → L. Tripletul (L,∨,∧) ıl numim latice dacasunt satisfacute proprietatile:L1) (comutativitate) a ∨ b = b ∨ a, a ∧ b = b ∧ a,L2) (asociativitate) (a ∨ b) ∨ c = a ∨ (b ∨ c), (a ∧ b) ∧ c = a ∧ (b ∧ c),L3) (absorbtie) a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a.

Exemplul 4.5 Fie multimea nevida A. Avem ca (L = P(A),∪,∩) esteo latice. Invitam cititorul sa verifice absorbtia: pentru X,Y ∈ P(A) avemX ∪ (X ∩ Y ) = X si X ∩ (X ∪ Y ) = X.

Cursul 4 27

Proprietatea 4.6 Fie laticea L si a ∈ L. Are loc proprietatea deidempotenta: a ∨ a = a and a ∧ a = a.

Demonstratie a ∨ a = a ∨ [a ∧ (a ∨ b)] = a ∨ (a ∧ x) = (L3) a. Analogpentru a doua identitate. �

Definitia 4.7 Fie laticea L si L′ ⊂ L nevida. Spunem ca L′ este sublaticeın L daca pentru orice x, y ∈ L′ avem ca x ∨ y ∈ L′ si x ∧ y ∈ L′.

Exemple 4.8 i) Fie B ⊂ A nevida. Atunci P(B) este sublatice ınP(A).ii) Fie L = N∗ cu operatiile a ∨ b = [a, b]=cel mai mic multiplu comun alnumerelor a si b, a ∧ b = (a, b)=cel mai mare divizor comun al numerelordate. Avem ca (L,∨,∧) este o latice.Fie numerele prime distincte p si q. Atunci L′ = {1, p, q, pq} este o sublaticeın N∗.

Definitia 4.9 Numim semilatice o multime nevida M ınzestrata cu ooperatie interna ∗ satisfacand:SL1) (a ∗ b) ∗ c = a ∗ (b ∗ c),SL2) a ∗ b = b ∗ a,SL3) a ∗ a = a.Deci (M, ∗) este un semigrup comutativ ın care orice element este idempo-tent.

Exemple 4.10 Daca (L,∨,∧) este o latice atunci (L,∨) si (L,∧) suntsemilatice. Este posibil ca aceste exemple sa fi sugerat denumirea.

Observatia 4.11 Pe laticea L definim relatia a ≤ b daca a ∨ b = b.Avem imediat ca ≤ este o relatie de ordine pe L. De asemeni, avem a ≤ bdaca si numai daca a ∧ b = a.

Definitia 4.12 i) Laticea L se numeste marginita daca exista un cel maimic element, notat 0, si exista un cel mai mare element, noatt 1.ii) Daca L este marginita si x ∈ L spunem ca x ∈ L este complementul luix daca x ∨ x = 1 si x ∧ x = 0.

Observatia 4.13 Avem 0 = 1 si 1 = 0 dar nu orice element dintr-olatice marginita admite complement !

Definitia 4.14 Laticea marginita (L,∨,∧, 0, 1) se numeste complemen-tata daca orice a ∈ L admite complement unic.

Defnitia 4.15 Laticea L se numeste distributiva daca au loc proprietatilede distributivitate:

28 M. Crasmareanu

D1) (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c),D2) (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c).

Definitia 4.16 O latice (L,∨,∧, 0, 1, ) complementata si distributiva senumeste algebra Boole sau latice booleana.

Cursul 5

Automate

Desi ın literatura de specialitate exista o multitudine de tipuri de automate,notiunea utilizata ın acest curs este urmatoarea:

Definitia 5.1 Numim automat un 5-uplu A = (Q,Σ, q0, δ, F ) unde Q siΣ sunt multimi nevide si finite, q0 ∈ Q, F ⊆ Q nevida iar δ este o functie:δ : Q× (Σ ∪ {ε})→P(Q). Denumiri:-Q=multimea starilor,-Σ=alfabetul de intrare; un element din Σ se mai numeste input,-q0=starea initiala,-δ=functia de tranzitie,-F=multimea starilor finale sau terminale.

Observatii 5.2 i) Datorita caracterului finit al multimilor implicate,uneori se precizeaza ın denumire ca A este un automat finit (AF).ii) Notiunea introdusa mai poate fi ıntalnita si cu numele de automat nedeter-minist cu ε-tranzitii. Particularizari ale lui δ conduc la notiunea de automatdeterminist (fara ε-tranzitii) respectiv automat determinist. Astfel avem:

Definitia 5.3 I) Automatul A se numeste:i) nedeterminist (AFN) daca δ(q, ε) = ∅ pentru orice q ∈ Q,ii) determinist (AFD) daca satisface conditia precedenta plus conditia |δ(q, x)| =1, pentru orice q ∈ Q si x ∈ Σ. In continuare, vom considera ın principalAFD-uri (a se vedea cursul urmator) si deci functia de tranzitie se consideraδ : Q×(Σ∪{ε})→ Q deoarece daca δ(q, x) = {q′} notam simplu δ(q, x) = q′.II) Data starea q ∈ Q numim ınchiderea lui q multimea:

Cl(q) = {q}+ ∪k∈N∗{qk+1 ∈ Q; q2 ∈ δ(q1 = q, ε), ..., qk+1 ∈ δ(qk, ε)}.

Pentru Q′ ⊆ Q definim: Cl(Q′) = ∪q∈Q′Cl(q) si δ(Q′, x) = ∪q∈Q′δ(q, x).

29

30 M. Crasmareanu

O notiune extem de importanta ın ceea ce urmeaza este:

Definitia 5.4 Extinderea functiei de tranzitie la cuvinte este:δe : Q× Σ∗ →P(Q),i) δe(q, ε) = Cl(q),ii) δe(q, wx) = Cl(δ(δe(q, w)), x), daca w ∈ Σ∗ si x ∈ Σ.

Observatia 5.6 i) Pentru un AFD avem Cl(q) = {q} si deci δe(q, x) =Cl(δ(q, x)) = δ(q, x) deoarece δ(q, x) are cardinalul 1. De aceea ın multereferinte bibliografice atunci cand se lucreaza cu AFD-uri se pastreaza (dinmotive de simplitate) notatia δ si pentru functia extinsa !ii) Un calcul inductiv imediat (dupa lungimea celui de al doilea cuvant) daegalitatea: δe(q, w1w2) = δe(δe(q, w1), w2). Rezulta ca pentru un AFD sicuvantul w = x1...xn avem:

δe(q, w) = δ(...(δ(q, x1), x2), ...xn).

Exprimam astfel: cand automatul aflat ın starea q primeste cuvantul w eltrece ın starea δe(q, w). Daca δe(q, w) = ∅ spunem ca automatul trece ıntr-ostare nedefinita iar daca |δe(q, w)| ≥ 2 spunem ca automatul trece ıntr-ostare ambigua.

Cea mai importanta notiune din teoria automatelor este:

Definitia 5.7 Limbajul acceptat sau recunoscut de automatul A este:L(A) = {w ∈ Σ∗; δe(q0, w) ∩ F = ∅}. Prin urmare, pentru un AFD avem:

L(A) = {w ∈ Σ∗; δe(q0, w) ∈ F}.

Un element din L(A) se numeste cuvant recunoscut de A.Din acest motiv notiunea de AFD se mai utilizeaza cu denumirea de

automat de acceptare. Exista o legatura profunda ıntre expresiile regulatesi limbajele acceptate de automate:

Teorema 5.8 Daca E este o expresie regulata peste Σ i.e. E ∈ Rex(Σ)atunci exista un automat finit cu ε-tranzitii peste alfabetul Σ astfel ıncatK(E) = L(A).

Definitia 5.9 Limbajul L peste Σ se numeste recognoscibil daca existaunautomat A cu alfabetul Σ asa ıncat L = L(A).

Exemple 5.10 i) Daca Σ = B = {0, 1} atunci L = B∗ \ B∗010B∗ esterecognoscibil conform Ex. 5.3.ii) L = {0n1n;n ≥ 1} nu este recognoscibil.

Reprezentari ale automatelor finite

Cursul 5 31

Putem reprezenta un AF ın doua moduri: tabelar si grafic. Din motivede simplitate vom alege doar primul mod desi uneori este preferat al doileamod datorita avantajului vizual: w ∈ Σ∗ este recunoscut (acceptat) de Adaca si numai daca ın graful lui A exista un drum de la starea initiala q0 lao stare finala q′ ∈ F , acest drum avand arcele etichetate succesiv cu literelecuvantului w. Se spune ca w este eticheta (engleza label) drumului de la q0la q′.

Astfel daca Q = {q0, ..., qn} si Σ = {x1, ..., xm} vom considera un tabelcu n+ 2 linii si m+ 1 coloane de tipul:

Q \ Σ x1 ... xj ... xm→ q0...

qi ← δ(qi, xj)

qn

unde sageata → marcheaza starea initiala iar ← stari finale.

Exemplul 5.11 Fie AF-ul cu Q = {a, b, c}, q0 = a, F = {c},Σ = {0, 1}si:δ(a, 0) = {b}, δ(a, 1) = {a, b}, δ(b, 0) = {c}, δ(b, 1) = {a}, δ(c, 0) = {c}, δ(c, 1) ={b, c}. Avem:

0 1

→ a b {a, b}b c a

c← c {b, c}

.

Fie w1 = 100100 si w2 = 0101. Avem:i) δe(a,w1) = δe(δ(a, 1), 0010) = δe(b, 0010) = δe(δ(b, 0), 010) = δe(c, 010) =δe(δ(c, 0), 10) = δe(c, 10) = δ(δ(c, 1), 0) = δ({b, c}, 0) = {δ(b, 0), δ(c, 0)} ={c, c} ∩ {c} = ∅ii) δe(a,w2) = δe(δ(a, 0), 101) = δe(b, 101) = δe(δ(b, 1), 01) = δe(a, 01) =δ(δ(a, 0), 1) = δ(b, 1) = {a} ∩ {c} = ∅.In concluzie, w1 ∈ L(A) si w2 ∈ L(A). Mai general, (01)+ ⊂ L(A).

Pagini Web utile:1) http://en.wikipedia.org/wiki/Automata theory2) http://mathworld.wolfram.com/AutomataTheory.html

SEMINARUL 5

32 M. Crasmareanu

S5.1 Fie automatul nedeterminist:

0 1

→ q0 q1 q0q1 q2 q0q2 q2 {q2, q3}q3 ← ∅ ∅

.

Sa se studieze cuvintele w1 = 11001, w2 = 1n001m cu n ≥ 1,m ≥ 2 siw3 = 0n, n ≥ 3.

Rezolvare w1 ∈ L(A) deoarece δe(q0, w1) = {q2, q3}, w2 ∈ L(A) deoareceδe(q0, w2) = {q2, q3} dar w3 ∈ L(A) deoarece δe(q0, w3) = q2 = q3.

S5.2 Fie AFD-ul:0 1

→ q0 q0 q1q1 ← q0 q2q2 ← q1 q0

.

Sa se studieze cuvintele w1 = 0011 si w2 = 0111.

RezolvareDeoarece δe(q0, w1) = q2 avem ca w1 ∈ L(A) iar din δe(q0, w2) =q0 avem ca w2 ∈ L(A).

S5.3 Fie AFD-ul:0 1

q0 q0 q0→ q1 ← q2 q1q2 ← q2 q3q3 ← q0 q1

.

i) Sa se studieze w1 = 12031204 si w2 = 1203104.ii) Sa se arate ca w = ...010... ∈ L(A).iii) Sa se deduca faptul ca L(A) = {0, 1}∗ \ {0, 1}∗010{0, 1}∗.

Rezolvare i) δe(q1, w1) = q2 ∈ F deci w1 ∈ L(A); δe(q1, w2) = q0 ∈ Fdeci w2 ∈ L(A).ii) δe(q1, ...010...) = q0 deoarece la aplicarea secventei 010 avem:1) q0 → q0 → q0 → q0,2) q1 → q2 → q3 → q0,3) q2 → q2 → q3 → q0,4) q3 → q0 → q0 → q0.

Cursul 6

Automate echivalente

Deoarece aspectul cel mai important ın functionarea unui automat ıl reprezintalimbajul acceptat este naturala :

Definitia 6.1 Automatele A,A′ peste acelasi alfabet se numesc echiva-lente si notam A ∼ A′ daca L(A) = L(A′).

Cum egalitatea multimilor este o relatie de echivalenta avem:

Propozitia 6.2 Relatia ∼ este o relatie de echivalenta pe multimea au-tomatelor cu alfabetul Σ fixat.

Prin urmare suntem interesati de gasirea unor reprezentanti remarca-bili ai unei clase de echivalenta date; acest aspect motiveaza urmatoareleteoreme de reducere. Astfel, un prim rezultat este legat de eliminarea ε-tranzitiilor:

Teorema 6.3 Dat automatul A cu ε-tranzitii exista A′ fara ε-tranzitiisi echivalent cu A.

La fel de important este rezultatul urmator ce releva o egalitate AFN=AFDdin punctul de vedere al limbajelor acceptate:

Teorema 6.4 Dat AFN-ul A exista un AFD Ad echivalent cu A.Demonstratie PresupunemA = (Q,Σ, δ, q0, F ) si fieAd = (Qd,Σ, δd, Q0, Fd):

i) Qd = P(Q), Q0 = {q0}, Fd = {Z ∈ Qd;Z ∩ F = ∅},ii) δd : Qd × (Σ ∪ {ε})→ Qd este:ii1) δd(∅, x) = ∅, δ(Z, ε) = ∅ pentru Z ∈ Qd nevida si x ∈ Σ,ii2) δd(Z, x) = {δ(q, x); q ∈ Z}.Avem ca Ad este AFD deoarece δd(Z, x) are un singur element (=o multime)privit ca element ın Qd.1) L(A) ⊆ L(Ad)

33

34 M. Crasmareanu

Fie w ∈ L(A); deci Z = δ(q0, w) ∩ F = ∅ i.e. Z ∈ Fd si avem δd(Q0, w) =Z ∈ Fd ceea ce spune ca w ∈ L(Ad).2) L(Ad) ⊆ L(A)Fie w ∈ L(Ad); deci δd(Q0, w) ∈ Fd i.e. {δ(q0, w)} ∩ F = ∅ ceea ce spune caw ∈ L(A). �

Exemplul 6.5 Fie A cu Q = {q0, q1, q2}, Σ = {0, 1}, F = {q2} si functiade tranzitie data de tabelul:

0 1

→ q0 q1 {q0, q1}q1 q2 q0q2 ← q2 {q1, q2}

.

Avem Qd = {Q1, Q2 = Q0, Q3, Q4, Q5, Q6, Q7, Q8 = Q} cu Q1 = ∅, Q3 ={q1}, Q4 = {q2}, Q5 = {q0, q1} = Q2 + Q3, Q6 = {q0, q2} = Q2 + Q4,Q7 = {q1, q2} = Q3 +Q4 si:-δd(Q1, 0) = Q1, δd(Q1, 1) = Q1,-δd(Q2, 0) = Q3, δd(Q2, 1) = Q5,-δd(Q3, 0) = Q4, δd(Q3, 1) = Q2,-δd(Q4, 0) = Q4, δd(Q4, 1) = Q7,-δd(Q5, 0) = δd(Q2, 0) + δd(Q3, 0) = Q3 +Q4 = Q7, δd(Q5, 1) = δd(Q2, 1) +δd(Q3, 1) = Q5 +Q2 = Q8,-δd(Q6, 0) = δd(Q2, 0) + δd(Q4, 0) = Q3 +Q4 = Q7, δd(Q6, 1) = δd(Q2, 1) +δd(Q4, 1) = Q5 +Q7 = Q8,-δd(Q7, 0) = δd(Q3, 0) + δd(Q4, 0) = Q4 +Q4 = Q4, δd(Q7, 1) = δd(Q3, 1) +δd(Q4, 1) = Q2 +Q7 = Q8,-δd(Q8, 0) = δd(Q2, 0) + δd(Q7, 0) = Q3 +Q4 = Q7, δd(Q8, 1) = δd(Q2, 1) +δd(Q7, 1) = Q5 +Q8 = Q8.Avem Fd = {Q4, Q6, Q7, Q8} si deci tabelul lui Ad este:

0 1

Q1 Q1 Q1

→ Q2 Q3 Q5

Q3 Q4 Q2

Q4 ← Q4 Q7

Q5 Q7 Q8

Q6 ← Q7 Q8

Q7 ← Q4 Q8

Q8 ← Q7 Q8

Cursul 6 35

Definitia 6.6 Dat automatul A spunem ca starea q ∈ Q este accesibiladaca exista w ∈ Σ∗ asa ıncat δe(q0, w) = q.

Observatia 6.7 Daca ın definitia precedenta am lua w ∈ L(A) ar rezultaq ∈ F . Dar asta nu ınseamna ca orice stare finala este accesibila !

Teorema 6.8 Dat A exista Aac cu toate starile accesibile si echivalentcu A.

Demonstratie Definim Aac = (Qac = {Q0, ..., Qr+1},Σ, δac, Q0, Fac)astfel:i)Qac va fi constituita din anumite submultimi ale multimii starilor accesibileale lui A i.e. {q ∈ Q;∃w ∈ Σ∗, δe(q0, w) = q}, Q0 = {q0}, Fac = {Qj ∈Qac;Qj ∩ F = ∅},ii) δac se determina prin recurenta astfel:Pasul 1. Notam Σ = {0, ..., n− 1},Pasul 2. Pentru i ∈ Σ definim δac(Q0, i) = {δ(q0, i)} = Qi+1. Obtinemastfel n multimi ce pot coincide cu Q0 sau ıntre ele; cele diferite le retinemsi le notam Q1, ..., Qj .Pasul 3. Pentru i ∈ Σ definim δac(S, i) = {δ(q, i); q ∈ S} = Qj+i+1 cuS ∈ {Q1, ..., Qj}; din nou avem n multimi ce pot coincide cu Q0, ..., Qj sauıntre ele; cele diferite le renumerotam Qj+1, ..., Qj+k.

Continuam acest procedeu pana cand nu mai obtinem multimi noi; deciam gasit r ≥ 1 asa ıncat Qr+1 ∈ {Q0, ..., Qr} dar Qr+s = Qr+1 pentru orices ≥ 2. Atunci Qac = {Q0, ..., Qr+1}. �

Exemplul 6.9 Fie A cu Q = {q0, q1, q2}, Σ = {0, 1}, F = {q2} si functiade tranzitie data de tabelul:

0 1

→ q0 q1 q2q1 {q1, q2} q1q2 ← q2 {q1, q2}

.

Avem deci:Pasul 1. Observam ca multimea starilor accesibile este tot Q deoareceδe(q0, ε) = q0, δ(q0, 0) = q1, δ(q0, 1) = q1.Pasul 2. δac(Q0, 0) = δ(q0, 0) = {q1} = Q1, δac(Q0, 1) = δ(q0, 1) = {q2} =Q2. Retinem Q1 si Q2.Pasul 3. δac(Q1, 0) = δ(q1, 0) = {q1, q2} = Q3, δac(Q1, 1) = δ(q1, 1) ={q1} = Q1,δac(Q2, 0) = δ(q2, 0) = {q2} = Q2, δac(Q2, 1) = δ(Q2, 1) = δ(q2, 1) ={q1, q2} = Q3. Deci retinem Q3.

36 M. Crasmareanu

Pasul 4. δac(Q3, 0) = δ(q1, 0) + δ(q2, 0) = {q1, q2}+ {q2} = {q1, q2} = Q3,δac(Q3, 1) = δ(q1, 1) + δ(q2, 1) = {q1}+ {q1, q2} = {q1, q2} = Q3.In concluzie, Qac = {Q0, Q1, Q2, Q3}, F3 = {Q2, Q3} si avem tabelul pentruδac:

0 1

→ Q0 Q1 Q2

Q1 Q3 Q1

Q2 ← Q2 Q3

Q3 ← Q3 Q3

.

Avem δac,e(Q0, ε) = Q0, δac(Q0, 0) = Q1, δac(Q0, 1) = Q2, δac,e(Q0, 00) =Q3 ceea ce spune ca toate starile sunt accesibile.

Definitia 6.10 i) Dat AFD-ul A starea q ∈ Q o numim productiva (saucoaccesibila) daca exista w ∈ Σ∗ asa ıncat δe(q, w) ∈ F .ii) Un automat cu toate starile accesibile si productive se numeste trim.

Observatia 6.11Din definitie avem ca q0 este productiva daca L(A) = ∅deoarece luam orice w ∈ L(A).

Teorema 6.11 Dat AFD-ul A exista un AFD Ap cu toate starile pro-ductive si echivalent cu A.

Demonstratie Construim Ap = (Qp = {Q1, ..., Qr+1},Σ, δp, Q0, Fp) cuQ0 = {q0} si procedand analog cu demonstratia anterioara luand Q1 = F siFp = {Qj ∈ Qp;Qj ∩ F = ∅}. �

SEMINARUL 6

S6.1 Sa se studieze AFD-ul cu |Q| = |Σ| = 1.

Rezolvare Avem Q = {q0} = F , Σ = {0} si δ : Q×Σ→ Q, δ(q0, 0) = q0.Rezulta L(A) = {0}∗. Reprezentarea tabelara:

0

→ q0 ← q0.

Observatie Un AFD cu |Σ| = 1 se numeste autonom.

S6.2 Sa se studieze AFD-ul cu |Q| = 1 si |Σ| = 2. Generalizare.

Rezolvare Avem Q si F ca mai sus iar Σ = {0, 1}. Evident δ(q0, 0) =δ(q0, 1) = q0 si deci L(A) = {0, 1}∗. Reprezentarea tabelara:

0 1

→ q0 ← q0 q0.

Cursul 6 37

Generalizare: Q = {q0} = F , Σ = {0, ..., n} si δ(q0, i) = q0, 1 ≤ i ≤ n.Avem L(A) = {0, ..., n}∗. Evident, acest automat este un trim.

S6.3 Sa se studieze AFD-ul cu |Q| = 2 si |Σ| = 1.

Rezolvare Fie Q = {q0, q1} si Σ = {0}.I)

δ 0

→ q0 q0q1 q0

.

a) F = {q0}; avem L(A) = {0}∗.b) F = {q0, q1}; avem L(A) = {0}∗.c) F = {q1}; avem L(A) = ∅.II)

δ 0

→ q0 q1q1 q1

.

a) F = {q0}; avem L(A) = ∅.b) F = {q0, q1}; avem L(A) = {0}∗.c) F = {q1}; avem L(A) = {0}∗.III)

δ 0

→ q0 q0q1 q1

.

a) F = {q0}; avem L(A) = {0}∗.b) F = {q0, q1}; avem L(A) = {0}∗.c) F = {q1}; avem L(A) = ∅.IV)

δ 0

→ q0 q1q1 q0

.

a) F = {q0}; avem L(A) = {02n;n ∈ N∗}.b) F = {q0, q1}; avem L(A) = {0}∗.c) F = {q1}; avem L(A) = {02n+1;n ∈ N∗}.

Automatul III se poate identifica cu permutarea identica π1 =

(0 10 1

)iar automatul IV cu permutarea ”twist” π2 =

(0 11 0

).

38 M. Crasmareanu

S6.4 Automatul ciclic C (p, r).

Rezolvare Fie Q = {q0, ..., qr+p−1} si Σ = {0}. Consideram functia detranzitie:

δ 0

→ q0 q1...

...

qr−1 qr...

...

qr+p−2 qr+p−1

qr+p−1 qr

.

Daca automatul paraseste una din starile q0, ..., qr−1 el nu se mai ıntoarceniciodata ın acea stare; le putem numi fara ıntoarcere. Ciclul de stariqr, ..., gr+p−1 se poate numi ciclul fara evadare, ın engleza no escape.

S6.5 Sa se studieze AFD-ul cu Q = {q0, q1}, Σ = {0, 1}, F = {q0} sifunctia:

δ 0 1

→ q0 ← q0 q1q1 q1 q1

.

Rezolvare L(A) = {0}∗.

S6.6 Sa se studieze AFD-ul cu Q = {q0, q1, q2}, F = {q1}, Σ = {0, 1} sifunctia:

δ 0 1

→ q0 q1 q2q1 ← q1 q2q2 q2 q2

.

Rezolvare L(A) = {0}+(= {0}∗ · {0} = {0} · {0}∗).

Cursul 7

Automat minimal

Am vazut ın cursul precedent ca pretul platit pentru adaugarea anumitorproprietati (convenabile) unui automat se reflecta ın cresterea, uneori foartemare (rapida), a numarului de stari. Este astfel naturala ıntrebarea dacaputem lucra cu anumite conditii de minimalitate.

Definitia 7.1 Fie A un AFD.i) Dat numarul natural k definim relatia =k pe Q prin: q1 =k q2 daca pentruorice w ∈ ∪ki=0Σ

i avem δe(q1, w) ∈ F daca si numai daca δe(q2, w) ∈ F .Spunem ca starile q1 si q2 sunt k-echivalente.ii) Definim relatia ≡ pe Q prin: q1 ≡ q2 daca q1 =k q2 pentru orice k ∈ N.Vom spune ca q1 si q2 sunt echivalente.

Reamintim ca apartenenta unui element la o multime se studiaza cuajutorul unei functii:

Definitia 7.2 Data multimea nevida X si submultimea sa Y definimfunctia caracteristica a lui Y functia χY : X → {0, 1} data de:i) χY (x) = 1 daca x ∈ Y , ii) χY (x) = 0 altfel.Exista autori care fac alegerea inversa: χY (x) = 0 daca x ∈ Y ([15, p. 84])dar ın literatura clasica (romaneasca) avem alegerea de mai sus.

Prin urmare, q1 =k q2 daca si numai daca χF (δe(q1, w)) = χF (δe(q2, w))pentru orice w ∈ Σ0 + ... + Σk. Astfel, obtinem ca q1 =0 q2 daca si numaidaca q1, q2 apartin simultan lui F sau Q \ F . O caracterizare pentru =k cuk ≥ 1 este:

Propozitia 7.3 q1 =k q2 daca si numai daca q1 =k−1 q2 si δ(q1, x) =k−1

δ(q2, x) pentru orice x ∈ Σ \ {ε}.

Deoarece relatia de egalitate este o echivalenta avem:

39

40 M. Crasmareanu

Propozitia 7.4 Relatiile =k si ≡ sunt echivalente pe Q.

Notam atunci Qm si Fm multimile cat determinate de ≡ pe Q respectivF . Definim δm : Qm × Σ∗ → Qm prin δm([q], w) = [δe(q, w)]. Se verificaimediat buna definire a acestei aplicatii.

Notiunea centrala a acestui curs este:

Definitia 7.5 AFD-ul A se numeste minimal daca pentru orice AFD A′

echivalent cu A avem |Q| ≤ |Q′|. In particular, automatul cu o singura stareeste minimal.

Avem deci Problema:Input: A AFD,Output: A′ AFD minimal si echivalent cu A.

Trebuie subliniat ca automatul minimal este unic pana la un izomorfism:

Definitia 7.6 AFD-urile A,A′ cu aceeasi Σ se numesc izomorfe dacaexista o bijectie h : Q→ Q′ asa ıncat: q′0 = h(q0), F

′ = h(F ) si h(δ(q, x)) =δ′(h(q), x) pentru orice q ∈ Q si orice x ∈ Σ i.e. urmatoarea diagrama estecomutativa:

Q× Σ δ → Q↓ h ↓ hQ′ × Σ δ′ → Q′

.

Rezulta imediat ca:1) h(δe(q, w)) = δ′e(h(q), w) pentru orice w ∈ Σ∗,2) L(A) = L(A′) si deci A,A′ sunt echivalente. Putem spune ca un izomor-fism realizeaza ın fapt, o ”recontorizare” a starilor.

In determinarea automatului minimal de un mare folos este rezultatulurmator:

Propozitia 7.7 i) Fie q1, q2 ∈ Q pentru |Q| = n. Atunci q1 ≡ q2 dacasi numai daca q1 =n−2 q2.ii) Daca Qm este ın bijectie cu Q atunci automatul A este minimal.

Unul din rezultatele centrale ale acestui curs este:

Teorema 7.8 Dat AFD-ul A avem ca Am = (Qm,Σ, δm, [q0], Fm) esteautomat minimal echivalent cu A.

Definitia 7.9 i) Daca ın definitia automatului retinem primele trei ele-mente SA = (Q,Σ, δ) atunci obtinem notiunea de semiautomat.ii) Un semiautomat (automat) se numeste conex daca orice doua stari se potuni i.e. oricare ar fi q1, q2 ∈ Q exista w ∈ Σ∗ asa ıncat δe(q1, w) = q2.

Cursul 7 41

iii) Un semiautomat (automat) se numeste perfect daca este conex si satisfaceδe(q, w1w2) = δe(q, w2w1) pentru orice q ∈ Q si w1, w2 ∈ Σ∗.

Observatii 7.101) Daca automatul A este conex atunci orice stare q ∈ Q este accesibila.2) Daca automatul A este conex atunci orice stare q ∈ Q este productiva; ınadevar, fixam qf ∈ F si din conexitate va exista w ∈ Σ∗ asa ıncat δe(q, w) =qf ∈ F .3) Din 1) si 2) rezulta ca un automat conex este un trim.

Definitia 7.11 O congruenta pe (semi)automatul A este o relatie deechivalenta ∼ pe Q cu proprietatea ca q1 ∼ q2 implica δ(q1, x) ∼ δ(q2, x)pentru orice x ∈ Σ. Rezulta ca δe(q1, w) ∼ δe(q2, w) pentru orice w ∈ Σ∗.

Pagini Web utile:1) http://planetmath.org/encyclopedia/Minimal2.html

SEMINARUL 7

S7.1 Semiautomatul grup si automatul grup.

Rezolvare Fie grupul finit G si semiautomatul SAG = (G,G, δ) cuδ data de multiplicarea ın G. Avem ca SAG este conex si daca G estecomutativ atunci SAG este perfect. Dat q0 ∈ G si F ⊂ G avem automatulAG = (SAG, q0, F ) care are toate starile accesibile si productive; deci AG

este trim.

S7.2 Sumatorul modulo n.

Rezolvare Fie n numar natural nenul. Semiautomatul numit astfel esteSAn = (N<n = {0, ..., n− 1},N<n, δ) cu δ(q, x) = q + x(mod n).

S7.3 Se cere un semiautomat care sa recunoasca constantele zecimalefara semn pornind dintr-o stare initiala START.

Rezolvare Fie Q = {q0, q1, q2, q3, q4} unde: q0=START, q1=constantaıntreaga, q2=constanta ıntreaga cu punct zecimal, q3=constanta cu partefractionara, q4=eroare. Fie Σ={.,0,...,9} si δ data de:1) δ(q0, .) = δ(q1, .) = q2, δ(q2, .) = δ(q3, .) = δ(q4, .) = δ(q4, i) = q4,2) δ(q0, i) = δ(q1, i) = q2, δ(q2, i) = δ(q3, i) = q3unde i ∈ N<9.

S7.4 Fie SAn sumatorul modulo n.i) O partitie pe N<n este o congruenta pe Sn daca si numai daca este de

42 M. Crasmareanu

tipul urmator: exista d ≥ 2 un divizor al lui n asa ıncat partitia este de tipRd adica are d clase cu acelasi numar de elemente si ordonand elementeleunei clase crescator avem ca diferenta dintre doua elemente consecutive ested.ii) Fie d1, d2 ≥ 2 divizori ai lui n; daca d1|d2 atunci Rd2 ⊆ Rd1 .

S7.5 Fie automatul A peste alfabetul binar cu Q = {q0, q1, q2, q3} si:

δ 0 1

→ q0 q1 q2q1 ← q3 q1q2 ← q2 q3q3 q3 q3

Se cere L(A).

Rezolvare Avem L(A) = {01n;n ∈ N}+ {10n;n ∈ N}.

S7.6 Fie automatul avand Q = {q0, ..., qn}, Σ = {1, ..., n} si:

δ 1 2 ... n

→ q0 q1q1 q2...

qn−1 qnqn ←

unde ın locurile necompletate apare multimea vida. Se cere L(A).

Rezolvare L(A) = {w = 12...n}.

S7.7 Se da automatul cu Q = {q0} = F , Σ = {1, ..., n} si:

δ 1 . . . n

→ q0 ← ∅ . . . ∅

si se cere L(A).

Rezolvare L(A) = {ε}.

S7.8 Dat alfabetul binar se cere un automat care sa recunoasca limbajulL(A) = {(01)n;n ∈ N}.

Cursul 7 43

Rezolvare Fie Q = {q0, q1, q2} si:

δ 0 1

→ q0 ← q1 ∅q1 ∅ q2q2 ← q1 ∅

.

S7.9 Dat alfabetul Σ multimea L ⊆ Σ∗ o numim recognoscibila dacaexista un automat A peste Σ asa ıncat L(A) = L. Sa se arate ca multimilesingleton sunt recognoscibile.

Rezolvare i) Fixam L = {w = a1...an ∈ Σ∗}. Fie A peste Σ cu Q ={q0, ..., qn}, F = {qn} si:

δ a1 a2 ... an→ q0 q1q1 q2...

qn−1 qnqn ←

unde ın locurile necompletate apare multimea vida. Avem L(A) = {w}.

ii) Fie L = {ε} si A peste Σ cu Q = {q0, q1}, F = {q0} si:

δ ... ai ...

→ q0 ← q1q1 q1

.

Avem L(A) = {ε}.

S7.10 Sa se arate ca multimea vida este recognoscibila.

Rezolvare Fie A peste σ cu Q = {q0, q1}, F = {q1} si:

δ ... ai ...

→ q0 q0q1 ← q0

.

Avem L(A) = ∅.

S7.11 Fie L1 si L2 recognoscibile. Sa se arate ca L1∪L2 este recognosci-bila.

44 M. Crasmareanu

Rezolvare Presupunem Li = L(Ai), 1 ≤ i ≤ 2 si fie A cu Q = Q1 ×Q2,q0 = (q10, q

20), F = (F1×Q2)∪(Q1×F2) si δ((q1, q2), x) = (δ1(q1, x), δ2(q2, x)).

Avem imediat ca L(A) = L1 + L2.

Consecinta Orice multime finita din Σ∗ este recognoscibila.

S7.12 Daca x ∈ Σ sa se arate ca L = x∗ este recognoscibil.

S7.13 Pentru L ⊆ Σ∗ si w ∈ Σ∗ definim w−1L = {α ∈ Σ∗;wα ∈ L}si Σ∗

L familia acestor multimi cu posibilitatea includerii si a multimii vide.Atunci L este recognoscibila daca si numai daca Σ∗

L este finita.

S7.14 Daca L ⊆ Σ∗ este recognoscibila atunci Σ∗ \L este recognoscibila.

S7.15 Daca L1 si L2 sunt recognoscibile atunci sunt recognoscibile:i) L1 ∩ L2; ii) L1 · L2.

S7.16 Sa se arate ca, relativ la alfabetul binar, limbajul L = {0n1n;n ∈N} nu este recognoscibil.

Rezolvare Fie, prin reducere la absurd, A cu L(A) = L si fie, eventualprin renumerotare, qn = δe(q0, 0

n). Sa se presupunem ca qn = qm. Avem,δe(q0, 0

m1n) = δe(qm, 1n) = δe(q0, 0

n1n) ∈ F si deci 0m1n ∈ L(A) = L. Daratunci m = n ceea ce spune ca Q este infinita. Fals.

S7.17 Fie alfabetele Σ1, Σ2 si f : Σ∗1 → Σ∗

2 cu f−1(ε2) = ε1. Sa se arateca daca L ⊆ Σ∗

1 este recognoscibila atunci f(L) este recognoscibila.

S7.18 Dat semiautomatul SA si w ∈ Σ∗ fie functia Fw : Q→ Q,Fw(q) =δe(q, w). Definim ∼SA pe Σ∗ prin w1 ∼ w2 daca Fw1 = Fw2 . Sa se arate ca∼SA este o congruenta pe Σ∗.

Rezolvare Fie x, y ∈ Σ∗ oarecare. Daca w1 ∼SA w2 atunci evidentxw1y ∼SA xw2y.

Observatie Fie w1 ∼SA w2 si x, y ∈ Σ∗. Atunci sau xw1y, xw2y apartinlui L(A) sau xw1y, xw2y apartin lui Σ∗ \ L(A). Deci:

w1 ∼SA w2 ⇔ [xw1y ∈ L(A)⇔ xw2y ∈ L(A),∀x, y ∈ Σ∗].

Fie L ⊆ Σ∗. Definim ∼L prin:

w1 ∼L w2 ⇔ [xw1y ∈ L⇔ xw2y ∈ L,∀x, y ∈ Σ∗]

si deci ∼SA=∼L(A).

S7.19 Fie L ⊆ Σ∗ recognoscibila de catre automatulAL. Atunci∼AL=∼L.

Definitia 7.20 Congruenta ∼L pentru L recognoscibila se numestecongruenta Myhill.

Cursul 8

Actiuni

Fixam ın acest curs o multime nevida X, nu neaparat finita. Reamintim caın exercitiul 1.3 am introdus grupul bijectiilor lui X, Bij(X) = {f : X →X; f bijectie}. Pentru simplitate, acelasi grup ıl vom nota cu S(X) deoarecedaca X are n elemente atunci acest grup este bine cunoscutul grup simetricSn.

Definitia 8.1 Numim grup de transformari pe X un subgrup G al luiS(X). Notiuni analoage se definesc prin ınlocuirea cuvantului ”grup” cu”monoid” respectiv ”semigrup”.

Din conditia de subgrup avem:GT1) daca f1, f2 ∈ G atunci f2 ◦ f1 ∈ G,GT2) daca f ∈ G atunci f este bijectie si f−1 ∈ G.

Una din cele mai importante notiuni matematice este:

Definitia 8.2 Dat grupul (G, ·, e) oarecare, numim actiune (la stanga)a lui G pe X o aplicatie φ : G×X → X, (g, x)→ gx satisfacand:A1) g2(g1x) = (g2g1)x,A2) ex = x,pentru orice g1, g2 ∈ G si orice x ∈ X.

Observatia 8.3 Exista si notiunea de actiune la dreapta, δ : X ×G→X, (x, g)→ xg cu propritatile:A’1) (xg1)g2 = x(g1g2),A’2) xe = x.Dar cele doua notiuni sunt echivalente ın sensul urmator:I) data o actiune la stanga avem ca aplicatia δ(x, g) = g−1x este o actiunela dreapta. In adevar:A’1) (xg1)g2 = g−1

2 (g−11 x) = (g−1

2 g1−1)x = (g1g2)−1x = x(g1g2),

45

46 M. Crasmareanu

A’2) xe = e−1x = ex = x.II) Reciproc data o actiune la dreapta avem ca aplicatia φ(g, x) = xg−1 esteo actiune la stanga. In adevar,A1) g2(g1x) = (xg−1

1 )g−12 = x(g−1

1 g−12 ) = x(g2g1)

−1 = (g2g1)x,A2) ex = xe−1 = xe = x.Prin urmare, ın cele ce urmeaza ne vom restrange la actiuni la stanga, aces-tea fiind cel mai des ıntalnite ın matematica (spre exemplu ın studiul pro-prietatilor de simetrie ale unui obiect matematic) fara a pierde din vederefaptul ca proprietatile A’1, A’2 sunt analoage proprietatilor extinderii functieide tranzitie δe din teoria automatelor. Acest fapt a si motivat alegereasubiectului acestui curs.

Fixam deci φ : G ×X → X si pentru orice g ∈ G definim φg : X → Xprin x→ gx.

Propozitia 8.4 φg ∈ S(X).

Demonstratie Avem: φg ◦ φg−1 : x → g−1x → g(g−1x) = (gg−1)x =

ex = x. Analog, φgφg−1 : x → gx → g−1(gx) = (g−1g)x = ex = x. Inconcluzie, φg este bijectie cu (φg) = φg−1 . �

Putem deci defini Φ : G→ S(X), g → φg.

Propozitia 8.5 Φ este morfism de grupuri.

Demonstratie Trebuie aratat ca Φ(g2g1) = Φ(g2) ◦ Φ(g1). Cum aces-tea sunt aplicatii trebuie aratata egalitatea pentru orice x ∈ X. Dar astaınseamna exact A1. �

Corolarul 8.6 Imaginea prin Φ a lui G este un grup de transformari peX.

Demonstratie Este o consecinta a rezultatului clasic din teoria grupurilor:dat un morfism de grupuri Φ : G → G′ avem ca Φ(G) este subgrup ın G′.(Aratati !). �

Avem si reciproca acestui ultim rezultat:

Propozitia 8.7 Dat grupul de transformari G al lui X avem ca:i) incluziunea i : G→ S(X) este un morfism de grupuri,ii) aplicatia φ : G×X → X, (g, x)→ g(x) este o actiune a lui G pe X.

Demonstratie i) evident, i(g1 ◦ g2) = g1 ◦ g2 = i(g1) ◦ i(g2),ii) A1 g2(g1x) = g2(g1(x)) = (g2 ◦ g1)(x) = (g2 ◦ g1)x; A2 ex = 1X(x) = x.�

Avem si un al treilea rezultat analog:

Cursul 8 47

Propozitia 8.8 Dat morfismul de grupuri Φ : G → S(X) avem caaplicatia φ : G×X → X, (g, x)→ Φ(g)(x) este o actiune a lui G pe X.

Demonstratie A1) g2(g1x) = Φ(g2)(Φ(g1)(x)) = Φ(g2) ◦ Φ(g1)(x) =Φ(g2g1)(x) = (g2g1)x,A2) ex = Φ(e)(x) = 1X(x) = x. �

In concluzie, urmatoarele trei notiuni sunt echivalente:i) actiune a lui G pe X,ii) morfism de grupuri Φ : G→ S(X),iii) G=grup de transformari pe X.Astfel, ın diferite surse bibliografice poate aparea una din aceste formeechivalente.

Definitia 8.9 Spunem ca elementele x, y ∈ X sunt ın relatia ”∼” sinotam x ∼ y daca exista g ∈ G a.ı. y = φg (x) i.e. y = gx.

Propozitia 8.10 ”∼” este o relatie de echivalenta pe X.

Demostratie reflexivitatea: x ∼ x doarece luam g = e,simetria: presupunem x ∼ y cu y = φg (x) si aplicam φg−1 acestei egalitati.Rezulta x = g−1y si deci y ∼ x,tranzitivitatea: presupunem x ∼ y, y ∼ z cu y = g1x, z = g2y. Rezulta

z = g2 (g1x)A1= (g2g1)x si deci x ∼ z. �

Definitia 8.11 Clasa de echivalenta a lui x ∈ X ın raport cu ”∼” senumeste orbita lui x la actiunea φ si o notam Gx sau Orb (x). Multimeaorbitelor o notam X/G si o numim spatiul factor al lui X la actiunea lui G.Avem surjectia π : X → X/G numita proiectie.

Daca discutia anterioara ne-a plasat pe X este naturala si o privireasupra lui G.

Definitia 8.12Dat x ∈ X numim stabilizatorul lui xmultimea Stab(x) ={g ∈ G; gx = x}.

Propozitia 8.13 Stab(x) este subgrup ın G.

Demonstratie Sa observam mai ıntai ca Stab(x) este nevida deoarecee ∈ Stab(x).i) Fie g1, g2 ∈ Stab(X); avem imediat ca g1g2 ∈ Stab(x),ii) Fie g ∈ Stab(x) oarecare; deci g−1(gx) = g−1x de unde rezulta ca g−1x =(g−1g)x = ex = x, deci g−1 ∈ Stab(x). �

ObservatieDin acest motiv, uneori Stab(x) este numit grupul de izotropiea lui x ∈ X.

48 M. Crasmareanu

O proprietate remarcabila a stabilizatorilor este:

Propozitia 8.14 Daca y ∈ Orb(x) atunci Stab(x) si Stab(y) sunt sub-grupuri conjugate.

Demonstratie Presupunem ca y = ax, a ∈ G.i) dat g ∈ Stab(x) avem ca aga−1 ∈ Stab(y) dupa cum se verifica imediat.Deci aStab(x)a−1 ⊆ Stab(y),ii) a arata Stab(y) ⊆ aStab(x)a−1 este echivalent cu a arata relatiaa−1Stab(y)a ⊆ Stab(x) care este analoaga celei de la i) cu argumentul x =a−1y. �

Corolarul 8.15Daca un element al unei orbite O are stabilizator abelian(finit) atunci toate elementele lui O au stabilizatorul abelian (finit). Maimult, oricare ar fi x, y ∈ O avem |Stab(x)| = |Stab(y)|.

Definitia 8.16 Fie H subgrup al lui G si elementele fixate x, y ∈ G.Spunem ca x, y sunt H-right echivalente si notam xH ∼r y daca existah ∈ H asa ıncat x = yh.

Propozitia 8.17 ∼r este o relatie de echivalenta pe G.

Demonstratie 1) reflexivitatea: luam h = e ∈ H. 2) simetria: fie x =yh. Rezulta ca y = xh−1 si cum h−1 ∈ H avem cerinta. 3) tranzitivitatea:presupunem x = yh1 si y = zh2. Rezulta x = z(h2h1) si cum h2h1 ∈ Havem concluzia. �

Multimea cat o notam G/H. Clasa de echivalenta a lui x ∈ G estexH = {xh;h ∈ H} si aplicatia h ∈ H → xh ∈ xH este evident bijectie; deci|xH| = |H|. Cum multimea claselor de echivalenta constituie o partitie alui G rezulta ca daca G este grup finit avem |G/H| · |H| = |G|.

Revenind la actiuni fie H = Stab(x); deci |G/Stab(x)| · |Stab(x)| = |G|.Fie φ : Orb(x) → G/Stab(x), y = gc → φ(x) = gStab(x). Avem ca φ estecorect definita: daca y = g1x = g2x atunci g−1

2 g1 ∈ Stab(x) si deci g1 = g2hcu h ∈ Stab(x); rezulta ca g1Stab(x) = g2Stab(x), ceea ce voiam.

Propozitia 8.18 φ este bijectie.

Demonstratie Evident φ este surjectie caic dat gStab(x) ∈ G/Stab(x)vom considera y = gx ∈ Orb(x). Fie acum φ(y1) = φ(y2) cu y1 = g1x, y2 =g2x; rezulta g1Stab(x) = g2Stab(x) i.e. g1h1 = g2h2 cu h1, h2 ∈ Stab(x).Deci g2 = g1h1h

−12 si avem y2 = (g1h1h

−12 )x = g1(h1h

−12 x) = g1x = y1

folosind ca Stab(x) este subgrup. �

Cursul 8 49

In concluzie, daca G si X sunt multimi finite avem pentru orice x ∈ X:

|Orb(x)| · |Stab(x)| = |G|, (8.1).

Definitia 8.19 Permutarea [a1, ..., ak] din Sn o numim permutare ciclicasau k-ciclu deoarece avem a1 → a2 → ... → ak → a1. Un 2-ciclu ıl numimtranspozitie.

Propozitia 8.20 1) Orice element din Sn este produs de permutari ci-clice distincte ın sensul ca un element apare cel mult odata.2) Transpozitiile genereaza Sn.3) Transpozitiile [12], ..., [1n] genereaza Sn deoarece [ab] = [1a][1b][1a].4) Transpozitiile [12], [23], ..., [n− 1n] genereaza Sn deoarece[1k] = [k − 1k]...[23][12][23]...[k − 1k].5) Transpozitia [12] si n-ciclul [12...n] genereaza Sn deoarece [kk + 1] =[12...n]k−1[12][12...n]1−k.

Definitia 8.21 Actiunea lui G pe X se numeste:i) tranzitiva daca exista o singura orbita i.e. X/G este o multime singleton,ii) libera daca toti stabilizatorii se reduc la {e}.

SEMINARUL 8

S8.1 Fie N(o) numarul orbitelor actiunii lui G pe X i.e. X = Orb(x1)∪... ∪Orb(xN(o)) cu Orb(xi) ∩Orb(xj) = ∅ pentru i, j diferite. Pentru g ∈ Gfie Fix(g) = {x ∈ X; gx = x}. Are loc formula Burnside:

N(o) · |G| =∑g∈G|Fix(g)|. (8.2)

Rezolvare Vom numara ın doua moduri distincte elementele lui X in-variate de actiunea lui G. Avem:∑

g∈G|Fix(g)| =

∑x∈X|Stab(x)|, (8.3)

si deci membrul drept din (7.2) este∑N(o)

i=1

∑y∈Orb(xi)

|Stab(y)|. Dar pentruorice y, z ∈ Orb(xi) avem: |Stab(y)| = |Stab(z)|frac|G||Orb(xi) rezulta:

∑g∈G|Fix(g)| =

N(o)∑i=1

|Orb(xi)||G|

|Orb(xi)|= N(o) · |G|.

50 M. Crasmareanu

S8.2 Fie X = N3 = {1, 2, 3} si G = {e, f, d} cu e = [1][2][3] permutareaidentica, d = [1, 2, 3] si f = [1, 3, 2]. Consideram actiunea naturala a lui Gpe X.i) Sa se arate ca G este subgrup ın S3; deci grup.ii) Se cer numarul orbitelor acestei actiuni.

Rezolvare i) df = [1, 2, 3][1, 3, 2] = [1][2][3] = e, fd = [1, 3, 2][1, 2, 3] =[1][2][3] = 3 si d2 = f, f2 = d. Deci d = f−1 sau ınca f = d−1 ceea ce arataca G este subgrup ın S3.ii) |Fix(e)| = 3, |Fix(d)| = |Fix(f)| = 0 si deci N(o) = 3+0+0

3 = 1. Orbitaunica este ıntreaga multime X ceea ce puteam vedea si direct: 1 ∼ 1 cug = e; 1 ∼ 2 cu g = d; 1 ∼ 3 cu g = f ; deci toate elementele lui X suntechivalente ıntre ele.

Interpretare geometrica: X este multimea varfurilor unui triunghi echi-lateral ∆, e=aplicatia identica, d=rotatia ın sens orar de unghi π

3 , f=rotatiaın sens trigonometric de unghi π

3 . Avem imediat ca f = d−1 si f2 = d.

S8.3 Se da semiautomatul A peste alfabetul binar cu Q = {q0, ..., q5} siδ data de: δ(q0, 0) = q1, δ(q0, 1) = q5, δ(qi, 0) = qi, δ(qi, 1) = qi−1, 1 ≤ i ≥ 5.i) Se cere reprezentarea tabelara a lui δ.ii) Daca F = Q \ {q0} se cere L(A) pentru automatul A.

Rezolvare i)δ 0 1

q0 q1 q5q1 q1 q0q2 q2 q1q3 q3 q2q4 q4 q3q5 q5 q4

.

ii) L(A) = {0n;n ∈ N∗} + {010n;n ∈ N∗} + {1a0m; a = 1, 2, 3, 4,m ∈ N} +{150n;n ∈ N∗}.

S8.4 Fie automatul A peste alfabetul binar cu Q = {q0, q1, q2, q3} si:

δ 0 1

→ q0 {q0, q1, q3} q0q1 q2 ∅q2 q3 ∅q3 ← ∅ ∅

.

Sa se studieze cuvintele w1 = 0110, w2 = 101101 si w3 = 1011.

Cursul 8 51

Rezolvare w1, w2 ∈ L(A) iar w3 /∈ L(A).

S8.5 Sa se arate ca φ : (Z,+) × R → R, φ(k, x) = k + x este o actiunesi sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. Fie M =R/(Z,+, φ) si fie ψ : M → S1, ψ([x]) = e2πix = cos(2πx) + isin(2πx).Sa verificam buna definire: [x] = [y] implica y = x + n si deci cos(2πy) +isin(2πy) = cos(2πx) + isin(2πx).1) ψ este injectiva deoarece ψ(x) = ψ(y) implica e2πi(y−x) = 1 adica y−x ∈ Zceea ce ınseamna [x] = [y].2) ψ este surjectiva ın mod evident.

In concluzie, R/(Z,+, φ) = S1. Avem:i) Orb(x) = x+ Z pentru orice x ∈ R,ii) Stab(x) = {0}.Deci, φ este actiune libera si netranzitiva.

S8.6 Sa se arate ca φ : (R,+) × R → R, φ(t, x) = etx este o actiune sisa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. Avem doar3 orbite:i) [0] = {0} si Stab(0) = R,ii) [1] = R∗

+,iii) [−1] = R∗

−.Deci R/(R,+, φ) = {[0], [1], [−1]}; pentru orice x = 0 avem Stab(x) = {0}.Deci actiunea este nelibera si netranzitiva.

S8.7 Fie n numar natural nenul. Un element (vector) din Rn ıl notamx = (x1, ..., xn). Sa se arate ca φ : (Rn,+) × R2n → R2n, φ(a, (x, y)) =(a+ x, y) este o actiune si sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. AvemStab(x, y) = {0n} si (x, y) ∼ (0, y) prin intermediul lui a = −x. DeciR2n/(Rn,+, φ) = (0,Rn) ≃ Rn. Actiunea este libera si netranzitiva.

S8.8 Sa se arate ca translatia φ : (Rn,+) × Rn → Rn, φ(a, x) = a + xeste o actiune si sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. Orice punctx se transleaza ın origine cu a = −x si deci Rn/(Rn,+, φ) = {[0]}. Actiuneaeste libera si tranzitiva.

S8.9 (Grupul ciclic de ordinul 2) Sa se arate ca (Z2,+) este grupizomorf cu (C2, ·) unde C2 = {1,−1}.

52 M. Crasmareanu

Rezolvare Cele doua grupuri au aceeasi tabela Cayley:

(Z2,+) 0 1

0 0 1

1 1 0

(C2,+) 1 −11 1 −1−1 −1 1

.

Prin urmare corespondenta 0 → 1, 1 → −1 este un izomorfism de grupuride la Z2 la C2.

Generalizare Grupul ciclic de ordinul n este multimea Cn a simetri-ilor de rotatie ale unui poligon regulat cu n laturi. Cn este deci multimearotatiilor de unghi θk = 2kπ

n cu k ∈ {0, ..., n − 1}, operatia de grup fiindcompunerea rotatiilor. Rezulta ca (Cn, ◦) este grup izomorf cu (Zn,+).

S8.10 Sa se arate ca φ : C2 × R → R, φ(ε, x) = εx este o actiune pe Rsi sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. AvemOrb(x) = {x,−x} si Stab(x) = {1}; deci actiunea data este libera si ne-tranzitiva.

S8.11 Sa se arate ca φ : (C2×C2)×R2 → R2, φ((ε, δ), (x, y)) = (εx, δy)este o actiune si sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. AvemOrb(x, y) = {(x, y), (x,−y), (−x, y), (−x,−y)} si Stab(x, y) = {(1, 1)}; deciactiunea este libera si netranzitiva.

S8.12 Sa se arate ca φ : (R∗, ·)× Rn → Rn, φ(λ, x) = λx este o actiunesi sa se studieze.

Rezolvare Verificarea axiomelor de actiune este imediata. AvemOrb(0) = 0, Stab(0) = R∗ iar pentru x = 0 avem Stab(x) = 1 iar Orb(x)este dreapta prin originea lui Rn fara origine. Spatiul cat Rn\{0}/(R∗,+, φ)se noteaza Pn−1R si se numeste spatiul proiectiv real n − 1-dimensional.Actiunea pe Rn \ {0} este libera si netranzitiva.

Cursul 9

Gramatici si limbajegenerate. Ierarhia Chomsky

Definitia 9.1 Numim gramatica sau sistem generativ un 4-upluG = (VN , VT , S, P ) cu:i) VN=multime nevida, finita, numitamultimea variabilelor (neterminalilor),ii) VT=multime nevida, finita, disjuncta de VN , numita multimea termi-nalilor. V = VN ∪ VT este vocabularul lui G,iii) S ∈ VN este simbolul de start sau axioma gramaticii,iv) P ⊂ V ∗ × V ∗, finita, este multimea regulilor de generare (productie).Elementele (α, β) ∈ P sunt supuse conditiei ca α sa contina un simbol dinVN ; putem scrie P ⊂ (V ∗VNV

∗)× V ∗.

Conventii de notatie 9.2I) Urmatoarele simboluri noteaza elemente din VN :-A,B,C, ..., S, ...-numele italice scrise cu minuscule: expresie, instructiune, ...II) Urmatoarele simboluri noteaza terminali:-a, b, c, ..., 0, ..., 9-operatori: +,−,×, /-simboluri de punctuatie, paranteze,-unitati lexicale: id, if, while, begin, ...III) X,Y, Z, ... sunt elemente din V iar u, v, x, y, z, w, ... sunt cuvinte din V ∗.IV) α, β, γ, ... sunt cuvinte din V . Un element (α, β) ∈ P ıl notam α→ β.V) Daca A → α1,..., A → αn sunt toate productiile cu originea ın A, (A-productii), notam: A→ α1|...|αn.VI) O gramatica va fi precizata prin productiile sale; de aici se deducmultimile VN si VT iar S este partea stanga a primei productii.

53

54 M. Crasmareanu

Exemplu 9.3 Gramatica S → SOS| − S|(S)|id,O → +| − | × |/ areVN = {S,O} si VT = {id,+,−,×, /, (, )}.

Definitia 9.4 Date u, v ∈ V ∗ scrierea u →∗ v noteaza faptul ca u = vsau exista un sir finit u1 = u, ..., un = v de elemente din V ∗ astfel ca ui →ui+1, 1 ≤ i ≤ n− 1. Un astfel de sir ıl numim derivare.Vom mai folosi notatiile:-”→(i)”: derivarea directa a folosit regula i din P ,-”→i”: derivarea s-a facut aplicand i pasi (reguli),-”→(i)j”: se aplica regula i de j ori.ii) Limbajul generat de G este L(G) = {w ∈ V ∗

T ;S →∗ w} iar w ∈ L(G) ılnumim fraza ın G.iii) FP (G) = {α ∈ V ∗;S → α} este multimea formelor propozitionale ale luiG. Deci L(G) = FP (G) ∩ V ∗

T i.e. limbajul generat este multimea formelorpropozitionale ce contin doar simboli terminali.v) Gramaticele G1, G2 se numesc echivalente daca L(G1) = L(G2).

Ierarhia Chomsky 9.5 Fixam gramatica G:0) G generala se numeste de tip 0,1) daca toate productiile α → β satisfac conditia |α| ≤ |β| atunci spunemca G este de tip 1 sau monotone,1’) daca toate productiile sunt de forma αAβ → αρβ cu A ∈ VN , α, β ∈V ∗, ρ ∈ V + atunci spunem ca G este dependenta de context,2) daca toate productiile sunt context-free i.e. de forma A → α cu A ∈VN , α ∈ V + atunci spunem ca G este de tip 2 sau context-free,lin) daca toate productiile sunt de forma A → α sau A → αBβ cu A,B ∈Vn, α, β ∈ V ∗

T atunci spunem ca G este gramatica liniara,3) daca toate productiile sunt de forma A → aB sau A → a cu A,B ∈ VNsi a ∈ VT atunci spunem ca G este de tip 3 sau regulata,3’) daca toate productiile sunt de forma A → α sau A → αB (respectivA → Bα) cu A,B ∈ VN , α ∈ VT atunci spunem ca G este drept liniara(respectiv stang liniara).Limbajul L ⊂ V ∗

T se numeste de tip r, 0 ≤ r ≤ 3 sau liniar daca exista ogramatica G de tip r sau liniara a. ı. L = L(G).

Gramaticile 1 si 1’ sunt echivalente si la fel 3 si 3’. Notand cu Linrespectiv Lr multimea limbajelor liniare respectiv de tip r avem:

L3 ⊂ Lin ⊂ L2 ⊂ L1 ⊂ L0

si acest sir de incluziuni stricte se numeste ierarhia lui Chomsky (1956).Lingvistul american Noam Chomsky a introdus gramaticile libere de

context ın scopul descrierii limbilor naturale. Desi acest scop s-a dovedit

Cursul 9 55

mult prea ambitios, limbajele (gramaticile) context-free s-au aratat utile ındescrierea limbajelor de programare. Astfel, au fost utilizate de Bachuspentry FORTRAN si Naur pentru ALGOL (din acest motiv, gramaticilelibere de context se numesc uneori gramatici ın forma Backus-Naur) ın timpce recent HTML-ul a fost descris cu un limbaj independent de context.

”An HTML document (with arbitrary text content) has this sort of struc-ture:<HTML><HEAD> <TITLE> Jane Doe’s Home Page </TITLE> </HEAD><BODY> <H1> Jane Doe </H1> <H2> Home Page </H2><P><CENTER> <IMG src=”jane.jpg”> </CENTER></P></BODY></HTML>The expression <HTML> must be followed by </HTML>, <HEAD> mustbe followed by </HEAD>, and so on, in the same pattern as matched paren-theses. Thus recognizing that a string belongs to a certain CFL (context-freelanguage) is one of the tasks performed by a web browser.”

Aceleasi limbaje context-free sunt deosebit de importante ın proiectareacompilatoarelor.

Pentru generalitati asupra operei lui Chomsky a se vedeahttp://en.wikipedia.org/wiki/Noam Chomsky ca si site-ul personalhttp://www.chomsky.info/. Alte site-uri recomandate:-http://en.wikipedia.org/wiki/Chomsky hierarchy-http://mathworld.wolfram.com/Grammar.html.

In aplicatii, sa notam ca dat L ∈ L0 se cauta r maximal pentru careL ∈ L0. Astfel, este posibil ca initial sa avem L = L(G) cu G de tip r darsa existe r′ > r si G′ de tip r′ astfel ıncat L = L(G′).

SEMINARUL 9

S9.1([13, p. 18]) Sa se arate ca L1 = {anbn;n ≥ 0} ∈ Lin− L3.

Rezolvare([10, p. 11]) Fie gramatica G cu VN = {S}, VT = {a, b} siP : S → ab|aSb. Avem ca G este liniara dar nu este regulata. Aratam prininductie ca L1 ⊆ L(G).1) pasul de pornire e evident din prima regula.2) presupunem ca akbk ∈ L(G), k ≥ 1. Deci avem o derivare S →∗ akbk cu

56 M. Crasmareanu

un = akbk si un−1 = ak−1Sbk−1. Avem atunci un−i →(2) ak−1(aSb)bk−1 =akSbk →(1) ak+1bk+1 ceea ce voiam.

A mai ramas de aratat ca L(G) ⊆ L1. Analizand derivarile posibile dinG avem PF (G) = {akSbk, akbk} dar ultima derivare nu mai poate continuadatorita regulilor de productie din G. Avem deci concluzia.

S9.2([13, p. 18]) Sa se arate ca L2 = L1L1 ∈ L2 − Lin .

S9.3([13, p. 18]) Sa se arate ca L3 = {anbncn;n ≥ 1} ∈ L1 − L2 .

Rezolvare([10, p. 20]) Fie G cu VN = {S,A}, VT = {a, b, c} si P : S →abc|aSA, bA → bbc, cA → AC. Este o gramatica monotona dar nu de tipul2. Aratam prin inductie ca L3 ⊆ L(G).

S9.4([13, p. 18]) Sa se arate ca L4 = {a2n;n ≥ 0} ∈ L1 − L2 .

Rezolvare([10, p. 24]) Fie G cu VN = {S,A,B,C}, VT = {a} si P :S → BAB,BA→ BC,CA→ AAC,CB → AAB,A→ a,B → ε.

S9.5([13, p. 18]) Sa se arate ca L5 = {an2;n ≥ 0} ∈ L1 − L2 .

S9.6([13, p. 18]) Sa se arate ca L6 = {an;n = prim} ∈ L1 − L2 .

S9.7([13, p. 18]) Sa se arate ca L7 = {anbmanbm;n,m ≥ 1} ∈ L1 − L2 .

S9.8([13, p. 18]) Sa se arate ca L8 = {anbm;n ≥ 1, 1 ≤ m ≤ 2n} ∈L1 − L2 .

S9.9([13, p. 18]) Sa se arate ca L9 = {anbmcp; 1 ≤ n ≤ m ≤ p} ∈ L1−L2

.

S9.10([13, p. 18]) Sa se arate ca L10 ∈ L2 − Lin unde L10 este lim-bajul lui Dyck pentru vocabularul {a, b} i.e. limbajul generat de gramaticaindependenta de context G = ({S}, {a, b}, S, P ) cu P : S → SS|aSb|ε.

S9.11 .

Rezolvare .

S9.12 .

Rezolvare .

Cursul 10

Problema cuvintelor

Deoarece vom lucra ın acest curs pe grupuri, extindem mai ıntai definitiacuvintelor pentru a formaliza notiunea de invers. Fixam X = {x1, ..., xk}o multime finita. Numim cuvant de lungime n pe multimea X o functiew : Nn = {1, ..., n} → X × {1}. Daca w(i) = (wi, εi) atunci cuvantul wse mai noteaza w = xε1w1

...xεnwn. Operatia de concatenare se defineste uzual:

ww′ := xε1w1...xεnwn

xε′1w′

1...x

ε′nw′

nsi ramane asociativa. Fie W (X) acest monoid

relativ la cuvantul vid.

Definitia 10.1 i) O echivalenta elementara pe W (X) este o pereche decuvinte de forma (d1x

εwx

−εw d2, d1d2) cu ε ∈ {1} si d1, d2 cuvinte arbitrare.

ii) Pe W (X) definim o relatie ın modul urmator: doua cuvinte le numimechivalente daca pot fi legate printr-un lant finit de echivalente elementare.Astfel, cele doua cuvinte se transforma unul ın celalalt prin stergerea sauintroducerea unor perechi xwx

−1w sau x−1

w xw, w = 1, ..., n.

Propozitia 10.2 Relatia astfel introdusa este o congruenta.

Monoidul cat devine grup definind inversul astfel: [w = xε1w1...xεnwn

]−1 =[w = x−εn

wn...x−ε1

w1] si notand cu 1 clasa cuvantului vid.. Acest grup numit

grupul liber generat de X si notat F (X); are o proprietate de universalitateın categoria grupurilor: pentru orice grup G si elemente fixate g1, ..., gk ∈ Gexista un unic morfism de grupuri φ : F (X)→ G satisfacand φ(xi) = gi, i =1, ..., k.

Mai general, fixam R = {c1, ..., cm} o multime de cuvinte peste Σ nu-mite relatii. Intersectia tuturor subgrupurilor normale ce contine R ıl notamN(R) si este subgrup normal. Putem vorbi atunci de grupul factor F (Σ)/N(R)notat < X|R > si pentru care elementele lui X le numim generatori. Maispunem ca grupul G =< X|R > este prezentat prin generatori si relatii.

57

58 M. Crasmareanu

Observatia 10.3 Trebuie avut grija atat ın precizarea generatorilor catsi a relatiilor:1) Prezentarea < x, y|xy = yx, xyx−1 = yxy−1 > este gresita deoarecex = y. Inmultim a doua relatie la dreapta cu y: xyx−1y = yx = xy.Simplificam prin xy la stanga si avem x−1y = 1 de unde concluzia.2) Relatiile x2 = y2 = (xy)2 = 1 implica comutativitatea xy = yx. Inadevar, din ultima relatie: xyxy = 1 pe care o ınmultim la stanga succesivcu x si apoi y.

Exemple 10.4 1) Cn :< x|xn = 1 > este prezentarea grupului ciclic deordin n ≥ 2 din cursul 8.2) < x, y|x2 = y3 = 1, yxy = x > este o prezentare a grupului simetricS3 luand x = [12] si [123]. De aici rezulta ca S3 este primul grup simetricneabelian deoarece din a treia relatie avem yx = xy−1 iar y−1 = y are day2 = 1 care ımpreuna cu a doua relatie conduce la contradictia y = 1.

Notiunea centrala a acestui curs a fost formulata de Dehn sub numele deproblema cuvintelor astfel: dat w ∈ X∗ sa se gaseasca o procedura continandun numar finit de instructiuni pentru a decide daca w = 1 sau nu. Oformulare moderna este urmatoarea:

Definitia 10.5 Grupul G =< X|R > are solutie la problema cuvintelordaca limbajul W (G) = {w ∈ X∗;w = 1} este recunoscut de un automatdeterminist.

Exemplul 10.6 Daca X este finita atunci grupul liber F (X) =< X|∅ >are solutie la problema cuvintelor.

Definitia 10.7 Dat grupul G =< X|R > si limbajul L ⊂ X∗ spunemca perechea (X,L) este o structura rationala pentru G daca L este regulatsi L genereaza pe G.

Consideram un simbol $ /∈ X (”the padding simbol”=simbolul auxiliar)si definim X ′ = X∪{$} si X(2, $) = X ′×X ′\{$, $}. Definim µ : X∗×X∗ →X(2, $)∗ prin:1) µ(u = x1...xm, v = y1...yn) = (x1, y1)...(xn, yn)(xn+1, $)...(xm, $) dacan < m,2) µ(u, v) = (x1, y1)...(xn, yn) daca n = m,3) µ(u, v) = (x1, y1)...(xm, ym)($, yn+1)...($, yn) daca n > m.Fie (X,L) structura rationala pentru G si w ∈ X∗; definimLw = {µ(w1, w2);w1, w2 ∈ L,w1 = ww2}.

Definitia 10.8 i) Structura rationala (X,L) a lui G se numeste structuraautomata daca Lε si Lx, pentru orice x ∈ L, sunt limbaje regulate.

Cursul 10 59

ii) Grupul G se numeste automat daca admite o structura automata.

Exemple 10.9 Sunt grupuri automate urmatoarele clase de grupuri:grupurile finite, grupurile libere finit generate, grupurile abeliene finit gen-erate, grupuri braid.

Dat w ∈ X∗ cu w = 1 reamintim ca w =F (X)

∏i = 1k(uir

±1i u−1

i ) cuui ∈ F (X), ri ∈ R, k ∈ N. Fie a(w) cea mai mica valoare a lui k.

Definitia 10.10 Functia izoperimetrica a lui G =< X|R > este fG :N→ N:

f(n) = max{a(w); |w| ≤ n,w = 1}.

Problema cuvintelor pe grupuri automate este rezolvata de:

Teorema 10.11 Daca G este grup automat atunci:1) G admite o prezentare finita cu functia izoparametrica marginita superiorde o functie patratica.2) G are solutie la problema cuvintelor.

Demonstatia acestui rezultat fundamental se bazeaza pe:

Propozitia 10.12 Fie < X|R > o prezentare finita a grupului G.Urmatoarele sunt echivalente:i) Functia izoparamerica este marginita superior de o functie recursiva.ii) G are solutie la problema cuvintelor.iii) Functia izoparametrica este marginita.

SEMINARUL 10

S10.1 Sa se arate ca urmatoarele sunt prezentari ale grupului trivial:a) < x, y|x2 = y3, xyx = yxy >.b) < x, y|xy = y2x, yx = x2y >.c) < x, y, z|xy = y2x, yz = z2y, zx = x2z >.

Rezolvare a) Din a doua relatie prin ınmultirea cu x la stanga si ladreapta avem: x2yx2 = xyxyx adica y7 = y3yy3 = xyxyx. Tot din a douarelatie prin ınmultire la dreapta cu yx avem xyxyx = yxy2x; deci y7 = yxy2xde unde avem y6(= x4) = xy2x. Obtinem x2 = y2 si din y2 = y3 avem y = 1.Revenind la a doua relatie rezulta si x = 1.

S10.2 Grupul diedral (dihedral group ın engleza) Dn este grupul simetri-ilor de rotatie al unei placi ın forma de poligon regulat cu n laturi. (Alti

60 M. Crasmareanu

autori ıl noteaza D2n.) Fie r rotatia de unghi 2πn ın jurul unei axe de sime-

trie perpendiculara pe poligon si s rotatia de unghi π ın jurul unie axe desimetrie din planul poligonului. Atunci o prezentare a lui Dn este:

Dn =< r, s|rn = 1, s2 = 1, sr = rn−1s >

si orice element dinDn este de forma rk sau rks cu 0 ≤ k ≤ n−1. Identitatilede calcul ın Dn:i) rarb = rk cu k = a+ b(mod n),ii) (ras)rb = rls cu l = a− b(mod n),iii) (ras)(rbs) = rls.Rezulta si alte perechi de generatori:I) (rs, s) deoarece r = (rs)s,II) (rs, r2s).

Rezolvare .

S10.3 Exista c si grupul diedral infinitD∞ generat de t, s : Z→ Z, t(z) =z + 1, s(z) = −z. Avem s2 = 1 ın timp ce t are ordin infinit. Identitateatst = s este evidenta din schema membrului stang: z → z + 1→ −z − 1→−z = s(z). Deci: D∞ =< t, s|s2 = 1, tst = s >.

Rezolvare .

S10.4

Rezolvare

Cursul 11

Functii recursive

In acest curs consideram functii f de tipul urmator:-functie partiala daca f : X → N cu X submultime (nevida ) a lui Nn,-functie totala daca f este definita pe tot Nn.Pentru simplitatea scrierii, ambele tipuri de functii le notam la fel f : Nn →N, ıntelegandu-se din context tipul. Fie P multimea tuturor functiilorpartiale (deci orice n) si T multimea tuturor functiilor totale. De asemenea,n-uplul (x1, ..., xn) ıl notam x.

Definitia 11.1 1) Fie numerele naturale n, k ≥ 1 si functiile g : Nk →N, h1, ..., hk : Nn → N din P. Numim compunerea lor functia f = g ◦(h1, ..., hk) : Nn → N data de f(x) = g(h1(x), ..., hk(x)). Evident f ∈ Pmembrul stang fiind definit acolo unde se poate defini membrul drept. Maispunem cam definit operatorul de superpozitie SUP.2) Fie g : Nn → N si h : Nn+2 → N din P. Functia partiala f : Nn+1 → Ndata de f(x, 0) = g(x), f(x, y + 1) = h(x, f(x), y) se numeste obtinuta prinrecursie primitiva. Cazul n = 0 este admis si atunci g se considera numarnatural fixat. Mai spunem cam definit operatorul de recursie primitiva REC.

Observatia 11.2 Dat x avem ca f(x, y) este definit: sau pentru niciuny sau pentru orice y ∈ N sau pentru y ∈ Nk = {1, ..., k} cu k determinat deg si h.

Definitia 11.3 1) Urmatoarele functii le numim initiale:i) functia zero z : N→ N, z(x) = 0,ii) fuctia succesor σ : N→ N, σ(x) = x+ 1,iii) functii proiectie πkr : Nk → N, πkr(x) = xr, k ≥ 1, 1 ≤ r ≤ k.Evident, toate functiile initiale apartin lui T .

61

62 M. Crasmareanu

2) Numim clasa de functii o submultime a lui P si clasa de functii totale osubmultime a lui T .3) O clasa C de functii totale o numim ınchisa primitiv recursiv daca:i) toate functiile initiale apartin lui C .ii) C este ınchisa la compunere i.e. daca g, h1, ..., hk ∈ C atunci g◦(h1, ..., hk) ∈C .iii) C este ınchisa la recursia primitiva i.e. daca g, h ∈ C atunci f otinutadin g si h prin recursie primitiva este element din C .

Exista o cea mai mica multime ınchisa primitiv recursiv F (pr) anumeintersectia tuturor claselor ınchise primitiv recursiv.

Definitia 11.4 Un element f ∈ F (pr) ıl numim functie primitiv recur-siva.

Teorema 11.4 (de caracterizare) Fie f ∈ T . Atunci f ∈ F (pr)daca si numai daca exista un sir f0, ..., fk = f unde fi este sau functieinitiala sau se obtine prin compunere din unele fj cu j < i sau se obtineprin recursie primitiva din doua functii fj , j < i.

Definitia 11.6 Un sir de tipul celui precedent ıl numim definitie primitivrecursiva a lui f .

Exemplu 11.7 Fie f : Nn → N element dintr-o clasa ınchisa primitvrecursiv C si definim g : Nm → N prin g(x1, ..., xm) = f(y1, ..., yn) undeyi este sau o constanta sau xj pentru un j fixat. Atunci g ∈ C deoareceg = f ◦ (h1, ..., hm) cu hj sau functie constanta (care este primitiv recursiva;vezi Ex. 10.?) sau o functie πkj .

Propozitia 11.8 Fie C o clasa ınchisa primitiv recursiv si g ∈ C deforma g : Nn+1 → N. Atunci urmatoarele functii apartin lui C :1)(adunarea repetata) f1 : Nn+1 → N, f1(X, y) =

∑yt=0 g(X, t).

2)(ınmultirea repetata) f2 : Nn+1 → N, f1(X, y) =∏y

t=0 g(X, t).Demonstratie Definitia primitiv recursiva a acestor functii este:

1) f1(x, 0) = g(x, 0), f1(x, y + 1) = f1(x, y) + g(x, y + 1).2) f2(x, 0) = g(x, 0), f2(x, y + 1) = f2(x, y)g(x, y + 1). �

Definitia 11.9 1) Dat n ≥ 1 numim predicat n-ar o afirmatie P (x1, ..., xn)ın n variabile ce este adevarata sau falsa ın functie de valorile variabilelorconsiderate ca elemente din N. Predicatul dat se identifica cu multimeaT (P ) = {x ∈ N;P (x) = adevarata}.2) Data C o clasa ınchisa primitiv recursiv. O submultime A a lui Nn o

numim ın C daca functia caracteristica χA ∈ C . In particular, un predicatn-ar este ın C daca χT (P ) ∈ C .

Cursul 11 63

Pentru rezultatul urmator reamintim ca date predicatele P si Q avem:P ∨Q ınseamna ”P sau Q”, P ∧Q ınseamna ”P si Q” iar ¬P este negatialui P .

Propozitia 11.10 Fie C o clasa ınchisa primitiv recursiva si A,B ⊂ Nn.Daca A si B sunt ın C atunci A∪B,A∩B si Nn\A sunt ın C . In consecinta,date predicatele n-are P si Q din C avem ca P ∨Q,P ∧Q si ¬P sunt ın C .

Demonstratie χA∪B = χAχB, χA∩B = sg(χA + χB) si χcA = 1−χA.�

In cele ce urmeaza x = y ınseamna predicatul P (x, y) adevarat doarcand x si y sunt egale, etc.:

Propozitia 11.11 Predicatele x = y, x = y, x < y, x ≤ y, x > y, x ≥ ysunt primitiv recursive.

Demonstratie χ=(x, y) = sg(|x− y|), χ<(x, y) = sg(x−y). Analog, =este ¬( =), ≤ este < ∨ =, ≥ este ¬(<). �.

Definitia 11.12 1)Fie multimea X si functia partiala f : X → X. Senumeste iteratia sau iterata lui f functia partiala F : X × N → X datade F (x, 0) = f(x) si F (x, n + 1) = f(F (x, n)). Daca f este totala notamF (x, n) = fn(x).2) Spunem ca functia f : Nn → Nk apartine clasei C daca toate functiileπkj ◦ f sunt din C pentru 1 ≤ j ≤ k.3) Clasa C de functii se numeste ınchisa la iteratii daca odata cu functiaf : Nn → Nn din C avem ca si iterata F : Nn+1 → Nn este din C .

Se poate arata ca daca C este ınchisa primitiv recursiv atunci C esteınchisa la iteratii. Suntem interesati ın reciproca acestui fapt.

Propozitia 11.13 Fie C o clasa de functii ce contine functiile initialesi este ınchisa la iteratii. Atunci C este ınchisa primitiv recursiv.

Vom introduce acum cea mai genrala clasa de functii recursive pen-tru care trebuie considerat un nou mod de generare de functii. Fie decif : Nn+1 → N o functie partiala. Vom defini o alta functie g : Nn → Nprin g(x)=cea mai mica valoare a lui y ∈ N pentru care f(x, y) = 0. Da-torita caracterului partial al lui f sunt necesare cateva precizari si de aceeaintroducem:

Definitia 11.14 Functia de minimizare a lui f este functia partialag : Nn → N data de:1) g(x) = r daca f(x, r) = 0 si pentru 0 ≤ s < r, f(x, s) este definita sinenula,

64 M. Crasmareanu

2) g(x) este nedefinita ın caz contrar. Folosim notatia g(x) = µy(f(x, y =0)). Atentie, g poate fi partiala chiar si cand f este totala. Spunem ca amdefinit operatorul de minimizare MIN

Definitia 11.15 Date functiile f si g ca mai sus, spunem ca g se obtinedin f prin minimizare regulata daca f este totala si pentru orice x ∈ Nn

exista y ∈ N asa ıncat f(x, y) = 0. Rezulta ca g este atunci functie totala.

Definitia 11.16 Clasa functiilor recursive ete cea mai mica clasa Cde functii totale care este ınchisa primitiv recursiv si ınchisa la minimizarereguluata i.e. daca f ∈ C si g se obtine din f prin minimizare regulataatunci g ∈ C .

O astfel de clasa exista, fiind de fapt intersectia tuturor claselor ce verificaproprietatile mentionate.

Definitia 11.17 1) O submultime A a lui Nn se numeste recursiva dacaχA este functie recursiva.2) Predicatul n-ar P se numeste recursiv daca multimeaAP = {x ∈ Nn;P (x) = adevarat} este recursiva.

Definitia 11.18 Clasa functiilor partial recursive este cea mai mica clasade functii partiale ce contine functiile initiale si este ınchisa la compunere,primtiv recursivitate si minimizare.

Clasa functiilor partial recursive ce sunt totale este ınchisa primitiv re-cursiv si ınchisa la minimizare regulata; prin urmare contine clasa functiilorrecursive. Deci, o functie recursiva este partial recursiva si totala dar reci-proca nu este valabila.

Exemple 11.19 Functia f : N→ N, f(x) = µy(x(y+1) = 0) este partialrecursiva dar nefiind totala nu este recursiva. In adevar, f(0) = 0 si ın restf este nedefinita.

Definitia 11.20 Se dau functiile f, g : N2 → N. Spunem ca f estefunc tia de minimizare limitata a lui g daca g(x, z) = µy ≤ z(f(x, y) = 0)i.e. valoarea g(x, z) se obtine astfel: daca exista 0 ≤ y0 ≤ z astfel caf(x, 0) > 0, ..., f(x, y0 − 1) > 0 si f(x, y0) = 0 atunci g(x, z) = y0; ın cazcontrar g(x, z) = z + 1. Spunem ca am definit operatorul de minimizarelimitata.

Concluzii: Criteriul de recunoastere a functiilor primitiv re-cursive sau recursive Se dau sirul finit de functii f0, ..., fk si functia f :1) sirul dat ıl numim pr-sir daca orice element al sau este functie initialasau se obtine din precedentele elemente cu operatorii SUP sau REC. Daca

Cursul 11 65

ın plus folosim si operatorul MIN spunem ca avem un r-sir.2) f este primitiv recursiva daca exista un pr-sir cu f ca element final.3) f este recursiva daca exista un r-sir cu f ca element final.

SEMINARUL 11

S11.1 Sa se arate ca urmatoarele functii sunt primitiv recursive:1) functia suma s : N2 → N, s(x, t) = x+ y.2) functia produs sau multiplicare m : N2 → N,m(x, y) = xy.3) functia exponentiala exp : N2 → N, exp(x, y) = xy.4) functia factorial Fac : N→ N, Fac(x) = x!.5) orice functie constanta c : Nn → N, c(x) = c cu c ∈ N fixat.6) functia predecesor Pred : N→ N, P red(x) = x−1 daca x > 1 si Pred(0) =0.7) scaderea proprie − : N2 → N, x−y = max{x− y, 0}.8) functia modul | | : N→ N.9) functia semn sg : N→ N, sg(x) = 1 daca x > 0 si sg(0) = 0.10) sg : N→ N, sg(x) = 0 daca x > 0 si sg(0) = 1.

Rezolvare 1) s(x, 0) = π11(x), s(x, y+1) = s(x, y)+1 = σ◦π33(x, y, s(x, y)).Putem spune ca π11, π33, σ, σ ◦ π33 este o definitie primitiv recursiva pentrus. In cele ce urmeaza vom restrange demonstratia la indicarea recursivitatii.2) m(x, 0) = z(x),m(x, y + 1) = m(x, y) + x.3) exp(x, 0) = 1, exp(x, y + 1) = m(exp(x, y), x).4) Fac(0) = 1, Fac(x+ 1) = m(Fac(x), x+ 1).5) Sa consideram n = 1; atunci functia constanta 0 este z, functia constanta1 este σ ◦ z, functia constanta 2 este σ2 ◦ z, etc. Pentru n general, functiaconstanta c este c′ ◦ πn1 cu c′ : N→ N functia constanta c.6) Pred(0) = 0, P red(x+ 1) = x = s(x, 0).7) x−0 = x = s(x, 0), x−(y + 1) = Pred(x−y).8) |x− y| = (x−y) + y−x.9) sg(0) = 0, sg(x+ 1) = 1.

S11.2 Sa se arate ca functiile urmatoare sunt primitiv recursive:1) ⌊./.⌋ : N2 → N, ⌊x/y⌋ = cel mai mic numar natural mai mic sau egal cux/y daca y > 0 respectiv ⌊x/0⌋ = 0.2) ⌈./.⌉ : N2 → N, ⌈x/y⌉ = cel ami mic numar natural mai mare sau egal cux/y daca y > 0 respectiv ⌈x/0⌉ = 0.3) rest : N2 → N, rest(x, y) = restul ımpartirii lui x la y daca y > 0 respectivrest(x, 0) = 0.4) prim : N→ N, prim(n) = al n-lea numar prim cu prim(0) = 2.

66 M. Crasmareanu

Rezolvare .

S11.3 .

Rezolvare

Cursul 12

Multimi si limbaje recursivenumerabile

Definitia 12.1 Submultime a A a lui N se numeste recursiv enumerabila (r.e. pe scurt) daca A = ∅ sau exista f : N→ N recursiva asa ıncat A = f(N.Alti autori folosesc denumirea de multime semirecursiva, [15, p. 93]

Observatia 12.2 Notiunea astfel introdusa formalizeaza conceptul demultime listabila deoarece elementele lui A se pot lista: f(0), f(1), ..., printr-o procedura cu un numar finit de instructiuni.

Pentru a caracteriza acest tip de multime consideram functia caracter-istica partiala a lui A, χpA : N → N: χpA(x) = 1 daca x ∈ A si χpA(x) estenedefinita daca x nu apartine lui A.

Propozitia 12.3 Pentru A ⊂ N urmatoarele afirmatii sunt echivalente:1) A este r.e..2) A este domeniul de definitie al unei functii partial recursive g : N→ N.3) functia caracteristica partiala χpA este partial recursive.4) A este imaginea unie functii partial recursive.5) sau A = ∅ sau exista o functie primitiv recursiva f : N → N asa ıncatA = f(N).

Demonstratie 1) ⇒ 2). Daca A = ∅ atunci putem considera A cadomeniu al unei functii g partial recursive avand domeniul vid: spre exemplug(x) = cel mai mic y natural pentru care x+ y+1 = 0. Fie acum A = f(N)cu f recursiva si definim g(x) = cel mai mic y natural pentru care f(y) = x.Avem ca g este partial recursiva si A = dom(g).2 ⇒ 3). Avem χpA = 1−z · g cu z functia zero. Rezulta ca χpA este partialrecursiva fiind obtinuta din g si functii primitiv recursive prin compunere.

67

68 M. Crasmareanu

3) ⇒ 4). Fie f = π11 + (1−χpA), reamintind ca π11 este functia identica peN. Avem concluzia.4) ⇒ 5). Avem existenta functiilor primitiv recursive u : N→ N si v : N2 →N asa ıncat f(x) = u(h(t)) unde h(t) = cel mai mic t pentru care v(x, t) = 0.Sa presupunem acum A nevida si fie a0 ∈ A pentru care definim F : N2 → Nprin:i) F (x, n) = u(r(t)) unde r(t) = cel mai mic t pentru care t ≤ n(v(x, t) = 0)daca exista astfel de t,ii) F (x, n) = a0 ın caz contrar.Avem ca F este primitiv recursiva si F (N2) = A. Fie J : N2 → N bijectiaprimitiv recursiva de la Exercitiul ??. Atunci F ◦ J−1 = F ◦ (K,L) : N→ Neste primitiv recursiva cu imaginea A.5) ⇒ 1). Evident. �

Propozitia 12.4(Kleene) Multimea A ⊂ N este recursiva daca si nu-mai daca A si N \A sunt ambele r.e..

Definitia 12.5 1)Fie X numtime numarabila si φ : X → N o bijectiefixata. Atunci submultimea A a lui X se numeste recursiva(respectiv r.e.)relativ la φ daca φ(A) este recursiva (respectiv r.e.).2) Numim enumerare Godel pentruX o aplicatie injectiva φ : X → N pentrucare φ(X) este recursiva.

Fixam ın cele ce urmeaza multimea finita A de cardinal n si de asemenibijectia {1, ..., n} → A, i → ai. Avem urmatoarele enumerari Godel ale luiA∗:I) φ1(ai1 ...aik) =

∑kj=1 ij(n+ 1)j−1,

II) φ′1(ai1 ...aik) =

∑kj=1 ijn

j ,

III) φ2(ai1 ...aik) = 2k∏k

j=1 pijj unde pj este al j-lea numar prim impar.

Definitia 12.6 Limbajul L peste A se numeste recursiv (respectiv r.e.)daca φ(L) este recursiv (respectiv r.e.) unde φ este φ1, φ

′1 sau φ2.

Fie gramatica G = (VN , VT , S, P ) si A = VN ∪ VT ; presupunem A ={a1, ..., an}. Sa notam productiile P = {α1 → β1, ..., αl → βl} si fie λi = |αi|,µi = |βi|.

Propozitia 12.7 Pentru i ∈ {1, ..., l} exista o functie primitiv recursivafi : N2 → N astfel ca, dacam = φ2(x1...xk) si x1...xk = x1...xr−1αixr+λi

...xkatunci fi(r,m) = φ2(x1...xr−1βr+λi

...xk) respectiv fi(r,m) = m alftel fi(r,m) =m.

Teorema 12.8 Un limbaj de tip 0 este r.e. si reciproc.

Cursul 12 69

Teorema 12.9 Un limbaj de tip 1 este recursiv.

Observatia 12.10 i) Reciproca teoremei precedente nu este adevarata:exista limbaje recursive care nu sunt dependente de context.ii) Fie S ⊂ N multime r.e. ce nu este recursiva si φ : A∗ → N una din enu-merarile Godel precedente. Exista o functie recursiva strict crescatoare f :N→ φ(A∗); atunci f(S) este r.e. si nerecursiva. Mai mult, φ(φ−1(f(S))) =f(S) si deci φ−1(f(S)) este limbaj r.e. nerecursiv.

In concluzie avem schema urmatoare:

L1 ( Lr ( Lr.e. = L0.

cu Lr multimea limbajelor recursive si Lr.e. multimea limbajelor r.e.

Propozitia 12.11 Daca L este un limbaj r.e. atunci la fel este ınchiereasa Kleene L∗.

SEMINARUL 12

S12.1 .

Rezolvare .

S12.2 .

Rezolvare .

S12.3 .

Rezolvare .

S12.4 .

Rezolvare .

S12.5 .

S12.6 .

Rezolvare .

S12.7 .

Rezolvare .

S12.8 .

Rezolvare .

70 M. Crasmareanu

Cursul 13

Entropia, energia si corelatiasurselor de informatie

Definitia 13.1 Numim sursa de informatie o pereche S = (Σ, π) cu Σalfabet si π o distributie de probabilitate pe Σ adica o aplicatie π : Σ→ R+

sastisfacand∑

s∈Σ π(s) = 1. Distributia π o numim pozitiva daca π(s) > 0pentru orice s ∈ Σ.

Observatii 13.2 i) Avem ca π(s) ∈ [0, 1] pentru orice s ∈ Σ.ii) O sursa de informatie poate fi gandita ca un dispozitiv ”black-box” careemite simboluri din Σ fiecare astfel de simbol s fiind emis cu probabilitateaπ(s).iii) Fixam |Σ| = n si notam S = (Σ = (si), π = (πi)), 1 ≤ i ≤ n cu conventiap1 ≥ ... ≥ pn. Vom nota tabelar:

S s1 . . . snπ p1 . . . pn

Exemplul 13.3 πu(s) =1n pentru orice s ∈ Σ este o distributie pozitiva

de probabilitate numita distributia uniforma.

Putem extinde π la monoidul cuvintelor obtinandu-se un morfism de laΣ∗ la monoidul multiplicativ al lui [0, 1], π : Σ∗ → ([0, 1], ·, 1) considerand:i) π(ε) = 0,ii) π(w) = π(w(1))...π(w(k)) pentru orice w ∈ Σk, k ≥ 2.Proprietatea de morfism o interpretam astfel: probabilitatea emiterii unuisimbol este independenta de simbolurile emise anterior; din acest motiv,sursele de informatii astfel definite mai sunt numite fara memorie, cele cumemorie mai fiind numite surse Markov. Obtinem astfel o extindere a lui π

71

72 M. Crasmareanu

la limbaje peste Σ:iii) π(∅) = 0,iv) π(L) =

∑w∈L π(w) daca L este submultime nevida a lui Σ∗.

Numarul real nenegativ π(L) ıl numim π-masura lui L. Astfel, πu-masuralui L o numim indicatorul de cod al lui L.

Definitia 13.4 Limbajul produs L1L2 se numeste neambiguu daca pen-tru orice w ∈ L1L2 exista cuvintele unice u ∈ L1 si v ∈ L2 asa ıncat w = uv.

Propozitia 13.5 1) π(Σk) = 1 pentru orice k ≥ 1.2) π(∪i∈ILi) ≤

∑i∈I π(Li) pentru orice familie Li, i ∈ I cel mult numrabila

de submultimi ale lui Σ∗ cu urmatorea conventie: daca exista i ∈ I asa ıncatπ(Li) = ∞ atunci π(∪i∈I) = ∞. Daca familia Li are multimile disjuncteatunci avem egalitate.3) π(L1L2) ≤ π(L1)π(L2). Daca produsul L1L2 este neambiguu atunci avemegalitate.4) π(L∗) ≤

∑i≥0 π(L

n) ≤∑

i≥0(π(L))n cu conventia: π(L) = ∞ implica

π(L∗) =∞.

Conceptul de entropie ca masura a informatiei si a gradului de incerti-tudine, a fost introdus ın 1948 de catre Claude Shannon. Aceasta notiuneeste profund analoaga conceputului similar din termodinamica unde a fostintrodus de catre Clausius ın 1864 ca masura a gradului de dezordine al unuisistem fizic.

Deoarece din punct de vedere matematic, informatia furnizata de sim-bolul sk ∈ Σ este Ik = − log pk rezulta ca media ponderata a informatiilorfurnizate de sursa data este:

Definitia 13.6 Se numeste entropie a sursei S numarul real nenegativ:

H(π) = −n∑

i=1

pi log pi

unde logaritmul este ın baza 2 si avem conventia 0 · log 0 = 0. Unitatea demasura a entropiei este ”biti/simbol”.

Alegerea bazei 2 se poate considera ca fiind neimportanta matematicdatorita proprietatii de schimbare a bazei logaritmilor si este impusa dinpunct de vedere tehnic de utilizarea calculului binar ın procesarea datelorde catre calculatoare.

Lema 13.7 Daca b > 0 si x > 0 atunci logb x ≤ x− 1 cu egalitate doarpentru x = 1.

Cursul 13 73

Propozitia 13.8 Inegalitatea Gibbs Fie numerele reale (pi, qi), 1 ≤i ≤ n satisfacand:i) 0 ≤ pi, qi ≤ 1,ii)

∑ni=1 qi ≤ 1 =

∑ni=1 pi.

Atunci: −∑n

i=1 pi log pi ≤ −∑n

i=1 pi log qi. Avem egalitate daca si numaidacaa pi = qi pentru totti i ∈ Nn.

Corolar 13.9 Pentru orice sursa de n informatii avem: 0 ≤ H(π) ≤log n = H(πu).

DemonstratieAvemH(πu) = −∑n

i=11n log 1

n = − log 1n = log n. Deoarece

pi ∈ [0, 1] avem −pi log pi ≥ 0 si rezulta membrul stang. Pentru membruldrept aplicam inegalitatea Gibbs cu qi =

1n , 1 ≤ i ≤ n. �

Cazurile de egalitate pentru inegalitatea precedenta sunt precizate de:

Propozitia 13.10 i) H(π) = 0 daca si numai daca p1 = 1.ii) H(π) = logn daca si numai daca π = πu.

Demonstratie i) H(π) = 0 daca si numai pentru orice i ∈ Nn avempi log pi = 0. Cum nu putem avea ca toti pi sunt nuli deoarece suma loreste 1 rezulta ca trebuie sa existe macar un indice i asa ıncat pi = 1. Dinordonarea probabilitatilor pi rezulta p1 = 1.ii) rezulta din cazul de egalitate al Inegalitatii Gibbs. �

Observatia 13.11 In termodinamica unui sistem fizic izolat, o stare deechilibru este caracterizata de entropie maxima. Prin analogie, am puteanumi distributia uniforma ca fiind starea de echilibru ”informational” alsursei date, toate cele n simboluri (stari) fiind la fel de probabile.

Definitia 13.12 Se dau sursele de informatie S1 = (Σ1, {pi}, i ∈ I), S2 =(Σ2, {qj}, j ∈ J). Numim produsul lor sursa S1S2 = (Σ1×Σ2, {piqj}). (Avemimediat

∑i,j piqj = 1.)

Putem spune ca sursa produs S2 genereaza grupe de cate doua mesajeale sursei S. Analog pentru o putere k ≥ 2 oarecare.

Propozitia 13.13 H(S1S2) = H(S1) +H(S2). In consecinta H(Sk) =kH(S).

Demosntratie −∑

i,j piqj log(piqj) = −∑

i,j piqj log pi−∑

i,j piqj log qj =∑j qjH(S1) +

∑i piH(S2). �

Definitia 13.14 Pentru sursa data initial definim:1) redundanta R = log n−H(π),

2) eficienta η = H(π)logn .

74 M. Crasmareanu

Exemplul 13.15 (n=2) Notand p1 = p avem:

S s1 s2π p 1− p

i) H(p, 1− p) = η = −p log p− (1− p) log(1− p),ii) R = 1 + p log p+ (1− p) log(1− p).

Inspirat de expresia energiei cinetice care este suma patratelor vitezelor,matematicianul roman Octav Onicescu a introdus ın 1964 conceptul urmator:

Definitia 13.16 Numim energia sursei date numarul real strict pozitiv:

E(π) =n∑

i=1

p2i .

Propozitia 13.17 i) E(πu) =1n ≤ E(π) ≤ 1.

ii) E(π) = 1n daca si numai daca π = πu.

iii) E(π) = 1 daca si numai daca p1 = 1.iv) E(S1S2) = E(S1)E(S2).

Demonstratie i) Faptul ca E(πu) = 1n este imediat ca si inegalitatea

din dreapta deoarece pi fiind subunitare avem E(π) ≤∑n

i=1 p1. Pentru aarata inegalitatea din stanga fie xi = pi − 1

n ; rezulta∑n

i=1 xi = 0. AvemE(π) = 1

n +∑n

i=1 x2i .

ii) Avem egalitate ın stanga daca si numai daca toti xi sunt nuli.iii) Avem egalitate ın dreapta daca si numai daca p2i = pi ceea ce revine lap1 = 1 si p2 = ... = pn = 0.iv)

∑i,j(piqj)

2 = (∑p2i )(

∑q2j ) din independenta celor doua surse. �

Definitia 13.18 Date sursele S1 si S2 de aceeasi dimensiune n numim:i) corelatia lor numarul real nenegativ C(π1, π2) =

∑ni=1 piqi.

ii) coeficientul de corelatie numarul real nenegativ CC(π1, π2) =C(π1,π2)√Eπ1)E(π2)

.

Propozitia 13.19 CC(π1, π2) ≤ 1 = CC(π, π) cu egalitate daca sinumai daca π1 = π2.

Demonstratie Faptul ca CC(π, π) = 1 este imediat iar inegalitatea esteexact inegalitatea Cauchy-Buniakowski-Schartz (CBS) din teoria produselorscalar. Avem egalitate ın inegalitatea CBS daca si numai daca vectoriin-dimensionali π1, π2 sunt coliniari adica exista numarul real λ asa ıncatπ2 = λπ1. Dar din

∑p1i =

∑p2i = 1 rezulta λ = 1. �

Cursul 13 75

SEMINAR 13

S13.1 Se da o sursa cu n = 5 si p1 =12 , p2 =

14 , p3 =

18 , p4 = p5 =

116 . Se

cere entropia, redundanta, eficienta si energia acestei surse.

Rezolvare H = 12 · 1 +

14 · 2 +

18 · 3 +

116 · 4 · 2 = 15

8 = 1.875 biti/simbol.R = log 5−H = 2.3219− 1.8750 = 0.4469, η = 1.875

2.3219 = 0.8075,E = 1

4 + 116 + 1

64 + 2256 = 0.25 + 0.0625 + 0.0156 + 0.0078 = 0.3359

S13.2 .

Rezolvare .

S13.3 .

Rezolvare .

S13.4 .

Rezolvare .

S13.5 .

Rezolvare .

S13.6 .

Rezolvare .

S13.7 .

Rezolvare .

76 M. Crasmareanu

Cursul 14

Compilatoare 1: Analizalexicala

Definitia 14.1 i) Un translator este un program (cutie neagra) care primestela intrare un text scris ıntr-un limbaj de programare, limbajul sursa, si pro-duce la iesire un text echivalent scris ın alt limbaj de programare, limbajulobiect.ii) Daca limbajul sursa este un limbaj de nivel ınalt iar limbajul obiect esteun limbaj de nivel inferior (limbaj de asamblare sau cod masina), atuncitranslatorul respectiv se numeste compilator.

Procesul de compilare a unui program are loc ın mai multe faze. O fazaeste o operatie unitara ın cadrul careia are loc transformarea programuluisursa dintr-o reprezentare ın alta.

Principalele faze ale unei compilari sunt:1) Analiza lexicala: textul sursa este preluat sub forma unei secvente de car-actere care sunt grupate apoi ın entitati numite atomi; atomilor li se atribuiecoduri lexicale, astfel ca, la iesirea acestei faze, programul sursa apare ca osecventa de asemenea coduri. Exemple de atomi: cuvinte cheie, identifica-tori, constante numerice, semne de punctuatie etc.2) Analiza sintactica are ca scop gruparea atomilor rezultati ın urma anal-izei lexicale ın structuri sintactice. O structura sintactica poate fi vazuta caun arbore ale carui noduri terminale reprezinta atomi, ın timp ce nodurileinterioare reprezinta siruri de atomi care formeaza o entitate logica . Exem-ple de structuri sintactice: expresii, instructiuni, declaratii etc.3) Pe durata analizei sintactice, de obicei are loc si o analiza semantica,

ceea ce ınseamna efectuarea unor verificari legate de:-compatibilitatea tipurilor datelor cu operatiile ın care ele sunt implicate,

77

78 M. Crasmareanu

-respectarea regulilor de vizibilitate impuse de limbajul sursa.4) Generarea de cod intermediar: ın aceasta faza are loc transformarea

arborelui sintactic ıntr-o secventa de instructiuni simple, similare macroin-structiunilor unui limbaj de asamblare. Diferenta dintre codul intermediarsi un limbaj de asamblare este ın principal aceea ca ın codul intermediar nuse specifica registrele utilizate ın operatii. Exemple de reprezentari pentrucodul intermediar: instructiunile cu trei adrese, notatia postfix, etc. Codulintermediar are avantajul de a fi mai usor de optimizat decat codul masina.5) Optimizarea de cod este o faza optionala al carei rol este modificarea

unor portiuni din codul intermediar generat astfel ıncat programul rezultatsa satisfaca anumite criterii de performanta vizand timpul de executie sau/sispatiul de memorie ocupat.6) Generarea codului final presupune transformarea instructiunilor coduluiintermediar (eventual optimizat) ın instructiuni masina (sau de asamblare)pentru calculatorul tinta (cel pe care se va executa programul compilat).In afara de aceste actiunile, procesul de compilare mai include urmatoarele:7) Gestionarea tabelei de simboluri: tabela de simboluri este o structura dedate destinata pastrarii de informatii despre simbolurile (numele) care aparın programul sursa; compilatorul face referire la aceasta tabela aproape ıntoate fazele compilarii. 8) Tratarea erorilor: un compilator trebuie sa fiecapabil sa recunoasca anumite categorii de erori ce pot apare ın progra-mul sursa; tratarea unei erori presupune detectarea ei, emiterea unui mesajcorespunzator si revenirea din eroare, adica, pe cat posibil, continuarea pro-cesului de compilare pana la epuizarea textului sursa, astfel ıncat numarulde compilari necesare eliminarii tuturor erorilor dintr-un program sa fie catmai mic. Practic, exista erori specifice fiecarei faze de compilare.

Derularea procesului de compilareFazele unui proces de compilare se pot ınlantui, ın principiu, ın doua mod-uri:-la iesirea/finalul fiecarei faze se va genera un fisier intermediar continandforma de reprezentare a programului sursa rezultata ın faza respectiva, fisierce va constitui intrare pentru faza urmatoare. In acest caz, ın fiecare faza vaavea loc cel putin o parcurgere a programului sursa, de la ınceput la sfarsit.O asemenea parcurgere se numeste trecere.-doua sau mai multe faze de compilare se ıntrepatrund astfel ıncat ele sa seexecute printr-o singura trecere.Aplicarea uneia sau alteia dintre aceste doua modalitati depinde de naturalimbajului compilat precum si de mediul ın care urmeaza sa ruleze com-pilatorul. Astfel, ın sprijinul proiectantilor de compilatoare au fost create

Cursul 14 79

instrumente software precum generatoarele de analizoare lexicale si sintac-tice, generatoarele de compilatoare sau sistemele de scriere a translatoarelor.Aceste instrumente sunt programe care produc compilatoare sau parti dincompilatoare, primind la intrare o specificare a limbajului sursa precum sia calculatorului tinta.

Un analizor lexical citeste textul sursa caracter cu caracter si-l trans-forma ıntr-o secventa de unitati primitive (elementare) numite unitati lexi-cale, ın engleza tokens.

O unitate lexicala descrie o secventa de caractere cu o anumita semnificatiesi este tratata ca o entitate logica. Astfel, pentru fiecare limbaj de progra-mare se stabilesc, atunci cand se proiecteaza acel limbaj, unitatile lexicalecorespunzatoare.

Majoritatea limbajelor utilizeaza urmatoarele unitati lexicale:1) constante; exemplu: 737,−68.94, 3e+ 2,2) identificatori; exemplu: alpha, un ident,3) operatori; exemplu: +, ∗, /, <,>,4) cuvinte rezervate; exemplu: begin, while,5) semne speciale; de exemplu: ; . : .

Problema analizei lexicale comporta cel putin doua aspecte:I) gasirea unei modalitati de descriere a unitatilor lexicale; astfel, se constataca expresiile regulate sunt instrumentele ce pot descrie orice unitate lexicala.II) recunoasterea acestor unitati lexicale ceea ce constituie analiza lexicalapropriu zisa; daca descrierea se face prin intermediul expresiilor regulateatunci mecanismul de recunoastere este automatul finit determinist conformTeoremei 5.8.

Unitatile lexicale sunt de doua categorii:a) unitati ce descriu un sir anume de caractere; exemplu if, while, ++ := ;b) unitati ce descriu o clasa de siruri: identificatori, constante, etc.In al doilea caz, vom considera o unitate lexicala ca fiind o pereche (tipul,valoarea).

Pentru unitati lexicale ce descriu un sir anume, prin conventie tipuleste acel sir iar valoarea coincide cu tipul. Astfel, caracterul ( este de tipparanteza stanga iar alpha este unitate lexicala de tip identificator care arevaloarea alpha. Mai spunem ca alpha este o instanta a tokenului identificatorsau lexem.LEXEM ∼e 1) Cuvant sau parte de cuvant care serveste ca suport minimalal semnificatiei; morfem lexical. 2) Unitate de baza a vocabularului carereprezinta asocierea unuia sau a mai multor sensuri; cuvant; unitate lexicala.din fr. lexeme. Sursa : NODEX (341523)

80 M. Crasmareanu

limbaje cu compilator C, FORTRAN, Pascal, ALGOL, BASIC

Pagini Web utile:1) http://en.wikipedia.org/wiki/Compiler2) http://ro.wikipedia.org/wiki/GNU Compiler Collection

Bibliografie

[1] Capra, F., Conexiuni ascunse, Ed. Tehnica, Bucuresti, 2004.

[2] Cazacu, C., Teoria calculabilitatii efective, Ed. Univ. ”Al. I. Cuza”, Iasi,1996.

[3] Chiswell, I., A Couse in Formal Languages, Automata and Groups,Universitext, Springer-Verlag, London, 2009.

[4] Grigoras Gh., Limbaje formale si tehnici de compilare, Ed. Univ. ”Al.I. Cuza”, Iasi, 1985.

[5] Grigoras Gh., Constructia compilatoarelor. Algoritmi fundamentali, Ed.Univ. ”Al. I. Cuza”, Iasi, 2005.

[6] Gontineac M., Limbaje formale si automate, Note de curs,http://www.math.uaic.ro/∼mgonti/.

[7] Holcombe W. M. L., Algebraic automata theory, Cambridge studies inadvanced mathematics 1, Cambridge Univ. Press, 1982.

[8] Howie J. M., Automata and Languages, Claredon Press, Oxford, 1991.

[9] Ivan Gh.; Ivan M., Concepte algebrice fundamentale ın studiul limba-jelor formale. Teorie si exercitii, Editura de Vest, Timisoara, 2006.

[10] Jucan, T.; Andrei, S., Limbaje formale si teria automatelor: Teorie sipractica, Ed. Univ. ”Al. I. Cuza”, Iasi, 2002.

[11] Onicescu, O.; Stefanescu V., Elemente de statistica informationalcuaplicatii, Ed. Tehnica, Bucuresti, 1979.

[12] Orman G., Limbaje formale, Ed. Tehnica, Bucuresti, 1982.

[13] Paun, Gh., Gramatici contextuale, Ed. Academiei, Bucuresti, 1982.

81

82 Bibliografie

[14] Simovici D., Limbaje formale si tehnici de compilare, EDP, Bucuresti,1978.

[15] Srivastava, S. M., A course in mathematical logic, Universitext,Springer-Verlag, 2008.

[16] Serbanati L. D., Limbaje de programare si compilatoare, Ed. Academiei,Bucuresti, 1987.

[17] Tomescu I., Introducere ın combinatorica, Ed. Tehnica, Bucuresti, 1972.(Cap. 8, p. 93.)

[18] Tiplea F. L., Fundamentele algebrice ale informaticii, Ed. Polirom, Iasi,2006.

Index

π-masura unui limbaj, 72

k-cuvant, 1

ınchiderea Kleene a unui limbaj, 8

ınchiderea pozitiva a unui limbaj, 8

ınmultirea repetata, 62

semiautomat (automat) conex, 41

actiune a unui grup pe o multime, 45

actiune libera, 49

actiune tranzitiva, 49

adunarea repetata, 62

alfabet, 1

alfabetul binar, 1

alfabetul minimal al unui limbaj, 8

alfabetul zecimal, 1

algebra Boole, 28

analiza lexicala, 77

analiza semantica, 78

analiza sintactica, 77

analizor lexical, 79

aplicatia de interpretare, 15

automat, 29

automat autonom, 36

automat finit determinist (AFD), 29

automat finit nedeterminst (AFN), 29

automat minimal, 40

automat nedeterminist, 29

automate echivalente, 33

automate izomorfe, 40

automatul ciclic, 38

coeficientul de corelatie a doua surse,74

compilator, 77

compunere de functii partiale, 61

concatenarea cuvintelor, 2

congruenta pe un (semi)automat, 41

congruenta pe un semigrup, 6

congruenta Rees, 22

congruenta generata de o relatie, 21

congruenta Myhill, 44

congruenta totala, 21

corelatia a doua surse, 74

cuvant nevid, 1

cuvant recunoscut de un automat, 30

cuvantul vid, 1

cuvinte egale, 2

cvasicongruenta, 9

definitie primitiv recursiva, 62

derivare ıntr-o gramatica, 54

distanta Hamming pe k-cuvinte, 14

distributia uniforma de probabilitate,71

distributie de probabilitate, 71

ecuatia unui monoid, 23

eficienta unei surse de informatie, 73

energia unei surse de informatie, 74

entropie, 72

enumerare Godel, 68

evolutia limbajului, 17

expresie ambigua, 16

83

84 Index

expresie regulata, 15

expresii regulate echivalente, 16

F-varietate de monoizi, 23

formula Burnside, 49

functia caracteristica a unei submultimi,39

functia caracteristica partiala a uneimultimi, 67

functia de minimizare, 64

functia de minimizare limitata, 64

functia exponentiala, 65

functia factorial, 65

functia izoparametrica a unui grupfinit generat, 59

functia modul, 65

functia produs (multiplicare), 65

functia semn, 65

functia suma, 65

functie partiala, 61

functie partial recursiva, 64

functie primitiv recursiva, 62

functie recursiva, 64

functie totala, 61

functii initiale, 62

generare de cod intermediar, 78

generarea codului final, 78

generatori ai unui semigrup, 3

gestionarea tabelei de simboluri, 78

gramatica, 53

gramatici echivalente, 54

grup automat, 59

grup de izotropie, 47

grup de transformari, 45

grup liber, 57

grupul bijectiilor unei multimi, 5, 45

grupul ciclic de ordin 2, 51

grupul ciclic de ordinul n-definitia,52

grupul ciclic de ordinul n-prezentare,58

grupul diedral, 60grupul diedral infinit, 60grupul simetric, 45

ideal ıntr-un monoid, 22idempotent, 5ierarhia Chomsky a gramaticilor, 54indicatorul de cod al unui limbaj, 72inegalitatea Gibbs, 73iterata unei functii, 63

latice, 26latice booleana, 28latice complementata, 27latice distributiva, 28latice marginita, 27laticea submultimilor unei multimi,

26lema de pompare, 25limbaj (formal), 7limbaj acceptat de un automat, 30limbaj independent la concatenare, 8limbaj produs neambiguu, 72limbaj r.e. nerecursiv, 69limbaj recognoscibil, 30limbaj recunoscut de un monoid, 16limbaj recursiv, 68limbaj regulat, 9limbajul generat de o gramatica, 54limbajul obiect al unui compilator,

77limbajul sursa al unui compilator, 77litere, 1lungimea unui cuvant, 1

metrica=distanta, 14minimizare regulata, 64monoid, 2monoid banda, 22

Index 85

monoid liber, 3monoid Rees, 22monoid semilaticeal, 25monoidul cuvintelor, 2multime listabila, 67multime periodica, 26multime recognoscibila, 43multime recursiv enumerabila (semire-

cursiva), 67multime recursiva, 64

numarul literelor dintr-un cuvant, 4

obiect initial, 3operatii boolene cu limbaje, 8operatorul de minimizare limitata, 64operatorul de minimizare MIN, 64operatorul de recursie primitiva REC,

61operatorul de superpozitie SUP, 61optimizare de cod, 78orbita, 47

palindrom, 17permutare ciclica =k-ciclu, 49pr-sir, 65predicat, 62predicat primitiv recursiv, 63predicat recursiv, 64prefix, 9prefix propriu, 9prezentarea grupurilor prin genera-

tori si relatii, 57problema cuvintelor, 58proprietatea de universalitate a

monoizilor liberi, 3

r-sir, 65recursie primitiva, 61redundanta unei surse de informatie,

73

reguli de simplificare ın monoidul cu-vintelor, 4

reprezentarea tabelara a automatelor,31

reversul unui cuvant, 17

ridicarea la putere a unui simbol, 2

RL-functie, 24

scaderea proprie, 65

semiautomat, 41

semiautomat (automat) perfect, 41

semiautomatul (automatul) grup, 41

semigrup, 2

semigrup liber, 3

semilatice, 27

simboluri, 1

spatiul proiectiv real, 52

stari k-echivalente, 39

stari echivalente, 39

stabilizator, 47

stare accesibila a unui automat, 35

stare ambigua a unui automat, 30

stare nedefinita a unui automat, 30

stare productiva a unui automat, 36

structura automata pentru un grup,59

structura rationala pentru un grup,58

subcuvant, 9

subcuvant propriu, 9

subgrup, 4

sublatice, 27

submonoid, 4

subsemigrup, 4

sufix, 9

sufix propriu, 9

sumatorul modulo n, 41

sursa de informatie, 71

sursa produs de informatii, 73

86 Index

teorema Kleene, 15tipul unei unitati lexicale, 79translator, 77transpozitie, 49tratarea erorilor la compilare, 78trim, 36

unitati lexicale, 79

valoarea unei unitati lexicale, 79varietate de monoizi, 22VRL-functie, 24

Complemente de matematic a pentru Computer …mcrasm/depozit/Comp_BOOK.pdfCursul 1 Monoidul...

Documents

Transcript of Complemente de matematic a pentru Computer …mcrasm/depozit/Comp_BOOK.pdfCursul 1 Monoidul...