Planul de azi ar fi sa ne ocupam putin de:
1) Automate nedeterministe. Va fi o teorema despre echivalenta lor cu cele deterministe mai incolo.
2) Paragraful 2.4 Functionarea unui automat, Stari accesibile si productive. (Notiunile vor servi la a optimiza automatul din teorema). [pg 54]
3) Echivalenta intre AFD si AFN (Adica intre cine si cine, puteti trimite primul raspuns de az...) Paragraf 2.5 [pg 56]
4) Exercitii si exemple de transformare a automatelor ...
Incerc sa tin si transmisia Teams deschisa cu Sharing de desktop, deci puteti vedea in timp real, teoretic, aceste notite.
AUTOMATE NEDETERMINISTE (prezentare informala)
Va amintiti din cursul anterior povestea cu broscuta noastra montana care sarea de pe o piatra pe alta. De fapt vorbeam acolo despre un automat finit determinist. Avea proprietatea ca pentru fiecare stare initiala (piatra din poveste) si pentru fiecare simbol de la intrare (sunet din poveste) miscarea broscutei (automatului) era binedefinita sau nu era de loc.
Matematicianul ar zice: Adica functia delta, notata, δ are ca valoare, pentru acea stare si acel simbol da ca rezultat o "multime" de stari cu o singura stare, sau o multime vida.
Acestea erau automate DETERMINISTE, adica este bine determinata starea in care poate ajunge automatul plecand dintr-o alta stare si avand la intrare un anumit simbol. Nu am dubii ce se intampla.
Ok. Dar sa vedem ce este cu automatele nedeterministe, mai intai. Nedeterminismul va insemna aparent ceva in plus. Anume ca "broasca" ar putea sari in mai multe locuri deodata.
S-ar zice ca astfel obtinem un sistem mai "tare" de recunoastere si validare a textelor, care pare sa poata mai multe... in realitate o teorema ne va spune ca nu este chiar asa, desi aceste automate noi, nedeterministe , impreuna cu altele, cu niste tranzitii neconsumatoare de text de la intrare (se vor numi epsilon-tranzitii, scris, ε-tranzitii) vor fi mai facil de utilizat in demersul teoretic ce urmeaza.
De fapt de aceea avem nevoie de ele, pentru demersul teoretic care ne va duce in final la ceva folosit de programatori, la expresiile regulare.
Sa explicam cam cum e cu nedeterminismul, intuitiv intai:
Toti cunoasteti intersectia de linga McDonald's ... Imaginati-va o masina
-----
-0---0-
stand la semaforul din intersectie
= O=
O
O
|
V-ati prins voi..
Acum semaforul se face verde si masina pleaca spre parcarea universitatii de linga corpul D. Dar sunt mai multe locuri in parcare !
Deci multimea starilor posibile, in care ajunge automatul, contine mai mult decat o stare.
Matematicianul ar scrie despre cardinalul multimii | δ(stare, simbol) | ca nu este neaparat <= cu 1.
Def intuitiva: Un astfel de automat, in care atunci cand pleci dintr-o stare pe baza unui simbol, ti se permite sa ajungi, potential, in mai multe stari diferite, se numeste automat finit nedeterminist.
Exercitiu: Desenati in maniera cunoscuta, o stare din care se poate pleca in doua stari diferite, la receptionarea aceluiasi simbol de pe banda de intrare.
Schita de solutie: Ascii art.
a
(A) -------------------> (B)
\
\a
\
_\|
(C)
liniile sunt bineinteles continue,iar starile A,B,C sunt de fapt incercuite, cum ati vazut si in carte.
Exercitiu: Acesta este sau nu un automat finit nedeterminist ?
Dupa ce sa ne uitam ? Dupa doua arce etichetate la fel, care pleaca din aceeasi stare (nod din graf).
Le-ati vazut ?
A , 1 si 1 - un arc catre el insusi altul catre B.
B, 1 si 1 - un arc catre el insusi altul catre E.
C , 2 si 2 - un arc catre el insusi altul catre E.
D , 3 si 3 un arc catre el insusi altul catre E.
Sunt chiar mai multe motive sa consideram automatul ca fiind nedeterminist, dar unul singur ajungea.
Totusi: In functionarea unui astfel de automat care potential ajunge in mai multe stari, notiunea de configuratie este aceeasi, si va conta pentru a defini un limbaj tot multimea sirurilor care, dupa consumare, il duc intr-una din starile finale, dar acum, atentie, fiind mai multe siruri potentiale de configuratii, e suficient ca un singur sir sa ma duca intr-o stare finala , si gata, cuvantul este acceptat.
2) Paragraful 2.4 Functionarea unui automat, Stari accesibile si productive. (Notiunile vor servi la a optimiza automatul din teorema). [pg 54]
Ce se poate intampla cand functioneaza un automat ... exact ca in povestea cu
broscuta noastra montana.
1) Miscare: (q,aw') |- (p,w') ... adica cum citim asta ?
Din starea q si avand cuvantul aw' la intrare (adica un word, un cuvant w'
prefixat cu o prima litera a)
se trece in configuratia ( asa il citim pe |-) formata din
starea p si cuvantul w' fiindca litera a a fost deja consumata in procesul trecerii
(tranzitiei ar zice unii).
Bineinteles, tranzitia are loc atunci cand functia delta ne permite , cand lui
δ(q,a) ii apartine p -ul , noua stare.
2) Blocare.
Cam banuiti cand este vorba de blocare. Cand functia delta nu mai da voie
adica δ(q,a) = multimea vida .
2') Oprire.
Este un caz particular de blocare. In care functia delta nu ii mai da voie sa mearga mai departe dar nu avem nevoie de asa ceva. Fiindca cuvantul este deja acceptat, adica am ajuns la o configuratie (f, ε ), unde f este o stare finala ,
din multimea F , iar epsilon spune ca sirul de la intrare a fost analizat in intregime.
3) Stationare,
conceptul este mai mult matematic, amintiti-va ca inchiderea relatiei ne
permitea sa zicem ca in zero pasi se trece de la (q,w) |- (q,w) dar
ar mai fi o situatie de stationare:
La acele automate care nu consuma nimic de la intrare, de pe banda, la o tranzitie (sau consuma sirul vid "" ,daca vreti)
numite automate cu epsilon-tranzitii, notat ε-tranzitii) avem posibilitatea ca dupa un sir nevid, sa zicem de k - epsilon tranzitii , k <>0 ,sa ajungem tot in starea q.
k
(q,w) |- (q,w).
Asta nu ne explica autorul cartii . Sa citim mai departe pagina [pg55].
STARI ACCESIBILE, STARI INACCESIBILE, STARI... vom vedea imediat.
De ce aceasta discutie ? Fiindca memoria calculatoarelor merita economisita si unele transformari de automate creaza automate enorme, care pot fi optimizate prin reducerea numarului de stari.
Ce naiba, (neacademic) e cu starile accesibile ?
Ideea este simpla si o putem sugera printr-un singur, simplu, desen:
--->(Start) ----------------------->((Starea B))
a
deci trec cand am la intrare un a
si mai am in automat:
(Starea X) ----------------------->(Starea Y)
x
Deci automatul este cam asa: 4 stari, una initiala una finala si doua separate,desi legate intre ele. Faceti voi desenul pe hartie.
--->(Start) ----------------------->((Starea B))
a
(Starea X) ----------------------->(Starea Y)
x
Cam asa arata ! Este evident ca limbajul acceptat de automat este L={"a"}
Si la fel de evident este faptul ca starile X si Y au doua hibe care nu le ajuta, le impiedica sa contribuie la recunoasterea unor cuvinte mai lungi, de exemplu
care contin litere de "x".
a) Pe de o parte nu ai cum sa ajungi la ele , plecand de la start, adica sunt stari
inaccesibile.
b) Pe de alta parte nu poti sa ajungi de la ele la starea finala , starea B, deci
, cum recunoasterea cuvintelor depinde de ajunsul in starea B sau intr-o (alta) stare finala, ei bine, ele nu produc alte cuvinte recunoscute, si li se zice stari neproductive.
Acum putem citi teorema 2.1 pg 55 si bineinteles def 2.5
Ce spune Def 2.5 ?
Cam ce am zis si noi. Ca daca exista un cuvant w si pun cuvantul w la intrare si
(q0,w)|-* (q,ε)
adica se consuma w de nu mai ramane decat "" - epsilon - din el si ajung in starea q, atunci starea q este accesibila. (cu daca si numai daca).
Iar daca nu exista nici un astfel de w, nu pot sa ajung in q, deci q este inaccesibila.
Teorema 2.1 [pg 55] ne spune ca putem sa calculam din aproape in aproape multimea de stari accesibile cu ajutorul functiei delta. Si bineinteles, putem reduce multimea de stari a automatului la multimea starilor accesibile, ca oricum de celelalte nu avem nevoie.
Comentez cei patru pasi ai algoritmului, ca-s scrisi in notatie matematica, si
vor fi fiind unii care nu .... simt bine ...
a) Plec de la multimea S0
in care pun starea initiala, ca ea e oricum accesibila, ajung in ea din start :)) Pun si un contor i=0 ca sa obtin succesiv multim de stari din ce in ce mai mari, Si .b) Noul S, adica S indice i+1 este vechiul S indice i la care se adauga acele stari q, (bineinteles din Q, multimea de stari, nu zic nimic nou) pe care, atentie,
mi le permite functia delta: δ(p,a) sa includa acest q
care este de adaugat. In toate combinatiile posibile , cu orice litera a si orice stare p de plecare, din Si .
Practic ce facui ? Luai toate starile p din Si -ul curent... le combinai cu toate literele a din alfabetul Σ (citeste sigma), si obtinui via functia δ (citeste delta), noile stari pe care le adaug la Si ca sa obtin S indice i+1.
Si tot asa mai departe dar ce sa vezi, automatul este finit, deci nu am cum sa adaug stari in aceste S-uri care devin din ce in ce mai mari....
evident ca nu pot sa obtin S-uri infinit de mari, deci ma opresc la o anumita multime care nu depaseste Q, multimea initiala de stari a automatului FINIT (AFD - F de la finit). e clar ca ma voi opri undeva, intr-un moment in care,
Si si S indice i+1 sunt identice.
c) daca S indice i+1 este egal cu S indice i, e clar ca nu mai avem ce stari sa adaugam. Salt la d).
Altfel salt la b), ca poate mai adaug ceva in S-ul care va deveni S indice i+2.
d) Este clar cand ma opresc. Cand nu mai gasesc nici o stare noua.
Dati pagina la [pg 56, definitia 2.6]
Cam pe aceesi idee mergand se definesc starile neproductive,
...este o stare neproductiva cand nu pot sa ajung din ea intr-un p din F,
p fiind stare finala, orice cuvant w as incerca sa pun la intrarea
( pe banda), automatului.
As vrea eu sa am asa un w incat (q,w) |-* (p, ε) cu p din F , dar ghinion,
nu am sansa aceasta, adica starea q din care plecai era neproductiva.
Imaginati-va ca ea nu poate produce nici un drum pina in multimea F de stari, indiferent ce ii dau la intrare.
Citim acum teorema 2.2:[pg 56 - 58 pe ebook] care ne spune ca putem sa reducem automatul (nu numai la starile accesibile , cum stiam) ci chiar numai la cele productive.
De fapt ambele reduceri sunt posibile, si ele se aplica una dupa alta, pt a reduce numarul de stari.
E cam aceeasi idee, din moment ce numai anumite feluri de stari participa la recunoasterea cuvintelor, putem sa ne rezumam numai la acelea, dar,
stai, trebuie sa le gasim mai intai.
Cititi algoritmul de la pg 56,
Ideea este exact aceeasi, doar ca de data aceasta mergem pe arcele functiei delta, inapoi, plecand de la multimea starilor finale, F.
a) A0 (A indice 0) este F.
b) La fiecare pas, construiesc un nou A indice i adaugand anumite stari p. De unde le iau ? Fiecare q din Ai -ul anterior, apartine unui delta de p si a.
a
(p) --------------> (q)
\
\a
\
_\|
(q')
Si acesti p se adauga la noul Ai devenit A indice i+1, deci merg inapoi pe arce. Ok ?
c) La fel, din cauza multimii finite Q, nu pot merge la infinit cu adaugatul de elemente, v-ati prins, nu-i asa ? Si cand A indice i si urmatoarea multime (A indice i+1) sunt egale, ne oprim.
Acum construim noul automat. Cum scrie pe ultimul rand din imagine.
Puteti citi si intelege ?
Ar trebui sa sune in minte cam asa:
Q' - noua multime de stari ramane sa fie formata doar din cele din A indice i+1.
F' - noile stari finalesunt tot acelea ca in F.
δ' - noua functie, citeste "delta prim" e asa definita:
δ'(q,a) = { p din Q' astfel incat p este in vechiul δ(q,a) } dar numai pt. orice q din Q'.
... si orice a din Σ.
Observatia este chiar amuzanta, daca gusti umorul matematic al poantelor:
"Am invatat o multime de capitole, dom'profesor. " Si multimea era vida :))
Exact la fel: Ce ne facem daca q indice 0, starea initiala a automatului initial,
nu este productiva , deci nu apare in noul Q' ?
Inseamna ca nu exista nici o secventa w de pus la intrarea automatului, care sa ne conduca inspre o stare finala (adica din F), fie ca secventa se termina sau nu cand ajungem acolo.
Pe cale de consecinta nu exista nici o secventa care sa se termine fix cand am ajuns intr-o stare din F.
Dar asta era exact conditia ca un cuvant sa fie acceptat: Sa se termine cuvantul de procesat simultan cu ajungerea la o stare din F.
Deci automatul nostru initial nu putea ajunge in nici o stare finala la terminarea cuvintelor, oricare ar fi ele, deci limbajul sau este:multimea vida.
Teorema de echivalenta intre AFD si AFN [pg 56, 58 pe ebook]
Care ne va spune ca putem lucra la fel de bine cu automate nedeterministe, acestea se compun intre ele mai usor, dar obtinem acelasi lucru care l-am face cu automate deterministe. Ne spune ca:
1) Automatele nedeterministe nu ne aduc nimic nou din punct de vedere al recunoasterii limbajelor ! Pare ca nu castigam nimic aici.
2) Putem folosi totusi operatii de compunere a automatelor care produc din doua (sau mai multe) AFD -uri un AFN, fara ca aceasta iesire din multimea de AFD -uri sa ne incurce.
Ba chiar teorema ne permite sa revenim inapoi in universul AFD-urilor (implementabile prin programe deterministe - ca broasca din poveste care se misca precis, bine determinat) cand printr-o operatie oarecare de combinare a automatelor ajungeam la un AFN.
Iata un exemplu anterior studiat ca exercitiu:
Definiti automatul care recunoste limbajul L= { "PSD", "PNL" } - varianta a problemei rezolvate anterior din cartea profesorului D.M, pg 25. Asemanarea exercitiului din volumul de acum 10 cu evenimente actuale este intamplatoare.
Pentru primul cuvant este simplu, avem un automat
P S D
---> (1) --------> (2 ) -------->(3) -------> ((4)) si la fel si pentru al doilea cuvant
P N L
---> (1) --------> (2 ) -------->(3) -------> ((4))
Ok ? L1={ "PSD" } L2 ={"PNL"}
Dar cum putem realiza automatul care recunoaste reuniunea a doua limbaje, oricare ar fi ele ?
Ziceti ? Va ascult ...
O idee ar fi sa punem prima stare, cea initiala in comun si sa plecam mai departe. Vom (re)gasi aceasta idee intr-o teorema viitoare.
Bineinteles, metoda merge indiferent de alfabetul(alfabetele) celor doua automate, care se pot reuni pentru a forma noul alfabet.
P S D
---> (1) --------> (2 ) -------->(3) -------> ((4))
||
|| P N L
---> (1) --------> (2 ) -------->(3) -------> ((4))
Cumva facem aceste doua stari sa devina egale, suprapuse (nuuuu, desenul de mai sus nu este corect asa) dar sugereaza ce si cum vom obtine. Iata ce obtinem:
P S D
---> (1) --------> (2 ) -------->(3) -------> ((4))
|
| P N L
---------> (2 ) -------->(3) -------> ((4))
Adica:
P S D
---> (1) --------> (2 ) -------->(3) -------> ((4))
\
\ P
_\ | N L
(2 ) -------->(3) -------> ((4))
Acum , desenati cu linii continue noul automat, si veti observa ca el este
nedeterminist, din starea 1 pleaca mai multe arce.
Este clar, in anumite operatii cu automate putem obtine din AFD -uri AFN -uri si cumva trebuie sa revenim in multimea aceea a AFD-urilor.
La asa ceva ne ajuta teorema 2.3 din paragraful 2.5 [pg 56].
Vreau sa ajung la ceva folosit de programatori, expresiile regulare. Iar intr-o demonstratie de acolo apar exact acest fel de operatii cu automate. Dati pagina la pagina 78]. Reveniti.
In imagine: O operatie cu automate, o reuniune de limbaje, in care se foloseste cam acelasi gen de "suprapunere" a starilor initiale, din demonstratia unei teoreme la care vom ajunge (Capitolul despre expresii regulare). Va mai fi insa ceva de explicat mai inainte, vedeti in imagine ce ?
Raspuns: Acel mic epsilon de pe cele doua arce (sageti) care pleaca din starea notata q indice 0.
Sa revenim la teorema 2.3 [pg 56].
Incercati sa cititi enuntul si explicatiile ....
Nu ... ideea demonstratiei nu se vede .... trebuie povestita putin.
Cum erau automatele nedeterministe ?
Ca in povestea cu masina care pleaca de la stop cand are verde si parcheaza in parcare, este posibil la fiecare pas sa ajungi intr-o multime de stari (potentiale)... iar la pasul urmator sa ajungi ... plecand din ele ... intr-o multime si mai mare (sau mai mica uneori) dar oricum alta multime de stari potentiale.
E fericit cazul cand in acea multime de stari in care poti ajunge, (acele stari potentiale), se afla si o stare din F. Exact in asa un caz, cuvatul w de la intrare e acceptat.
Deci, retinem: cand multimea de stari in care ajung, intersectata cu F, starile finale, ne da ceva nevid, cuvantul este recunoscut.
Deci cam cum decurg schimbarile de configuratie:
({q0'}, abc...w) |- (M1, bc...w) |- (M2, c...w) |- (M3, ...w) |- ... |- (Mn, ε)
si Mn (citeste M indice n) intersectat cu F sa fie nevid. (ε - e notatia pt "" )
De fapt ce am scris noi aici insirand aceste multimi potentiale de stari, in aceste "configuratii" de tip nou, perechi in care primul element nu mai este o stare ci o multime de stari ?
Acum sa va vad ! Sunt acestea configuratii de tip nou ? Sau de tip vechi ?
Unii ar spune ca sunt niste configuratii de tip nou, fiindca primul element nu mai este o stare din Q ci o submultime de stari din Q. ( se noteaza ca apartine lui P(Q), cu P -rotunjit, este multimea submultimilor lui Q acest P(Q)).
Dar stai putin, cititorule !
Ce-ar fi sa zicem ca aceste submultimi ale lui Q, submultimi de stari din vechiul automat, sunt starile unui nou automat. Evrika !
Exact aceasta este ideea pe care e facuta demonstratia teoremei 2.3. care se face, in esenta ei, construind noul automat... dupa aceea se face imediat demonstratia ca fiecare cuvant recunoscut de vechiul automat e recunoscut si de cel nou (si reciproca) care e aproape evidenta.
Constructia noului automat trebuie explicata insa pe indelete:
Vechiul automat era: M1=(Q1 , Σ , δ1, q0', F1)
Noul automat este M2=(Q2 , Σ , δ2, q0'', F2) dar cine sunt acestia ?
Sa vedem:
Q2 este multimea , colectia, submultimilor lui Q1, cel initial. Provine din ideea sirului de multimi, create de nedeterminism.
Σ - alfabetul , este acelasi. E normal, automatele recunosc acelasi limbaj. si totul e scris cu acelasi alfabet, toate cuvintele w propuse automatelor spre acceptare.
Uitati-va pe sirul de tranzitii... am notat starea initiala cu q0' ca in automatul M1.
({q0'}, abc...w) |- (M1, bc...w) |- (M2, c...w) |- (M3, ...w) |- ... |- (Mn, ε)
Cine e starea initiala a noului automat ?
Pai este elementul dintai din prima configuratie. Nu-i asa ca orice automat pleca in analiza, in procesarea textului, din configuratia:
(stare initiala, cuvant de analizat)
Pai daca punem egal intre aceste perechi se vede imediat:
({q0'}, abc...w) = (stare initiala, cuvant de analizat)
ca starea initiala a noului automat este multimea care are ca element vechea stare initiala.
In noul automat o notasem q0'' , deci:
q0'' = {q0'}
dar scrieti voi acel 0 ca indice inferior ca sa arate ca in carte.
Dar ce stari sa punem in F indice 2 ? Adica ce multime de stari finale are noul automat ?
Oricum, aceasta noua F2 va fi o colectie de multimi de stari din F1. Cam ce stari sa punem in multimile colectiei ?
Are sens sa avem in multimile colectiei numai stari dinafara lui F1 ? Pai , ele nu ne ajuta cu nimic la recunoasterea cuvintelor , de catre M1 dotat cu F1.
Atunci vom prefera acele multimi de stari din Q1, care contin cel putin o stare finala de-a primului automat. O astfel de multime, S, s-o numim, intersectata cu F1 va da ceva nevid, o multime nevida.
Ce mai ramane de definit din noul automat M2=(Q2 , Σ , δ2, q0'', F2) ?
Q2 - am definit, sunt partile , submultimile lui Q1
Sigma e la fel.
q0'' = {q0'}
F2 - e in imagine
A ramas functia delta 2. Cum definim delta 2 pornind de la delta 1 ?
δ = ? ( δ )
2 1
Cum sare(a) broasca din poveste in mod pardon, nedeterminist ? Dintr-o stare, sarea cam ca MultiMan (stiti personajul de benzi desenate, care se multiplica) , intr-o multime de stari. Dar din starile acelea plecau alte -----> arce mai departe.
Deci trebuia la pasul urmator sa reunesc toate aceste multimi de destinatii. Fiecare din destinatiile
din δ1(q,a) producea la pasul urrmator o alta multime de destinatii samd.
Vorba lunga, saracia omului, trebuiesc reunite valorile date de functia delta 1 pentru toate starile de care dispunem, sa zicem intr-o multime curenta S de stari.
Deci functia delta 2 a noului automat, aplicata unei multimi S de stari, care S contine o serie de valori , fiecare sa o numim provizoriu q... ca sa o calculez nu am decat de reunit valorile vechii functii delta 1 pentru toate aceste q...
Offff, mai bine scriem matematic:
Si bineinteles, ramane cazul...cand S este vida. In acest caz delta 2 de multimea vida va da, fireste, multimea vida.
Am definit astfel AFN-ul echivalent. M2=(Q2 , Σ , δ2, q0'', F2).
Cititi acum, fiindca acum puteti citi singuri: pg 57, pg 58.
si recalculati multimile delta 2 care se obtin pentru automatul din exemplul cu numarul 4.
Exercitii de seminar puteti crea singuri:
- desenati un automat nedeterminist ca la pagina 57 jos.
Si calculati cu formula de mai sus functia delta 2 , obtinand multimi de stari noi, care vor fi starile din noul automat... ca la pagina 58.
Easter egg: Propuneti o problema de acest gen, pentru colectia de probleme in vederea examenului. Si rezolvati-o. Nu uitati sa mi-o trimiteti !
Opriti-va deocamdata din lectura inainte de paragraful 2.6.
Ba nu !
Felicitari tuturor celor care au rezistat pina la capat, desi ati fost provocati sa abandonati ! Ati dovedit ca aveti ceea ce in Parabola adevaratei stiinte a vietii, basm arab din O mie si una de nopti era sursa pentru intreaga stiinta pe care o inveti intr-o viata: Virtutea rabdarii !
Va doresc ca aceasta virtute sa nu va paraseasca niciodata !
Sarbatori fericite !
The End.
Niciun comentariu:
Trimiteți un comentariu