Expresii Regulate si 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 si Gramatici Regulate - Pagina 1
Expresii Regulate si Gramatici Regulate - Pagina 2
Expresii Regulate si Gramatici Regulate - Pagina 3
Expresii Regulate si Gramatici Regulate - Pagina 4
Expresii Regulate si Gramatici Regulate - Pagina 5
Expresii Regulate si Gramatici Regulate - Pagina 6
Expresii Regulate si Gramatici Regulate - Pagina 7
Expresii Regulate si Gramatici Regulate - Pagina 8
Expresii Regulate si Gramatici Regulate - Pagina 9
Expresii Regulate si Gramatici Regulate - Pagina 10
Expresii Regulate si Gramatici Regulate - Pagina 11
Expresii Regulate si Gramatici Regulate - Pagina 12
Expresii Regulate si Gramatici Regulate - Pagina 13
Expresii Regulate si Gramatici Regulate - Pagina 14
Expresii Regulate si Gramatici Regulate - Pagina 15
Expresii Regulate si Gramatici Regulate - Pagina 16
Expresii Regulate si Gramatici Regulate - Pagina 17
Expresii Regulate si Gramatici Regulate - Pagina 18
Expresii Regulate si Gramatici Regulate - Pagina 19
Expresii Regulate si Gramatici Regulate - Pagina 20

Conținut arhivă zip

  • Expresii Regulate si Gramatici Regulate.doc

Alții au mai descărcat și

Autocad pentru Incepatori

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

Sisteme de Operare

1.1 Sisteme de calcul. Structura sistemelor de calcul Sistemele de operare sunt colecţii de programe existente pe sistemele de calcul . Prin...

Proiectarea unei Interfete pentru Comanda unui Motor de Curent Continuu Folosind un Microcontroler

Microcontrolerele Siemens SAB 80C166 Caracteristici Firma Siemens a dezvoltat propria linie de microcontrolere. Aceasta cuprinde microcontrolere...

Curs Informatica

Un calculator personal este alcătuit din două categorii de componente: hardware şi software. Hardware-ul reprezintă ansamblul elementelor fizice,...

Programarea Orientata spre Obiecte - Limbajul Java

1. INTRODUCERE IN PROGRAMAREA ORIENTATA SPRE OBIECTE OBIECTE D. Un obiect este un un mod simplificat de a identifica într-un program un lucru, o...

Circuite Logice Programabile

1. Recapitulare noţiuni de descriere în VHDL, sinteză şi implementare în circuitele logice programabile 1. 1. Introducere VHDL-ul este un limbaj...

Interfa Grafica in Java

Toate interfetele extind interfata java.util.EventListener Un obiect A care trebuie sa intercepteze evenimente de un anumit tip produse de un...

Proiectare Asistata de Calculator Partea 1

Capitolul 1 Introducere Proiectarea asistată de calculator s-a dezvoltat în contextul dezvoltării resurselor hard şi soft oferite de...

Ai nevoie de altceva?