Va rog sa aveti iarasi manualul de Limbaje formale si teoria automatelor la indemana, deschis la pagina 49. (nr paginii tiparite). [pg 49 -54]
Dar inainte de a discuta paragraful 2.2 Configuratii si relatii de tranzitie precum si punctul b) pg 51, as dori sa va reamintesc care eraobiectul studiului nostru, intr-o prezentare informala, deocamdata, inainte sa trecem la cea formala.
AUTOMATE - O PREZENTARE INFORMALA
Obisnuiesc atunci cand prezint acest subiect, teoria automatelor , sa il prefatez cu o povestioara, usor de tinut minte, si care are pina la urma legatura cu modul de reprezentare a automatelor.
Ii spuneam , in gluma, fiindca mai si glumim, "Povestea broastei montane" - biologii pot sa ma certe pt titlu - dar e mai usor de tinut minte asa.
Luati o foaie noua de hartie, avem de desenat ceva, in timpul povestii.
Povestea suna asa: La munte, printre bolovani, traieste o broscuta montana. Ea isi are adapostul linga o piata (pe care o vom desena rotunda, in coltul stg sus al unui patrat imaginar cu latura de un lat de palma).
(A)
Aceasta este piatra A, si in fiecare dimineata, trezita de razele soarelui, broscuta noastra se suie pe piatra notata cu A. Putem desena asta asa, cu o mica sageata care intra in (nodul etichetat al multigrafului, ar zice matematicienii)
->(A)
Intre peretii canioanelor (montane) se aud sunete, probabil turistii se joaca haulind si admirand ecoul, se aud (sa zicem) vocale: a,e , i,u.
Speriata de sunete, broasca noastra se muta de pe o piatra pe alta, dar nu oarecum, ci dupa urmatoarele reguli:
Daca este pe piatra A si aude un "a" atunci sare pe piatra (B), desenati piatra B, in coltul din dreapta sus al patratului. (voi cere desenele ca proba de activitate).
a
-> (A) -------------------------------> (B)
De pe piatra B , daca aude un "e", broscuta noastra sare pe piatra C, iar de pe
C ar sari pe D daca aude un "u".
a
-> (A) -------------------------------> (B)
/
/
/
e /
/
| /_
u
(C) -------------------------------> (D)
Desenati dvs, mai bine decat mine care fac ASCII art.
De pe B sare pe C daca aude un "e", iar inapoi de pe C pe B sare daca aude un "o".
a
-> (A) -------------------------------> (B)
/ _
/ /|
/ /
e / / o
/ /
| /_ /
/ u
(C) -------------------------------> ((D))
Indicatii pt un desen corect:
Acum la desen: Liniile sunt continue, iar cercurile din jurul A,B,C, D sunt complete, cel din jurul lui D este dublu !
Reprezentarea ca graf a automatului din povestea cu broscuta.
Imagine de la: Andrei P.
Imagine de la: Andrei P.
De pe B sare pe C daca aude un "e", iar inapoi de pe C pe B sare daca aude un "o".
In D este capatul calatoriei broscutei noastre, sa zicem ca pe aici trec in sir delicioasele furnici care ii plac si care fac o bucla in jurul pietrei D.
Desenati un cerc suplimentar in jurul pietrei D (al nodul D din multigraf ar zice matematicienii). Vom numi mai tarziu o acsemenea stare = stare finala.
Si acum problema: Ce sir de sunete (ce string) face broasca noastra fericita, in sensul ca exact atunci cand se termina sirul de sunete, broasca a ajuns pe piatra D, (starea finala.)
Trimiteti raspunsul si desenul dvs pe e-mail la adresa cunoscuta !
Intre timp mai notam niste explicatii, n-ar fi rau sa notati si dvs.
1) Turistii din poveste emit niste sunete care se comporta ca Literele unui alfabet notat
Σ = { a, e, o , u}
2) Ducerea broscutei de la A la D, adica "trecerea automatului din starea initiala in (una din starile) starea finala, odata cu terminarea cuvantului peste alfabetul sigma" defineste o multime de cuvinte, cele care au permis aceasta ducere.
Deci asa un mecanism, format ca in poveste. din stari si tranzitii, este un dispozitiv care defineste, accepta, valideaza, cuvintele unui limbaj. I se mai spune automat acceptor de limbaj in unele carti.
3) Ce am definit eu de fapt cu aceasta poveste este multimea cuvintelor care .... stiti voi... duc proasca de la A la D... adica o multime de cuvinte anume, adica o submultime din Σ *.
Exercitiul nr 1: Care este primul cuvant solutie a problemei ?
Haideti, ganditi un minut ...
Raspuns: "aeu"
Exercitiul nr 2:Dar daca broscuta imaginara s-ar plimba de mai multe ori intre B si C, ce cuvinte s-ar forma ?
Completati multimea:
Exercitiul nr 3: Completati multimea, astfel incat sa fie exact limbajul acceptat de automat.
L = { aeu, ... , .... , }
Exercitiul nr 4: Pentru fiecare pereche formata din stare (piatra din poveste) si textul neanalizat de la intrare, calculati perechea urmatoare ... si tot asa ... pina se termina sirul:
Indicatie :Sa ii dam de exemplu sirul de sunete: "aeu"
Perechile ar fi: (A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "") . Sirul vid il aveti in manual notat cu litera greceasca epsilon.
2.2 Configuratii si relatii de tranzitie [pg 49 pe manualul scanat, si 48]
Ati recunoscut in povestea cu broscuta un automat finit determinist, (in sensul ca pentru orice configuratie (stare, cuvant la intrare) exista cel mult o configuratie in care poate sa ajunga un automat.
Functia de tranzitie, notata , numita functia delta este definita asa, in povestea noastra:
delta(A, a) = { B }
delta(B, e) = { C }
delta (C, o) = { B }
delta (C, u) = { D }
O puteam scrie ca in carte:
δ(A, a) = { B }
δ(B, e) = { C }
δ(C, o) = { B }
δ(C, u) = { D }
Starile formeaza multimea Q = { A,B,C,D}
Iar multimea starilor finale este : F = {D} , cea cu cercul dublu: ((D))
Starea initiala este fireste starea : A, cea cu sageata: -> (A)
Din toate acestea definim formal automatul: M = {Q, Σ , δ ,A, F}. In general A este notat cu q indice 0, indice inferior.
Numim configuratie o pereche format dintr-o stare si textul de la intrarea automatului, cel neanalizat: (s, t) din multimea Q x Σ*
Sa citim acum impreuna pagina 49. Pe multimea acestor configuratii (apartinand lui Q x Σ*) se definesc urmatoarele 4 relatii de tranzitie, din ce in ce mai complexe, iar de ultima avem nevoie express pentru a defini matematic limbajul acceptat de un automat.
Cititi Definitia 2.2 punctul
a): .... Comentez:
Pt doua stari p,q din Q si un a din Σ sigma si un w - cuvant peste Σ* (sigma stelat) ...
.... configuratia (p,aw) trece in configuratia (q,w) daca si numai daca (functia delta ii permite) adica lui δ(p,a) ii apartine q , nota bene !
Schimbarea de configuratie o notam ca o relatie pe multimea configuratiilor, si o scriem ca un T rasturnat spre stanga: |- , continuu. Vezi manualul ! La punctul:
b) ... definim o schimbare de configuratie, i se zice tranzitie, in mai multi pasi, |- k, (de fapt k este scris deasupra liniei) numarul k fiind numarul de pasi
Exercitiu: Intre prima si ultima configuratie ce relatie de tranzitie este ? Fiind mai multi pasi, este o k tranzitie ! Cat este k = ?
(A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "")
Numara tranzitiile !! K = ?
Daca nu e clar , citeste inca o data definitia de la punctul b, pg 49.
c) Dar poate ca nu ne intereseaza numarul de tranzitii, el putand fi un numar
oarecare pozitiv. Asa apare "+ tranzitia" , se citeste "+ tranzitia" si se noteaza |- + cu plusul deasupra liniei.
Definitia ei este simpla: Daca intre doua configuratii are loc un numar oarecare pozitiv de pasi de tranzitie, atunci aceasta este o plus tranzitie.
Exercitiu: Intre prima si ultima configuratie este sau nu o + tranzitie ?
(A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "")
[] a) Da este. de ce ?
[] b) Nu , nu este. de ce ?
Alegeti un raspuns.
d) Dar matematicienii merg mai departe, la ceea ce se numeste inchiderea reflexiva si tranzitiva a relatiei de tranzitie.
Pur si simplu pentru orice sir de tranzitii prima si ultima configuratie sunt si ele in relatie (deja +tranzitia garanteaza asta, ea fiind deci inchiderea tranzitiva a relatiei |- de tranzitie.)
Acum mai adaugam si ca orice pereche (s,w) este in relatie |- * cu ea insesi, ca si cum ar fi un fel de tranzitie in zero pasi, asa obtinem inchiderea reflexiva, relatia devine reflexiva - vezi teoria relatiilor cursul initial - sau la pg 6 , manual.
Definitie: (q0,w) - la noi (A,w) - A fiind starea initiala - se numeste configuratie initiala.
Acum o intrebare de control: Ced o face pe o configuratie sa fie finala:
a) Starea este din F, muyltimea de stari finale.
b) Cuvantul de la intrare este terminat, a ramas "" din el, (notat cu epsilon).
Deci asa un mecanism, format ca in poveste. din stari si tranzitii, este un dispozitiv care defineste, accepta, valideaza, cuvintele unui limbaj. I se mai spune automat acceptor de limbaj in unele carti.
3) Ce am definit eu de fapt cu aceasta poveste este multimea cuvintelor care .... stiti voi... duc proasca de la A la D... adica o multime de cuvinte anume, adica o submultime din Σ *.
Exercitiul nr 1: Care este primul cuvant solutie a problemei ?
Haideti, ganditi un minut ...
Raspuns: "aeu"
Exercitiul nr 2:Dar daca broscuta imaginara s-ar plimba de mai multe ori intre B si C, ce cuvinte s-ar forma ?
Completati multimea:
Exercitiul nr 3: Completati multimea, astfel incat sa fie exact limbajul acceptat de automat.
L = { aeu, ... , .... , }
Exercitiul nr 4: Pentru fiecare pereche formata din stare (piatra din poveste) si textul neanalizat de la intrare, calculati perechea urmatoare ... si tot asa ... pina se termina sirul:
Indicatie :Sa ii dam de exemplu sirul de sunete: "aeu"
Perechile ar fi: (A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "") . Sirul vid il aveti in manual notat cu litera greceasca epsilon.
2.2 Configuratii si relatii de tranzitie [pg 49 pe manualul scanat, si 48]
Ati recunoscut in povestea cu broscuta un automat finit determinist, (in sensul ca pentru orice configuratie (stare, cuvant la intrare) exista cel mult o configuratie in care poate sa ajunga un automat.
Functia de tranzitie, notata , numita functia delta este definita asa, in povestea noastra:
delta(A, a) = { B }
delta(B, e) = { C }
delta (C, o) = { B }
delta (C, u) = { D }
O puteam scrie ca in carte:
δ(A, a) = { B }
δ(B, e) = { C }
δ(C, o) = { B }
δ(C, u) = { D }
Starile formeaza multimea Q = { A,B,C,D}
Iar multimea starilor finale este : F = {D} , cea cu cercul dublu: ((D))
Starea initiala este fireste starea : A, cea cu sageata: -> (A)
Din toate acestea definim formal automatul: M = {Q, Σ , δ ,A, F}. In general A este notat cu q indice 0, indice inferior.
Numim configuratie o pereche format dintr-o stare si textul de la intrarea automatului, cel neanalizat: (s, t) din multimea Q x Σ*
Sa citim acum impreuna pagina 49. Pe multimea acestor configuratii (apartinand lui Q x Σ*) se definesc urmatoarele 4 relatii de tranzitie, din ce in ce mai complexe, iar de ultima avem nevoie express pentru a defini matematic limbajul acceptat de un automat.
Cititi Definitia 2.2 punctul
a): .... Comentez:
Pt doua stari p,q din Q si un a din Σ sigma si un w - cuvant peste Σ* (sigma stelat) ...
.... configuratia (p,aw) trece in configuratia (q,w) daca si numai daca (functia delta ii permite) adica lui δ(p,a) ii apartine q , nota bene !
Schimbarea de configuratie o notam ca o relatie pe multimea configuratiilor, si o scriem ca un T rasturnat spre stanga: |- , continuu. Vezi manualul ! La punctul:
b) ... definim o schimbare de configuratie, i se zice tranzitie, in mai multi pasi, |- k, (de fapt k este scris deasupra liniei) numarul k fiind numarul de pasi
Exercitiu: Intre prima si ultima configuratie ce relatie de tranzitie este ? Fiind mai multi pasi, este o k tranzitie ! Cat este k = ?
(A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "")
Numara tranzitiile !! K = ?
Daca nu e clar , citeste inca o data definitia de la punctul b, pg 49.
c) Dar poate ca nu ne intereseaza numarul de tranzitii, el putand fi un numar
oarecare pozitiv. Asa apare "+ tranzitia" , se citeste "+ tranzitia" si se noteaza |- + cu plusul deasupra liniei.
Definitia ei este simpla: Daca intre doua configuratii are loc un numar oarecare pozitiv de pasi de tranzitie, atunci aceasta este o plus tranzitie.
Exercitiu: Intre prima si ultima configuratie este sau nu o + tranzitie ?
(A,"aeu") |- (B , "eu") |- (C, "u" ) |- (D, "")
[] a) Da este. de ce ?
[] b) Nu , nu este. de ce ?
Alegeti un raspuns.
d) Dar matematicienii merg mai departe, la ceea ce se numeste inchiderea reflexiva si tranzitiva a relatiei de tranzitie.
Pur si simplu pentru orice sir de tranzitii prima si ultima configuratie sunt si ele in relatie (deja +tranzitia garanteaza asta, ea fiind deci inchiderea tranzitiva a relatiei |- de tranzitie.)
Acum mai adaugam si ca orice pereche (s,w) este in relatie |- * cu ea insesi, ca si cum ar fi un fel de tranzitie in zero pasi, asa obtinem inchiderea reflexiva, relatia devine reflexiva - vezi teoria relatiilor cursul initial - sau la pg 6 , manual.
Definitie: (q0,w) - la noi (A,w) - A fiind starea initiala - se numeste configuratie initiala.
Def: (q0,epsilon) adica (q0,ε), notat ca in manual, care la noi este (D,"") se numeste configuratie finala.
Acum o intrebare de control: Ced o face pe o configuratie sa fie finala:
a) Starea este din F, muyltimea de stari finale.
b) Cuvantul de la intrare este terminat, a ramas "" din el, (notat cu epsilon).
c) Ambele !
banuiti care e rasp. corect si complet !
Dati pagina la pg 50.
Cititi observatiile !
2.3 Limbaje acceptate de automate finite
Def 2.3: Limbajul acceptat, fie ca il notam cu L, fie ca il notam cu T(M) fie ca il notam cu L(M) este, citim impreuna rel (2.3): "multimea acelor cuvinte w peste alfabetul sigma cu proprietatea ca din configuratia initiala (q0,w) se trece dupa orice numar de pasi de tranzitie |-* intr-o configuratie finala, simultan cu epuizarea textului w, din care ramane epsilon ".
Acum puteti citi singuri despre reprezentarea tabelara de la pg 50 si reprezentarea sub forma de graf de la pagina 51.
Exercitiu: Redesenati schita ASCII art de mai sus in stilul desenului de grafuri de la pagina 51.
Studiati exemplele de la paginile 51, 52, 53.
Intrebare de control: Automatul de la pagina 52 de jos ce limbaj accepta ?
Intrebare de control: Automatul de la pagina 52 accepta sirul "11" ?
Scrieti seria configuratiilor...
Intrerupem o ora ca sa puteti citi paginile indicate ... astept intrebari si raspund la intrebari in aceasta ora ...
Lectura usoara !
[pg 54]
Stop. Partea practica, la intalnirea urmatoare.
banuiti care e rasp. corect si complet !
Dati pagina la pg 50.
Cititi observatiile !
2.3 Limbaje acceptate de automate finite
Def 2.3: Limbajul acceptat, fie ca il notam cu L, fie ca il notam cu T(M) fie ca il notam cu L(M) este, citim impreuna rel (2.3): "multimea acelor cuvinte w peste alfabetul sigma cu proprietatea ca din configuratia initiala (q0,w) se trece dupa orice numar de pasi de tranzitie |-* intr-o configuratie finala, simultan cu epuizarea textului w, din care ramane epsilon ".
Acum puteti citi singuri despre reprezentarea tabelara de la pg 50 si reprezentarea sub forma de graf de la pagina 51.
Exercitiu: Redesenati schita ASCII art de mai sus in stilul desenului de grafuri de la pagina 51.
Studiati exemplele de la paginile 51, 52, 53.
Intrebare de control: Automatul de la pagina 52 de jos ce limbaj accepta ?
Intrebare de control: Automatul de la pagina 52 accepta sirul "11" ?
Scrieti seria configuratiilor...
Intrerupem o ora ca sa puteti citi paginile indicate ... astept intrebari si raspund la intrebari in aceasta ora ...
Lectura usoara !
[pg 54]
Stop. Partea practica, la intalnirea urmatoare.
-----------------------------------------------
Raspunsuri la exercitii, si comentarii.
Indicatii pt un desen corect:
Raspunsuri la exercitii, si comentarii.
1) Ce șir de sunete face broasca?
Corect:Sunetele le fac turistii, ei ofera un sir de sunete care pune "broasca" - a se citi automatul - in miscare, astfel ca sa ajunga de la starea initiala la cea finala.
R: șirul este {a, e, o, u}.
(gresit pusa intrebarea , gresit raspunsul)
(gresit pusa intrebarea , gresit raspunsul)
Broasca face oac! (glumeam)
Corect:Sunetele le fac turistii, ei ofera un sir de sunete care pune "broasca" - a se citi automatul - in miscare, astfel ca sa ajunga de la starea initiala la cea finala.
2) Exercițiul numărul 1
R: aeu
Corect !
3) Exercițiul numărul 2
R: a urmat de secvența eo de n ori , urmat de eu.
Se va scrie { a(eo)n eu } unde n este un fel de exponent al lui (eo).
Corect asa.
Exercițiul numărul 3
R: L = { aeu, aeoeu, aeoeoeu etc. }
Corect asa.
Indicatii pt un desen corect:
Acum la desen: Liniile sunt continue, iar cercurile din jurul A,B,C, D sunt complete, cel din jurul lui D este dublu !
Niciun comentariu:
Trimiteți un comentariu