Expresii regulate și gramatici regulate

Curs
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 20 în total
Cuvinte : 4338
Mărime: 54.54KB (arhivat)
Cost: Gratis

Extras din document

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).

Preview document

Expresii regulate și gramatici regulate - Pagina 1
Expresii regulate și gramatici regulate - Pagina 2
Expresii regulate și gramatici regulate - Pagina 3
Expresii regulate și gramatici regulate - Pagina 4
Expresii regulate și gramatici regulate - Pagina 5
Expresii regulate și gramatici regulate - Pagina 6
Expresii regulate și gramatici regulate - Pagina 7
Expresii regulate și gramatici regulate - Pagina 8
Expresii regulate și gramatici regulate - Pagina 9
Expresii regulate și gramatici regulate - Pagina 10
Expresii regulate și gramatici regulate - Pagina 11
Expresii regulate și gramatici regulate - Pagina 12
Expresii regulate și gramatici regulate - Pagina 13
Expresii regulate și gramatici regulate - Pagina 14
Expresii regulate și gramatici regulate - Pagina 15
Expresii regulate și gramatici regulate - Pagina 16
Expresii regulate și gramatici regulate - Pagina 17
Expresii regulate și gramatici regulate - Pagina 18
Expresii regulate și gramatici regulate - Pagina 19
Expresii regulate și gramatici regulate - Pagina 20

Conținut arhivă zip

  • Expresii Regulate si Gramatici Regulate.doc

Alții au mai descărcat și

Autocad pentru începători

C1.1.CONCEPTUL DE CAD TERMINOLOGIE - COMPUTER AIDED ENGINEERING -CAE-vizeazăetapeledecercetare,inovaresiconcepţie; - COMPUTER AIDED DRAWING/...

Calculatoare

Răspunsuri Arbori şi păduri 1. D. O relaţie de încredere oferă posibilitatea folosirii în comun doar a resurselor între domenii; ea nu oferă în...

Securitatea informațională a business-ului

Lecţia 1 Introducere în securitatea informaţională 1.Informaţia ca obiect de valoare şi protecţie 4 2.Conceptele de bază ale Securităţii...

Informație și Document în Societatea Cunoașterii

Introducere I. Documente electronice – definire, caracteristici şi tipologie I. 1. Delimitări terminologice I. 2. Document text I. 3....

Evaluarea eficienței investițiilor în IT&C

Capitolul 1.BAZE METODOLOGICE ALE EVALURII EFICIENŢEI INVESTIŢIILOR ÎN IT&C 1.1. Evaluarea eficienţei în condiţiile specifice investiţiilor din...

Arhitectura microcalculatoarelor tip IBM-PC. configurații, caracteristici. reguli de instalare și exploatare

. Notiuni introductive Un sistem de calcul poate contine sute sau mii de componente individuale (circuite integrate, diode, rezistoare,...

Bazele Informaticii - Curs 1

I. SISTEME INFORMATICE I. 1. NOTIUNEA DE “SISTEM” În general, un sistem se defineste ca fiind un ansamblu de elemente fizice si logice...

Abordare aplicativă - sistemul de gestiune al bazelor de date Microsoft Access 2000

Concepte de bază Un sistem de baze de date: este un sistem computerizat de păstrare a înregistrărilor al cărui scop principal este să stocheze...

Te-ar putea interesa și

Limbă și stil în opera lui Tudor Arghezi

INTRODUCERE Motto: ,,Stilul nu este ingredientul târziu al ideii, ci fratele ei geamăn". Pentru realizarea acestei lucrări de licență m-am axat...

Învățământul Primar

CAP. I. Introducere 1.1. Învăţământul primar în contextul actual „Formarea şi dezvoltarea profilului moral cu dimensiune axiologică a...

Predicatul

CAPITOLUL I INTRODUCERE În anul 1951, când în planurile de învatamânt ale facultatilor filologice s-a introdus disciplina Limba româna...

Rolul Jocului

1. CONSIDERAŢII PRELIMINARE Învăţământul preşcolar ocupă un loc bine conturat, cu funcţii şi sarcini precise, în viziunea unitară a învăţământului...

Conceptele Fundamentale ale Limbajelor de Programare

INTRODUCERE Obiectul disciplinei: limbajele de programare Obiective: · Studiul conceptelor fundamentale care stau la baza proiectării...

Limbaje Formale și Translatoare

1. Introducere Curs1 LFT Limbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare. Pentru a putea însă folosi limbaje...

Software de Sistem

Cap.1 - INTRODUCERE 1.1 DEFINIŢII Propoziţia simplă este o aserţiune, o afirmaţie, exprimată minimal printr-o acţiune concretă, un predicat,...

Compilatoare

Evolutia vietii este insotita de o permanenta acumulare de experienta statistica, dobandita prin incercari directe ale unor subiecti activi....

Ai nevoie de altceva?