Expresii regulate și gramatici regulate

In acest capitol vom arata faptul ca un limbaj regulat (acceptat de un automat finit) poate fi descris prin expresii regulate. O expresie regulata se descrie prin string-uri formate cu simboluri din , folosind paranteze () pentru grupare, precum si operatorii +,  si *. Operatorul + este folosit pentru reuniune, operatorul  este folosit pentru concatenare, iar operatorul * inseamna “de ori cate ori“.

Formal, operatorii + si  se definesc pentru doua multimi de simboluri A si B astfel:

A+B = AB

AB = {vw | v  A, w  B}

Practic, pentru AB se calculeaza produsul cartezian dintre A si B, cu deosebirea ca fiecare element din AB nu reprezinta o pereche ordonata (intre paranteze) de elemente din A si B, ci reprezinta un nou simbol obtinut prin alipirea celor doua.

Daca A = {, ab} si B = {a, b, ab}, atunci avem:

A+B = {, ab, a, b}

AB = {a, b, ab, aba, abb, abab}

Formal, operatorul * (Kleene star) se defineste pentru o multime de simboluri M astfel:

, unde .

Evident, in definitia de mai sus, Mi contine cuvintele de lungime i formate cu simboluri din multimea M. Multimea M* este infinita, daca M nu este vida.

Daca M = {a, b}, atunci avem:

M* = {, a, aa, aaa, …., b, bb, bbb, ab, aab, …., abb, abbb, ….}.

De exemplu, expresia (a+bc)* reprezinta cuvintele formate cu simbolul a si/sau simbolurile alipite bc luate de oricate ori. Expresia descrie limbajul format din cuvintele , a, bc, abc, bca, aa, bcbc etc.

Definitia 1: Pornind de la un alfabet dat , o expresie regulata se construieste astfel:

1. , {} si {a} (a  ) sunt expresii regulate. Aceste se numesc expresii regulate primitive.

2. Daca r1 si r2 sunt expresii regulate, atunci r1 + r2, r1  r2 sunt expresii regulate.

3. Daca r este expresie regulata, atunci r* si (r) sunt expresii regulate.

4. Un string este o expresie regulata daca si numai daca poate fi derivata din expresii regulate primitive in urma aplicarii de un numar finit de ori a regulilor 2 si 3.

Propozitia 1: Cateva proprietati imediate ale operatorilor +,  si *:

1. Operatia + este comutativa si asociativa, iar  nu este comutativa, dar este asociativa.

2. r +  =  + r = r, pentru oricare expresie regulata r.

3. r   =   r = 

4. r  {} = {}  r = r

5. * = {}.

6. Operatia  este distributiva fata de +, adica r1(r2+ r3) = r1 r2 + r1 r3, pentru orice expresii regulate r1, r2, r3.

Pentru o expresie regulata r vom nota cu L(r) limbajul asociat expresiei r.

Definitia 2: Limbajul L(r) asociat expresiei r este definit dupa regulile:

1.  este expresia regulata cu care se noteaza multimea vida

2.  este expresia regulata cu care se noteaza multimea {}.

3. Pentru fiecare a   cu a se noteaza expresia regulata {a}.

Pentru fiecare expresii regulate r1 si r2 avem:

4. L(r1 + r2) = L(r1)  L(r2)

5. L(r1  r2) = L(r1)L(r2).

Pentru fiecare expresie regulata r avem:

6. L((r)) = L(r)

7. L(r¬*) = L(r)*.

Exemplu: L(b*  (a + b)) = L(b*)L(a + b) = L(b)*(L(a)  L(b)) = L(b)*{a, b} = {a, ba, bba, bbba, …., b, bb, bbb, bbbb}, adica este limbajul format cu cuvintele ce incep cu oricate simboluri b si se termina cu a sau b. Prin “oricate” se intelege niciunul sau unul sau doua sau trei sau patru etc.

Observatie: Pentru operatorii +,  si * stabilim oridinea de aplicare (precedenta) astfel: * se aplica primul, apoi  si in final + (daca lipsesc parantezele). De asemenea, putem omite  in definirea expresiilor regulate. In exemplul de mai sus puteam descrie expresia regulata asociata limbajului fara  astfel b*(a+b).