Buna ziua,
Bun venit la o noua intalnire cu automatele si teoria limbajelor formale.
Aveti nevoie de capitolul al treilea, [pg 75 -79, exclusiv 79]
EXPRESII REGULARE (comentarii in sprijinul intelegerii lor)
Cititi introducerea de la pagina 75 ? Ce ati inteles de aici ? Ce nu ne spune autorul ?
Dar totusi de ce s-a ajuns la aceste faimoase expresii regulare ? Scopul lor conteza ?
Intai pentru ca programarea defensiva are limitele ei. Este usor sa eviti problema anului 2000, daca de exemplu testezi valorile anilor care sunt primiti de o functie. Este usor sa vezi ca o data nu pica pe 30 februarie, comparand fiecare zi cu intervalele de valori posibile din lunile corespunzatoare.
Fiindca sunt comparatii numerice. Dar ce ne facem, cu functiile care proceseaza texte ?
De exemplu daca vrem sa evitam atacuri cum este SQL Injection ?
Ce ne-ar trebui aici ?
Un mod de a testa TEXTELE care sunt introduse in niste functii ale programului, dar aceste texte, aceste stringuri sunt mult mai variate decat numerele, si nici macar nu sunt ordonabile (decat dupa lungime si lexicografic, in ordine de dictionar - dar asta nu prea ajuta).
Ce ne trebuie ?
Un sistem de verificare si comparare a textelor, pentru a vedea daca niste texte sunt din niste multimi de texte posibile. Si care sa fie si un sistem rapid.
Putem numi aceste multimi de texte = Limbaje. OK !
Si putem verifica aceste texte cu niste parsere, cum sunt cele generate cu Bison, dar timpul de calcul este prea mare. Nu stiu daca va amintiti, dar la gramaticile monotone timpul de analiza poate fi exponential, la cele de tip 3 (GIC - gramaticile independente de context) poate fi un polinom (grad cel putin 2) de lungimea textului. Si daca stringul de testat are 1024 de litere ? Fac pentru test un milion de operatii ? Intr-o bucla a programului ?
Pe de alta parte automatele au ceea ce ne intereseaza: Viteza. Daca un string are lungimea n, atunci dupa parcurgerea a n-etape, "dupa ce broscuta din poveste face n pasi", cuvantul analizat se termina si stim daca ajung intr-o stare finala.
Timpul de calcul este de O(n).
Abia acum puteti citi:
Paragraful 3.1. [pg 75]
Aici este vorba de acele multimi de texte din care ar putea face parte textele pe care le supunem la test. Clasa acestor multimi nu este lasata in aer, nu este lasata sa fie "sigma stea" - inchiderea alfabetului ci, dat fiind ca automatele sunt echivalente cu gramaticile de tip 3. (teorema anterioara) este o clasa mai mica de texte care poate fi construita inductiv !
Intrebare de control: Ce face definitia 3.1. ?
a) Defineste inductiv multimile de astfel de texte.
b) Defineste recursiv multimile de astfel de texte.
c) Defineste iterativ multimile de astfel de texte.
C. era gresit !
Recapitulare: ce am facut cu paragraful 3.1, definitia 3.1 ?
Am construit inductiv, recursiv daca vreti, colectia multimilor regulare, acele multimi de texte pentru care vom putea testa cu ajutorul automatelor daca textul apartine multimii.
Nota: Remarcati ca nu putem testa in timp liniar apartenenta textului nostru de verificat la ORICE fel de multime.
Pauza 10 min,
In pauza dau consultatii pt licenta... aveti colegi.
Definitia 3.2. [pg 75]
Cititi va rog definitia 3.2 si spuneti ce ati observat !
Intrebare de control:
Care e legatura intre def 3.2 si def 3.1 ?
Intrebare de control:
Care este diferenta ?
De data acesta am inventat o notatie pentru multimi de texte !
Dar care este relatia dintre aceste notatii pentru texte si automatele despre care vorbeam ?
Cititi Observatia de la pagina 75 ! Dati pagina la pagina 78 !
Ce gasiti aici: Felul in care, structural, inductiv, cum deja sunteti obisnuiti,
se construieste automatul care recunoaste textele indicate de expresia regulara.
Pina acum stiam de corespondenta :
O multime regulara <--> O expresie regulara.
Acum stim si de corespondenta :
O multime regulara <--> O expresie regulara --> Un automat care recunoaste textele.
Sa parcurgem impreuna rand cu rand tabelul de la pagina 78.
- In prima coloana este forma expresiei regulare
- In a doua coloana, presupunand ca avem ce ne trebuie, stari sau automate intregi, e construit automatul care accepta acea expresie.
- In a treia sunt observatiile.
Intrebari de control:
- la ce ne-au folosit epsilon tranzitiile ?
Cateva comentarii la acest tabel se regasesc la pagina 76, paragraf 2 de sus, inainte de exemple. Retineti acele notatii: expresiei p+q ii corespunde masina M indice p+q samd.
Intrebare de control:
Care alte astfel de notatii se mai folosesc si ce inseamna ele ?
Ramanem la pagina 76, la exemple:
Exercitiu:
Acoperiti cu o banda de hartie coloana a II-a din tabele si rescrieti pe banda multimea de texte care corespund acelor expresii regulare.
Rescrieti multimile descrise de aceste expresii. V-au iesit ca in carte ?
Sa trecem acum la def 3.3 pg 76.
Intrebare:
De ce este nevoie de o astfel de definitie ?
Raspuns: Ca sa putem face calcule cu expresii regulare , exact cum faceam cu expresii aritmetice !
In primul caz, al calculelor cu expresii aritmetice, numarul reprezentat de expresie trebuie sa fie acelasi:
Cand zic ca : 2 x(3+5) = 2x3 + 2x 5
In cazul calculelor cu expresii regulare, multimea de texte pe care o descriu acestea va ramane aceeasi. Si din aceasta cauza e nevoie de aceasta definitie a egalitatii expresiilor (egalitate indusa de egalitatea multimilor reprezentate).
Continuati lectura pina la pagina 77, observatia 5 !
Exercitii de algebra a limbajelor:
Demonstrati ca au loc relatiile de la observatia 5.
Am scris de mana, pe cartea pe care ati primit-o cum se fac aceste demonstratii.
Exemplu:
a) r+s = s+r
L(r+s) = { w | w apartine lui L(r) sau w apartine lui L(s) } =
= { w | w apartine lui L(r) U L(s) } = U inseamna reuniune
= { w | w apartine lui L(s) U L(r) } = reuniunea este comutativa
= { w | w apartine lui L(s) sau w apartine lui L(r) } =
= L(s+r)
In ora urmatoare va rog sa rezolvati aceste exercitii de algebra a limbajelor,
indicatiile sunt la pg 77 jos.
Teorema 3.1
Cititi enuntul teoremei 3.1 pg 77.
Intrebare de control:
Tabelul de la pagina 78 este pentru:
- implicatia directa
- implicatia inversa
- intreaga teorema.
Sugestie: Cititi titlul subcapitolului 3.2 [pg 79]
Spor la facut demonstratiile !
Niciun comentariu:
Trimiteți un comentariu