Buna ziua si bun venit la cursul de LFA si compilatoare.
Recapitulare:
Suntem deja dincolo de jumatatea semestrului, cand alte facultati dau examenele partiale.Dat fiind ca v-am tinut la curent cu predarea regulata a teoriei si ati primit si manualul teoretic de Limbaje Formale si Teoria Automatelor precum si cel practic de Constructia Compilatoarelor cu Flex si Bison... e ,momentul sa vedem unde am ajuns.
TEORIE
1) La Teorie am terminat (de mult) de predat gramaticile si suntem in capitolul de teoria automatelor, va rog sa revedeti TOATE postarile LFA (fie ca sunt notate IFR fie ca nu, de pe blog, pina la zi.
Voi continua predarea regulata a teoriei, pe blog, luni dupa amiaza.
Atentie: Sunteti vulnerabili la exercitii cu gramatici ! Dintre ele se remarca doua categorii de exercitii:
a) Se stie gramatica, aflati limbajul generat.
b) Se stie limbajul generat, aflati care este o gramatica (eventual de un anume tip) care il genereaza.
Grupa IFR are in sectiunea suport a site-ului IFR, manualul de Limbaje Formale si Tehnici de Compilarea al Prof. D.M., gasiti exercitii la pg 20.
Un exemplu simplu de exercitiu: [pg 20, paragraf 1.5, ex(b)]
Gasiti limbajul generat de gramatica, precizand tipul gramaticii, conform clasificarii Chomsky.
N = {S} Ce era acesta , ziceti repede !
T = {a,b} Nu-s notati cu sigma dar ce sunt ? Ziceti repede !
P = {S -> aSb| ab} Ce sunt aceste P ? Ziceti repede ?
Nu ati putut zice ce sunt, recititi capitolul despre gramatici sau revedeti filmul despre gramatici.
Intrebare de control: Cum s-ar scrie altfel multimea p, impartind-o in reguli scrise separat. Scrieti voi si trimiteti o poza a solutiei. Multumesc.
Pozele pot fi postate ca dovada de activitate.
Puteti citi regulile din P ? cum le-ati citi ?
Intrebare: Care din regulile din acest P, se aplica prima ?
P = {S -> aSb,
S -> ab}
Intrebare: este acelasi P ?
a) Da ! De ce ?
b) Nu, de ce ?
Dat fiind ca S -> ab este o regula care face sa dispara neterminalul S, si este singura de acest fel, e clar ca ea se va aplica ultima.
Deci sunt posibile doua feluri de derivari in gramatica G de mai sus: G = (N,T,P,S).
1) Derivarea S=> ab care genereaza cuvantul ab. ab apartine limbajului L(G), generat de gramatica.
2) Derivari care aplica prima regula de n-ori si apoi a doua regula o data. Acestea sunt derivari de forma:
S=> aSb => aaSbb => aaaSbbb => aaaabbbb.
In general derivari de forma:
S=> aSb => aaSbb => aaaSbbb => aaaabbbb.
Ce proprietate au sirurile de a-uri si b-uri formate aici ?
Raspuns: Au cate b-uri , atatea a-uri.
Concluzie: L este limbajul cuvintelor de forma { aa...ab...bb | numarul de b-uri egal cu numarul de a-uri, si acest numar n este >0 } Observati ca nu pot obtine stringul vid.
Exercitiu de notatie: Daca scriu n a-uri ca fiind: a la puterea n, SCRIETI !, cum s-ar nota limbajul de mai sus ?
Dati pagina la pagina [21 manualul domnului D.M - il au cei de la FR,doar] . Cititi limbajul de la ex.3. punct (e). Este acelasi ?
Prin ce difera ?
Ati raspuns un c in plus la mijloc, intre a-uri si b-uri ? Ok.
Apropos: Care ar fi gramatica acestui limbaj format din cuvinte de forma :
aaacbbb ?
L = {aa..acb..bb | acelasi numar n de b-uri si de a-uri, n>1}
Raspuns: Ia vedeti gramatica:
N= {S}
T ={a,b,c}
P = { S-> aSb , S-> c }
Este ok ?
Dar gramatica:
N= {S}
T ={a,b,c}
P = { S-> aSb , S-> abc }
Este ok ?
In care dintre ele se obtine prin generare din S, cuvantul format din litera c ? care dintre gramatuci este potrivita si care nu ?
Ora 10:00:
Sa mai luam un exemplu, notez si "gandurile".
Paragraful 1.5 (manualul domnului D.M. pentru FR) , exemplul (d) pg 20.
N = {S,A,C} ... aha... start... un A, oare ce inseamna si ceva numit C
... o fi vreo cifra ?
T = { +,-,0,1,2,...9} ... avem +,- cifre printre terminali..
... aha... o gramatica a numerelor, de pare
... sau cev a cu secvente de cifre si semne...
... vor fi fiind expresiii ? Sa vedem regulile :
P = { S-> A | +A | -A, ... probabil numere, cusem +, cu semn - sau fara
... oare neterminalul A inseamna numar ? Va intreb !
A -> AC , ... aha ... un A mai lung are un C (o fi o cifra ?) in plus la
sfarsit !
A -> C , ... sau un A este format dintr-un singur C ...
... Ar putea fi regula : "Un numar poate fi format
din o cifra".
C -> 0|1|2|...9} ... Clar: C sunt cifrele zecimale.
... A sunt sirurile de cifre care formeaza un numar
fara semn.
... S sunt sirurile de cifre care formeaza un numar
cu semn.
}
Evident, limbajul produs de G, se zice generat de G, este: L = { 0, +1, -1, 1, +2, -2, 2 , +3, -3, 3 samd }
Este corect raspunsul de mai sus ?
Nu ! Gasim imediat o alta secventa, care nu e in multimea de mai sus dar este generata de gramatica ! Observati ca se poate gresi foarte usor.
S => +A ... am aplicat S->+A
S => +A => +C ... am aplicat A->C
S => +A => +C => +0 ...am aplicat C=> 0
Similar putem obtine:
S => -A => -C => -0 ...am aplicat C=> 0
Concluzia este ca limbajul nostru include cel putin: {+0,-0, 0}
Deci este cel putin : L = { 0,+0, -0, +1, -1, 1, +2, -2, 2 , +3, -3, 3 samd }
Dar stai ! Putem deriva si siruri mai lungi care incep cu +0 sau -0, cum ar fi:
+0127
S => +A ... am aplicat S->+A
S => +A => +AC ... am aplicat A->AC
S => +A => +AC => +ACC ...am aplicat A->AC
S => +A => +AC => +ACC => +CCC ...am aplicat A->C
... si daca mai aplica C-> 0 C->1 C->7 in cele trei locuri...
... obtin dupa 3 pasi de =>
S => +A => +AC => +AAC => +ACC => +CCC => ... => +0127
Concluzia: L este limbajul secventelor de oricate cifre nule sau nenule, precedate de + , - sau nimic.
Ar trebui demonstrata si incluziunea inversa, adica faptul ca daca un cuvant este generat de limbaj el nu poate avea decat o anumita forma.
Se vede imediat ca un astfel de cuvant incepe cu +, - sau primul caracter a ceva derivat din A care este si primul caracter a ceva derivat din C care este cifra.
Ca urmare derivarile posibile sunt:
S=> +A ... si expandam A, pina dispar neterminalii
S=> -A ... si expandam A , pina dispar neterminalii
Acuma intrebarea este exact ce se poate face cu A, dar dat fiind ca am o singura regula cu exact un A in stanga si exact un A in dreapta (A->AC) e clar ca ea se poate aplica succesiv de (sa zicem n-1 ori, pt orice n) si atat tot.
A =>AC => ... => ACC ...C Iar fiindca A va dispare odata, sa zicem dupa n-1 pasi de aplicare a (A->AC),
A =>AC => ... => ACC ...C => C....C cu n de C
care prin transformarea C-urilor in cifre...
dau
A =>AC => ... => ACC ...C => C...C => ... => c...c - unde c-urile suntn cifre distincte.
Clar:
Deci este cel putin : L = { 0,+0, -0, +01, -01, 01, +2, -2, 2 , +3, -3, 3 samd }
pe scurt este limbajul secventelor de orice si oricate cifre zecimale , inlusiv zero, precedate de +,- sau nimic.
Alte exercitii: Pot fi inspirate de gramaticile altor limbi:
De exemplu intr-o limba straina (aici japoneza) putem avea mici exercitii de formare a unor propozitii, iar voi softistii puteti contribui la crearea unor manuale interactive de Japoneza, daca doriti:
S -> PronumeDemonstrativ Particula Obiect Verb . (toate sunt neterminali)
PronumeDemonstrativ -> KORE | SORE | ARE (acesta de linga mine, acesta de
linga tine ,acela departe de noi)
Particula -> WA
Obiect -> MADO | KIKU (fereastra, crizantema)
- e un complement direct de fapt
Verb -> DESU (verbul copulativ a fi la prezent).
Derivati in aceasta gramatica propozitiile:
KORE WA MADO DESU .
ARE WA KIKU DESU.
Derivati alte propozitii:
(dupa un manual de la doamna Angel Hondru, transmit multumiri autoarei).
Exercitiu de programare: Scrieti un program care, pe baza alegerii regulilor gramaticale, chiar genereaza aceste texte. Scrieti alt generator de texte bazat pe o gramatica.
Exercitiu de implementare: Scrieti regulile gramaticale de mai sus , in formatul acceptat de Bison. Adaugati fisierul Lex . Analizati textele de mai sus cu analizatorul generat de Bison si Flex.
Exercitii: luati dintr-un manual de limba straina niste exercitii "filling the blanks" de completare a spatiilor cu alte cuvinte si scrieti gramatica acelor exemple. (Nu orice exemple sunt suusceptibile pt acest exerciti, doar cele ca mai sus.)
TEORIA AUTOMATELOR
Am predat deja teoria automatelor finite deterministe, am insa de adaugat despre automatele finite nedeterministe cate ceva si de continuat capitolul de teoria automatelor (stari accesibile, stari productive etc).
Urmeaza sa prezentam ceva foarte important pentru programatori: expresiile regulare, care sunt niste notatii in forma de expresie (dar cu niste operatori speciali, nu +, -,*,/) si se folosesc din toate limbajele de programare. Urmariti blogarile cursurilor LFA din fiecare LUNI in continuare. O problema teoretica va fi cum de sunt aceste expresii echivalente cu automatele, o problema practica va fi chiar determinarea expresiei cand avem desenat automatul, sau invers , gasirea automatului si a limbajului cand stim expresia regulara (asa ceva e mai usor).
Sa facem cateva exercitii impreuna, din manualul profesorului D.M. (il au colegii de la F.R). pg 48, paragraf 2.5, Probleme propuse.
1. Construiti automatele finite pentru recunoasterea limbajelor (citez din carte)
(a) L = {PSDR, PNL, PUNR} - asemanarea cu numele partidelor e PUR intamplatoare, asemanarea unui cuvant din ultima propozitie cu un nume de partid este pur intamplatoare. samd
Pai, hai sa vedem
(nota, un asemenea automat, scris ca expresie regulara, adaugat intr-un program PHP ar putea fi parte a unui soft care verifica sau intercepteaza postari cu acele cuvinte pe un site universitar, sau a unuia care adauga , dupa un timp, aprecieri sau non aprecieri acelor texte,in acele puncte asa cum a fost un celebru virus) deci problema este reala.
Observatie: Toate incep cu litera P deci din starea initiala, plecam (sarind ca o broasca - vezi povestea cu broasca montana), in starea urmatoare:
P
--> (0) ----------> (1)
Acum este simplu, din starea (1) pleaca trei "sageti" , arce, catre trei stari distincte. Decizia o luam dupa a doua litera: S, N, U
P S
--> (0) ----------> (1) -----> (2)
| \
| \N
U | _\|
| (3)
\|/
(4)
Pe dvs. va rog sa desenati liniile continui , nu punctate ca in acest ASCII ART.
Dupa aceea este usor, din starile 2,3 4 pleaca aceste succesiuni de arce si stari:
D R
(2)----------> (5) ----------->((6))
L
(3)----------> ((7))
N R
(4)----------> (8) ----------->((9))
Desenati starile inconjurate de cercuri complete.
In final automatul arata asa:
P S D R
--> (0) ----------> (1) -----> (2) ----------> (5) ----------->((6))
| \
| \N
U | _\| L
| (3)----------> ((7))
\|/
(4)----------> (8) ----------->((9))
N R
Exercitiu: Desenati corect automatul si trimiteti desenul, pe e-mail.
Exercitiu: Reprezentati automatul in alt mod.
Partea despre compilatoare:
Aici avem mai multe lucruri de facut... Incep o pagina noua.
Niciun comentariu:
Trimiteți un comentariu