Azi, ca antrenament, incepem sa lucram exercitii despre automate,
vom reveni la capitolul de constructie a compilatorului in saptamana a XII-a.
Ca pregatire teoretica minimala pentru aceasta serie, musai cititi:
Din capitolul de curs despre automate, pg 50-52-54 (ebook pg 52-56).
Deschideti manualele la pagina 69 [pg 71 ebook].
Sa vedem cam cu ce exercitii isi antreneaza autorul cartii studentii lui,
fireste voi incepe cu cele mai simple.
Paragraf 2.9 Ex1:
Sase reprezinte tabelar automatele.... dar nu am mai facut asta pina acum !
Indicatie: Uitati-va la exercitiul nr 2: Acolo aveti un ex de automat reprezentat tabelar.
Ideea e simpla:
____|__________|__
| |
| |
| |
Pe coloana din stanga sunt starile: la noi p si q.
____|__________|__
| |
p | |
q | |
Pe linia de sus sunt simbolurile alfabetului: la noi sunt a si b.
____|__a _b_ __|__
| |
p | |
q | |
In tabel sunt plasate starile in care ajung, atucni cand am o anume stare a automatului, din stanga, si un anumit simbol la intrare, de sus:
____|__a _b_ __| F_
| |
p | q p | 0
q | p p | 1
Ne uitam pe diagrama: starea p si litera a ma duc in q !
Ne uitam pe diagrama: starea p si litera b ma duc in p !
Ne uitam pe diagrama: starea q si litera a ma duc in p !
Ne uitam pe diagrama: starea q si litera b ma duc in p !
Ultima coloana este coloana starilor finale, si exprima valoarea de adevar
a propozitiei: Aceasta stare este finala.
Starile finale erau acelea la care cercul e dublu, se vad imediat pe graf.
Deci in coloana finala puneti un 1 in dreptul luiu q si un zero in dreptul lui p.
Si asa arata automatul nostru reprezentat ca un tabel.
____|__a _b_ __| F_
| |
p | q p | 0
q | p p | 1
Exercitiul numarul 1.b: Automatul este cel din poza 1 b).
Transcrieti-l sub forma de tabel:
____|__________|__
| |
| |
| |
Acesta e tabelul gol, nu uitati, in stanga starile, sus literele alfabetului, in mijloc starile noi si in coloana dreapta starile finale.
____|__a___b___|__
| |
p | q b |
q | |
r | |
Din p cu a ajung in q !
Din p cu b ajung tot in p !
Urmeaza :
Din q cu a ajung in p !
Din q cu b ajung in starea r !
Din r cu a ajung in p !
Din r cu b la intrare ajung in q !
____|__a___b___|_F_
| |
p | q b | 0
q | p r | 0
r | p q | 1
Randul vostru: treaba este simpla deocamdata, desenati tabelele pentru automatele de la punctele c si d din imagine.
Completati-le si trimiteti pozele pe e-mail:
Va las timp sa desenati tabelele si sa le completati, cam atat cat imi ia si mie sa le completez.
c) Transcrieti-l sub forma de tabel:
____|__________|__
| |
| |
| |
Intrebari de control:
Ce ati scris pe coloana stanga ?
i) p q r s
ii) p q r t
Ce ati scris pe randul lui q (al transzitiilor ce pleaca din starea q) ,
in pozitia a II-a, cand la intrare este litera b ?
i) strea p
ii) starea q
iii) nici o stare
iv) multimea vida !
Acum va las timp sa va ocupati de punctul d).
d) Transcrieti-l sub forma de tabel:
Cum se numesc starile, cititi in cele patru cercuri ale lor :
..... si scrieti pe coloana din stanga:
.....
Care este alfabetul de intrare (sigma) ? Uitati-va la etichetele de pe sageti !
Se scriu pe marginea de sus !
____|__________|__
| |
| |
| |
| |
Elemente de control:
i) Aveti in tabel o linie cu doua multimi vide ? E clar de ce este acolo ?
ii) Aveti in tabel doi de r r , unul sub altul in coloana a II- ? Ce inseamna asta vi-s a vis de arcele etichetate cu b ?
ii) Aveti in tabel doi de p unul sub altul ?
Daca ati raspuns negativ refaceti, va rog, exercitiul.
Iar daca adaugam si multimile vide in tabele, arata asa, (multumesc D. pt img.)
In img: Sol de la Alex.F.
Gasiti totul pe blog.
video4linux.blogspot.com.
Incepem in doua minute seria a a II-a de exercitii:
Sa luam exercitiul 2 pg 71:
Reprezentati sub forma de graf:
a) Desenul se face imediat....
din coloana stanga luam starile si desenam celetrei cerculete, primul este starea initiala.
---> (p) (q) (r)
Desenati si voi si trimiteti poza.
Serios, daca nu va faceti aceste mici exercitii si nu trimiteti imagini, nu veti avea din ce obtine o nota la partea practica, mai ales ca unii nu ati lucrat nici la compilator prea mult. Sunteti avertizati !
Acum sa desenam impreuna:
p cu a ma duce in starea q, deci sageata de la p la q etichetata cu a:
a
---> (p) ------------------> (q) (r)
Mai departe: p cu b ma duce in p ( a doua pe rand 1, tabela a)):
Deci desenam o bucla de la p la p, o sageata ce pleaca din p si ajunge tot in p.
a
---> (p) ------------------> (q) (r)
/ \
|__|
Puneti varf la sageata in ce parte doriti. Si eticheta b pe sageata.
a
---> (p) ------------------> (q) (r)
/ \
|__|
b
Acum randul 2 din tabel: q cu a la intrare ma duce in r.
a a
---> (p) ------------------> (q) --------------------> (r)
/ \
|__|
b
Iar q cu b la intrare ne duce in starea p deci sageata inversa de la q la p.
__________
/ b \
|/_ \ a
---> (p) ------------------> (q) --------------------> (r)
/ \ a
|__|
b
starea r si cu simbolul a ma duce in starea p, randul 3 din tabel.
__________
\ / b \
_\| |/_ \ a
---> (p) ------------------> (q) --------------------> (r)
| / \ a /
| |__| /
| b /
| /
\____________________________________ /
a
Iar r cu b ma duce tot in r deci pun o sageata in bucla pe starea r.
__________ __
\ / b \ / \
_\| |/_ \ a | |
---> (p) ------------------> (q) --------------------> (r) | b
| / \ a //|\ |
| |__| / \ __/
| b /
| /
\____________________________________ /
a
Desenati fireste tot automatul cu linii continue nu cu sageti intrerupte.
Ne ajuta cineva dintre voi cu o imagine ?
in tabela 2. a) ....
Vlad P. ne trimite doua imagini din caietul lui de LFA (automate):
Primesc o intrebare: "Nu prea stim ce avem de facut ?"
Aveti de rezolvat exercitii de la pg 69 (pg fizica, pe ebook e +2=pg71).
Pentru Ex 1, ati citit probabil capitolul de curs despre automate,
la pg 50-52-54 (ebook pg 52-56) aveti felul cum se reprezinta automatele tabelar.
Ati avut de citit acest set de paragrafe , cu ocazia cursului (pg blog anterioara).
Exemplu de rezolvare ati avut la pg 53(pg 55 ebook):
In imagine: Pg 55 -ebook, exemplu de reprezentare de automat in doua feluri.
In acest moment astept desene de automate de la dvs, inclusiv cel de la 2.b:
Suntem si pe Teams, ati intrat ? Intrucat nu a intrat nimeni pe Teams, sau s-a iesit foarte repede, ramanem pe blog. De altfel Teams a dat erori azi.
Sa trecem la alt fel de exercitii:
Stati putin sa aleg alt fel de ex. Iata un ex de construire a unui automat care accepta un limbaj. Va amintiti de acele site-uri care nu primesc o adresa de email daca nu e corecta sau daca nu are in ea ceva, de exemplu @ ?
Ex 4 pg 70 [pg 72 ebook]
Ex 4. ca in carte, marit sa se vada ...
hai sa gandim oleaca la el impreuna...
Cum credeti ca se rezolva .... ?
Cuvintele din acest limbaj, acceptat de automat, par sa aiba trei parti succesive:
L = { w | w = partea_1 0 0 partea_a_2_a }
S-o luam pe bucatele:
Un automat care recunoaste 0 urmat de zero e usor de facut ? Il vedeti in minte ?
Uitati, nu mai pun paranteze la stari, dar C este finala, cerc dublu, A, B sunt cu cercuri simple:
0 0
--> A -------> B ------> C
E clar ca trebuie un 0 sa "ne sara broasca" in starea B si inca un zero sa ne sara in starea finala C. Ok ?
Dar ce fac cu partea I si a II-a , formate din orice caractere...
Un automat format dintr-o bucla pe starea (finala) si cu orice simbol din alfabet pe arc (adica pe sageata) ar rezolva pb. Aici A este o stare finala. (Trimiteti desene, ca sa completam blogul, va rog)
--> A _
/ |\
| |
|__ __|
0,1
E clar ca oricati de 0 si 1 ar veni , "broasca din poveste" adica automatul "trece de pe piatra A pe piatra A" - trece din starea A in starea A... si tot asa (tot pe loc pe loc pe loc, dar consumand literele de la intrare) ...
.... imaginati-va broasca sarind pe starea A in timp ce in fundal pe un ecran se deruleaza banda cu literele de la intrare pe masura ce se consuma.
Pt acest automat limbajul este {0,1}* adica orice secventa de 0 si 1.
La final pentru partea a doua ....... ne mai trebuie un automat de acesta.
--> C _
/ |\
| |
|__ __|
0,1
Si cand le combinam pe toate obtinem solutia, mai greu de desenat pt mine in ASCII! Atentie, A, B au cerc simplu, C este stare finala are cerc dublu.
0 0
--> A _ --------> B ----------------> C _
/ |\ / |\
| | | |
|__ __| |__ __|
0,1 0,1
daca pun paranteze si nu cercuri la stari, cum e tipic, ar arata asa:
0 0
--> (A) _ -------> (B) ------------> (( C)) _
/ |\ / |\
| | | |
|__ __| |__ ___|
0,1 0,1
Cum merge acest automat pt a accepta un cuvant care are sigur doi de zero
De ex 11110111001110111 ?
Pina aici "bate pasul" in A .... (glumeam) dar e ok:
11110111001110111
La primul zerou din cei 2 sare in starea B
11110111001110111
La al doilea trece in starea C.
11110111001110111
Si de acum tot ce ar veni , tot trece din C in C pina la sfarsit, cand
starea C fiind finala si cuvantul terminat, gata, este acceptat cuvantul de automat (, recunoscut ca bun!).
Cine face exercitiul 5 ?
Atentie , n>=0, poate fi si zero, m>=1, deci am un 1.
1
--> (A) _ ----------------------------> (( C)) _
/ |\ / |\
| | | |
|__ __| |__ ___|
0 1
Intrebare de control: Este bun asa ?
a) da
b) nu
c) va trimit eu un desen...
Cine face exercitiul 6 ?
Timpul a expirat!
Continuati pregatirea pentru examen rezolvand, pe termen lung, problemele de la finalul capitolului despre automate.
Gluma zilei:
Circula o anecdota in care profu' de matematica avand de predat suma unghiurilor in triunghi face 3 triunghiuri pe tabla si intreaba:
- Ce au in comun ?
Si o voce din clasa raspunde: Sunt toate facute cu creta rosie !
:)) :))) :))) :)
Niciun comentariu:
Trimiteți un comentariu