Buna ziua si bun venit la noua intalnire cu
teoria formala (aka matematica) a limbajelor (si cea a automatelor)
La inceput strigam catalogul, pardon trimitem invitatiile la participare.
Acum pregatiti va rog manualul profesorului M. Limbaje formale si teoria automatelor. Am ramas la pagina 79.
Amintiti-va contextul discutiilor noastre. Incercam sa gasim o modalitate de a introduce automatele, dispozitive de verificare a textelor, in limbajele de programare, dar acest lucru era oarecum problematic.
Automatele erau usor de DESENAT, oarecum dificil de programat si am propus pentru ele:
- o reprezentare a multimilor de texte la aparteneta de care putea fi verificat un text: multimile regulare
- o reprezentare a acestor multimi regulare sub forma de:
expresii regulare
Aceste expresii regulare, semanand la forma cu expresiile aritmetice, se pot scrie in limbajele de programare. De altfel limbajele de programare includ expresiile aritmetice.
Si aceste expresii regulare se pot transforma usor in automate ! Vedeti tabela de la pagina 78.
(Mda ' acestea sunt automate cu epsilon-tranziti, dar am demonstrat mai inainte ca ele sunt echivalente cu cele clasice si se pot transforma in cele clasice. Un computer ar sti sa faca asta, programat fiind.)
Numai ca noi avem problema inversa: Am desenat un automat care ne prinde bine la validat, la verificat niste stringuri, ceeea ce e usor de facut sub forma de desen, si ne-ar trebui expresia regulara.
Avem de facut doua lucruri:
-1. De demonstrat ca in general o asemenea expresie exista. Teorema este in esenta cea de la pagina 79 si atentie, cel mai usor se citeste aceasta pagina intai de sus in jos, o vom comenta impreuna.
-2. Intrucat metoda din teorema este dificila computational, ar cere sa construim un intreg set indexat de multimi regulare si expresii regulare (nu zic nu, exista in teoria algoritmilor asa algoritmi, la capitolul programare dinamica)ne-ar trebui o metoda mai practica, mai rapida, chiar daca DEPENDENTA de problema. Adica nu e un algoritm universal, dar sa mearga repede.
Metoda o gasim in manual la pagina 81. [pg 81].
Se bazeaza pe un fel de formula a rezolvarii ecuatiei de gradul intai (nici macar de garadul al doilea) din universul expresiilor regulare, o gasiti la pagina 80, in chenarul de jos.
Pg 80, jos: Rezolvarea ec. de gradul I, in lumea expresiilor regulare, nu in lumea numerelor.
Sa incepem !
3.2 Determinarea expresiilor regulare [pg 79]
Pare socant, dar mie mi se pare ca pagina aceasta se citeste cel mai bine de jos in sus. Daca nu ma credeti, cititi formula pentru "R indice ij indice superior k",
Rijk
doua randuri mai jos de unde scrie:
Metoda 1. Simtiti ca ati priceput ceva ? Pariez ca nu.
Sa mergem la baza paginii. Citim impreuna ultimul paragraf: Ziceti dupa mine:
"Limbajul acceptat de automatul M se poate specifica cu ajutorul expresiei regulare
rij1n + rij2n + .. + rijpn
unde F =
{ q
j1 , q
j2 ... qjp } ... scuzati softul de bloging ca nu scrie bine formule cu indici.
" Am inchis ghilimelele.
Ati inteles ceva mai mult ? Se poate intelege cevaa mai mult ? Eu zic ca da.
Fiti atenti pas cu pas:
- Are automatul mai multe stari finale ! In numar de p. Posibil, Da.
- Sa pp ca ar avea numai cate una din ele pe rand.
- Ar fi atunci mai multe automate cu o stare finala. Da ?
- Fiecare ar accepta o multime (n.n. regulara) de cuvinte.
- Fiecare automat de mai sus ar fi transformabil intr-o expresie regulara.
- Daca expresiile s-ar scrie si le-am calcula ca fiind acele
rij1n
cu indici de la "j 1" la "j p"atunci intregul automat, care si-ar putea sfarsi functionarea SAU in prima stare finala q
j1 SAU in urmatoarea, ce expresie
regulara echivalenta ar avea ?
Daca e cu SAU ?
Sau inseamna reuniune, inseamna + (uneori notat | ) la expresii regulare !
Deci ?
r1j1n + r1j2n + .. + r1jpn
Dar cum sa construim aceste multimi "r indice inferior i j indice superior n" ?
rij1n
Si ce este cu acesti indici ?
Sa intelegem impreuna. Sa vedeti ca se poate intelege !!
rij1n
Ce sunt indicii acestui rij n , doi sunt jos , deci de acelasi fel, unul este sus.
1)Despre cel de sus va dau eu raspunsul, este un fel de indice n ca la inductie, care creste pas cu pas, dar creste doar pina la n. Cine este n ? Este ceva finit la un automat !
Ce era finit la un automat ?
Numarul de stari ! |Q| = n. Despre el este vorba, si concluzia este ca vom construi acele r indice ....... printr-un fel de inductie dupa n, numarul nodurilor, starilor din automat care participa la constructia multimilor si expresiilor.
Ok. deci n e un fel de indice de inductie, in intervalul 0 - n. 0 = nr de elemente din multimea vida, deci la constructie vor participa ... cum zero stari ? Trebuie sa mai fie niste stari pe undeva. Ca din nimic nu construim nimic - decat cel putin in fizica cuantica. Este momentul ...
Sa ne uitam la indicii de jos:
2) Al doilea acel j indice 1 isi tradeaza usor semnificatia, este indicele unei stari (in particular al unei stari din F, dar modul de numerotare sugereaza ca sunt posibili si alti de j.).
Prin similitudine, si primul indice i, este tot al unei stari din automat. Dar la noi , la suma cautata este egal cu 1. Corectati !
Cine este starea 1 ? Starea initiala de la care plecam. Cine sunt acele stari J1 pina la Jp ? Starile in care ajung.
Exact aceasta este ideea constructiei:
Sa construim printr-un fel de inductie finita acele expresii regulare (si bineinteles si multimile regulare se pot construi analog):
rijk unde
i = indicele starii initiale din care plec
j = indicele starii finale in care ajung
k = indicele k dupa care fac inductia
Ne trebuie formula inductiva: Iat-o ?
rijk
= rikk-1
(
rkkk-1
)+
rkjk-1
+
rijk-1
Dar cum o intelegem:
rijk
adica "Expresia r care coresp drumurilor in automat de la starea i la starea j prin stari de indice cel mult = cu k" este
rikk-1
(
rkkk-1
)+
rkjk-1
produsul a trei expresii, semn ca stringul este concatenare a trei stringuri...
+rijk-1
sau "r care coresp drumurilor in automat de la starea i la starea j prin stari de indice cel mult = cu k-1".
Ia sa ne gandim un pic cum ajungem de la starea i la starea j, prin noduri de indice maxim k, inductie dupa k, cand trec de la k-1 la k ! Stim
rijk-1
adica felul cum ajung de la i la j prin noduri / satri de indice maxim k-1. Acum mai apare nodul k.
(i) (k) (j)
| /|\
| |
| |
----------------......------------------------
rijk-1
Decocamdata de la i la j pot ajunge direct, cum spune ipoteza de inductie, prin noduri intermediare de indice cel mult k-1 si acestor drumuri prin graf le corespunde
rijk-1
Acum apare se inodul de indice k, starea k, si astfel apar mai multe variante de a ajunge de la i la j, de data aceasta via k.
rikk-1
(i) -------------> (k) (j)
| /|\
| |
| |
----------------......------------------------
rijk-1
Primul pas ar fi sa ajung de la i la k, cf ip de inductie, cu stari de indice cel mult k-1 deci
rikk-1
Dar drumul nu s-a sfarsit, am ajuns abia in K. Si stringul va fi mai lung.
Din (k) as putea sa ajung
direct in j (dar vom mai vedea ca se poate sa mai si batem pasul pe loc tot prin k).
rikk-1 rkjk-1
(i) -------------> (k) ----------------> (j)
| /|\
| |
| |
----------------......------------------------
rijk-1
Dar sa nu ne grabim, drumurile de la i la j prin k pot fi ceva mai complicate, nu doar :
- din i in k si
- din k in j
Se poate si sa "batem pasul pe loc" plecand si revenind in k de cate ori vrem, ca si cum ar fi o bucla pe k.
rikk-1 rkjk-1
(i) -------------> (k) ----------------> (j)
| / |\ /|\
| / \ |
| --------
(rkkk-1 )* |
----------------......------------------------
rijk-1
In concluzie, drumurile de la i la j prin k pot fi ceva mai complicate:
- din i in k si
- din k in k de cate ori vrem (vedeti ca * inseamna repetarea !)
- din k in j
Cee ce ar da nastere ls trei stringuri concatenate, sau trei expresii regulare facute produs.
Acum daca va uitati la diagrama de mai sus, o copii, si la formula, legatura incepe sa se vada:
rikk-1 rkjk-1
(i) -------------> (k) ----------------> (j)
| / |\ /|\
| / \ |
| --------
(rkkk-1 )* |
----------------......------------------------
rijk-1
rijk
= rikk-1
(
rkkk-1
)+
rkjk-1
+
rijk-1
Si acum hai sa vedem cum incepe inductia: De la k=0.
rij0
= a1 +...+
aj + ai +...+
ak - aici indicii pot fi variati si se mai aduna si un + X.
Cum pentru drumurile de la i la j cu indic e0 sus nu luam in considerare si alte noduri, stari, intermediare, e clar ca vor conta doar acele litere a pentru care
delta (
qi ,a) =
qj
ceea ce se scrie: δ (
qi ,a) =
qj
Si toti acesti a cu diferiti indici se aduna pentru a forma expresia rij indice 0 si se mai aduna si ceva notat cu X.
De unde provine acest ceva, X, si cine este el.
Sunt situatii cand i = j, in acest caz am si stringul vid, "", epsilon, acceptat pe drumul de zero pasi de la i la j.
Deci:
daca i = j atunci X = epsilon.
iar daca i <> j atunci X = multimea vida. (Stiti voi, se noteza cu "fi mare").
Sa trecem acum la multimile regulare echivalente expresiilor.
La mijlocul paginii 79 [pg 79], gasiti formula T(M) a multimii regulare care corespunde automatului.
Ati gasit-o ? Ati gasit si greseala de tipar ?
Mai departe, de la mijlocul paginii [pg 79] in sus, toata povestea se repeta, dar de data aceasta gandim in multimi regulare.
Aveti 15 minute pentru citit pg 79, da, de la jumatate in sus !
Acum v-ati "prins" de ce incepe astfel cu constructia multimilor Rij ?
Ati inteles de ce am notat cu X nu cu A multimea cu alternativa, acolada X= { ... ?
Acum dati pagina la pagina 80. [pg 80]
Aici gasiti metoda a II-a , de rezolvare in particular.
Cititi prima parte a paginii 80.
Care este ideea ?
Ne interesau niste expresii regulare atasate nodurilor din graf, adica starilor din autoamat : Le notam cu niste litere mari, ca pe necunoscute: X,Y, Z, vedeti la pg 82, este o figura, Reveniti la pagina 81, ...... sau le putem nota, tot ca pe niste necunoscute dar cu majuscule de la inceputul alfabetului: A, B, C vedeti la pg 81. In ambele locuri, pe diagrame.
Ati gasit diagramele de la pg 81, 82, cu necunoscutele puse linga stari ?
Bun, ne pregatim sa facem un sistem de ecuatii, pentru fiecare astfel de automat. Am gasit necunoscutele. dar cum se scriu ecuatiile ?
Daca am avea undeva:
a
(X) <---------- (Y)
Este clar ca atunci cand ajung in X via Y mai trebuie sa concatenez o litera de a.
Deci cumva X = .... + Ya
daca am fi avut doua arce de la Y la X cu a si a' pe arc, am fi avut doua moduri, cu SAU intre ele de a ajunge de la Y la X.
Si atunci : X = ....
ceva .... + Y(a+b).
Ceva-ul spune ca mai sunt si alte moduri de a ajunge in X, nu numai via Y. Iar + ul dintre a si b spune ca pot sa ajung in doua moduri, cu SAU intre ele, din Y in X, dar stringul s eva lungi de la cel parcurs pina in Y cu un a sau cu un b.
Intr-adevar : Y(a+b) = Ya + Yb
Ok, pentru toate nodurile Xk care au arce care pleaca din ele si ajung in nodul nostru X, marcate cu literele a indice k (ak).
Gasiti suma scrisa de mana , cu sigma majuscula, la mijlocul paginii 80, putin mai jos ?
Ati gasit-o ?
Ar tebui s-o cititi: "Xi este egala cu suma dupa acei k pentru care q indice i apartine lui delta de q indice k si a indice k , suma din X indice k produs cu a indice k + un beta indice i".
Cine este beta indice i gasiti mai jos:
- este epsilon daca q indice i este starea initiala
- este Fi majuscula (exp regulara notata cu semnul multimii vide) altfel
Ati gasit formula de la pg 80 jos ? Cu acolada ?
Inainte de a da o formula de calcul pentru rezolvarea unor astfel de ecuatii, sa vedem doar cum se face un astfel de sistem:
CONSTRUCTIA SISTEMULUI PE UN EXEMPLU
Dati pagina la pagina 81:Desenati pe o foaie diagrama de pe pagina.
Starile automatului sunt notate A, B, C, ... la nevoie mai mult. Ne uitam la arce.
Cum ajung in A?
- Pai direct, fiindca e stare initiala, fara sa citesc nimic... deci epsilon:
A = ε + ...
sau altfel cum ?
Din C pot sa ajung in A dar se adauga un b la sirul parcurs pina in C, el devenind Cb.
Deci punand la loc cu SAU (aka +) ambele variante obtinem:
A =
ε + Cb
Am stabilit prima ecuatie.
Cum ajung in B ?
Doar o posibilitate , din A pe arcul cu eticheta a.
Deci B = Aa
Am stabilit a doua ecuatie.
Cum ajung in C ?
In trei moduri.
Din A pe arcul etichetat cu b, din C pe arcul, bucla, etichetat cu a, din B pe arcul etichetat cu b.
C= Ab + Ca + Bb.
Am stabilit a treia ecuatie.
Concluzia: Am un sistem cu trei ecuatii, dar se rezolva ad hoc, cum vom putea !
A =
ε + Cb
B = Aa
C= Ab + Ca + Bb.
Pregatiri teoretice: Sistemul fiind de gradul I,avem nevoie de ecuatia de gradul intai in expresii regulare si de formula ei de rezolvare.
Dati pagina la pagina 80 jos, unde este o formula in chenar!
Cititi ultimul paragraf deasupra chenarului si chenarul.
In esenta, ecuatia, (scrieti-o si voi pe un cartonas, post-it, si puneti-l la vedere, fiindca vom da pagina si vom avea nevoie de formula)
X = Xα + β
Are solutia : X =
β α*.
Cum se memoreaza:
Spuneti dupa mine: Solutia este "termenul liber inmultit cu coeficientul necunoscutei, iterat" sau mai usor de retinut "
termenul liber inmultit cu coeficientul necunoscutei , stelat."
Hai sa facem un exercitiu:
Z = Z(abc)* + ac(bc)* Cat este Z ?
Ziceti formula magica:
"
termenul liber inmultit cu coeficientul necunoscutei , stelat."
Si solutia este:
Z = ac(bc)* ((abc)*)* = ac(bc)* (abc)* fiindca ((abc)*)* = (abc)*
Nota: solutia este unica daca
ε nu apartine Limbajului formulei α , α fiind coeficientul necunoscutei.
Demonstratia este imediata:
Aratam ca ecuatia:
X = Xα + β
Are solutia : X =
β α*.
Calculam:
Xα + β pentru X = β α* :
Xα + β = β α*α + β = β (α*α + ε) = β (α*) = X deoarece (α*α + ε) = α*
SA NE INTOARCEM LA PRIMUL SISTEM:
A =
ε + Cb
B = Aa
C= Ab + Ca + Bb.
Starea finala a automatului este doar C, vezi diagrama, deci am fi multumiti sa aflam expresia necunoscutei C !
Dar in ecuatia a treia avem prea multe variabile, dar de una scap usor:
Fiindca B = Aa pot sa substitui acest B in ultima ecuatie:
C = Ab + Ca + Bb in care inlocuiesc B = Aa
Obtin: C = Ab + Ca + Bb = Ab + Ca + Aab = A(b+ab) +Ca
(Acum si pe A il pot inlocui din prima ecuatie cu C-uri.)
Obtin: C = Ab + Ca + Bb = Ab + Ca + Aab = A(b+ab) +Ca = (ε + Cb)(b+ab) +Cb.
Acum am o ecuatie de gradul I: C = C alfa + beta ...... dar cat sunt alfa si beta ? Dezvoltam produsele ca sa aflam.
C = (ε + Cb)(b+ab) +Ca.
C = (ε + Cb)(b+ab) +Ca = (b+ab) + Cb(b+ab) +Ca = (b+ab) + Cbb+Cbab +Ca =
C( bb+bab +a ) + (b+ab)
Atentie, se poate gresi foarte usor la calcule !!
Ecuatia este:
C =C( bb+bab +a ) + (b+ab)
Acum rostim formula magica:
"termenul liber inmultit cu coeficientul necunoscutei , stelat."
C = (b+ab)( bb+bab +a )*
Si am rezolvat pb. C era cel care ne trebuia.
Seminar:
Rezolvati cu cartea in fata, fara sa va uitati la solutie ( ea este pentru control) Exemplul 2 pg 82 si Exemplul 3 pg 83.
Rezolvati:
3.3 Probleme propuse ! pg 84 - 85 -86.
Ca de obicei... cat scrie la subsolul paginii continuam,
continuam.
