[exercitii de la. pg 43 din ebook-ul M si altele de la pg 22 din alta carte de D.Mircea]
Suntem in saptamana a 10-a. Pentru astazi "indraznesc" sa va propun cateva obiective:
1) Sa va pun la indemana cateva manuale alternative in limba romana, le-ati primit deja pe e-mail. Va rog intai sa le "frunzariti" si sa imi raspundeti la intrebarea care vi se pare mai "citibil" decat e-book-ul trimis initial, dupa care facem cursul.
Intrebare de control: Unul din manuale a fost probabil scanat si trecut printr-un software OCR, ceea ce il face de calitate indoielnica, tipografic vorbind. Care ?
2) Sa facem o recapitulare sau mai bine zis niste exercitii recapitulative la capitolul gramatici, (stiu, am mai facut). As dori sa ma asigur ca macar cele mai simple exercitii sunt pe deplin intelese de toata lumea.
3) Va invit sa compuneti propriile exercitii si sa le trimiteti, pentru o colectie de probleme (pentru examen ?? - asa ceva nu promit in scris). Un cel mai greu exercitiu care ati sti sa il faceti, insotit de un cel mai usor exercitiu care n-ati sti sa il faceti pot fi de ajuns.
Exercitii din primul e-book trimis (cel scanat al prof. M.) pg 43, probleme propuse.
Ex 0. (Cel scris in creion la inceputul listei) [pg 43 - pg 45 pe ebook]
Definiti multimea identificatorilor unui limbaj cu ajutorul unei gramatici.
Intrebare de control: Ce era un identificator intr-un limbaj de programare ?
Raspuns: O secventa de litere si cifre care .... completati dumneavoastra.
Sugesti de rezolvare: Cand aveti de construit gramatica unui limbaj ale carui cuvinte sunt formate din doua parti , partea A si partea B, este rezonabil sa
definiti o prima regula S -> AB si sa impartiti problema in alte doua probleme:
Sa dam o gramatica pentru limbajul acelor texte de tip A, produse din A,
si o alta pentru limbajul acelor texte B produse din B. Apoi sa le reunim cumva, cu atentie sa nu coincida numele de neterminali.
Mai pe romaneste:
O secventa de litere si cifre care incepe cu o litera este formata din: (1)
- inceput care este o litera (2)
- continuare care poate fi: (3)
-- o alta cifra sau litera (4)
-- o prima cifra sau litera urmata de o alta continuare. (5)
Sa le dam niste nume de neterminali acestor feluri de texte:
- inceput care este o litera ---> notat cu A
- continuare care poate fi: ---> notata cu B
-- o alta cifra sau litera ----> notata cu C
-- o prima cifra sau litera urmata de o alta continuare.
Aproape e gata, sa nu il uitam pe S simbolul de start, cel al multimii tuturor textelor. ----->notat cu de obicei cu S
Este momentul sa vedem cum formulam regulile:
Din (1) deducem ca avem o regula:
S -> AB
Din (2) deducem ca avem o regula:
A -> 'a'|'b'|'c'|...|'z'|'A'|'B'|'C'|...|'Z'
Din (3),(4) si (5) avem:
B -> CB
B -> C
C -> '0'|'1'|'2'|...|'9'|'a'|'b'|'c'|...|'z'|'A'|'B'|'C'|...|'Z'
Punem impreuna toate regulile in multimea P:
P = { S -> AB , A -> 'a'|'b'|'c'|...|'z'|'A'|'B'|'C'|...|'Z' , B -> CB
B -> C , C -> '0'|'1'|'2'|...|'9'|'a'|'b'|'c'|...|'z'|'A'|'B'|'C'|...|'Z' }
Alfabetul
Σ ={ 'a' ...'z', 'A', .... , 'Z' , '0' , '1', ... , '9'}
Neterminalii (ii culegem din reguli):N = { S, A, B, C }
Simbolul de start: este fireste S, capul regulii ce da forma generala a textelor.
Iar toate patru impreuna definesc o gramatica: G = {N, Σ, P, S }
Exercitii din primul e-book trimis (cel scanat al prof. M.) pg 43, probleme propuse.
Ex 1. [pg 43 - pg 45 pe ebook]
Sa se defineasca multimea numerelor naturale ca limbaj generat de o gramatica:
Intrebare de control: Din cate parti sunt formate numerele naturale, scrise cu cifrele obisnuite, zecimale ?
Indicatie: Ce e aparte la prima cifra ? Este diferita de .... ?
Este exact la fel: o prima parte formata dintr-o cifra nenula si
o a doua parte formata
dintr-una sau mai multe
cifre oarecare, inclusiv zero.
Si exact la fel gandind obtineti gramatica (am sa comentez putin regulile)
P = { S -> AB , //Textele au partea A si partea B
A -> '1'|'2'|...|'9' , // Partea A e dintr-o cifra de la 1 la 9
B -> CB // Partea B e formata dintr-o parte B mai scurta
// ... si o parte C in fata ei (adica o cifra)
B -> C , // Sau doar dintr-o singura parte C (adica o cifra)
C -> '0'|'1'|'2'|...|'9' // Care parte C este formata dintr-o cifra, da si 0.
}
Alfabetul
Σ ={ '0' , '1', ... , '9'}
Neterminalii (ii culegem din reguli):N = { S, A, B, C }
Exercitii din primul e-book trimis (cel scanat al prof. M.) pg 43, probleme propuse.
Ex 2. Fie gramatica G = (N,Σ P,S), unde N = {S,C} , Σ ={ a,b} si
P = { S -> ab, S -> aCSb , C -> S , C -> bSb, CS -> b }
Sa se studieze daca ababab apartine limbajului generat de gramatica, notat de obicei L(G).
Nota: (ab) la a doua, se intelege ca abab.
Intrebare de control: Cum vi se pare problema ?Sa se studieze daca ababab apartine limbajului generat de gramatica, notat de obicei L(G).
Nota: (ab) la a doua, se intelege ca abab.
a) banala
b) rezolvabila cu un algoritm
c) presupune creativitate
Raspuns c.
De stiut pt alte probleme:
Daca gramatica ar fi monotona, adica regulile ar lungi mereu secventele de simboluri, as putea incerca un backtracking , incercand la fiecare pas
toate regulile posibile, pina cand cuvintele obtinute se lungesc mai mult decat cuvantul dat.
Miniexemplu:
S -> aSb
S -> cSd
S -> ab
S -> cd
Aratati ca acdcdb nu apartine limbajului.
Va las sa va ganditi daca:
1) puteti obtine ababab aplicand regulile
2) sau gasiti un contraargument
Timp de gandire 15 minute.
Are cineva vreo idee ??
Haideti sa ne uitam mai cu atentie la reguli:
P = { S -> ab,
S -> aCSb ,
C -> S ,
C -> bSb,
CS -> b }
Ce observati ?
P = { S -> ab, //Regula aceasta adauga un a si un b
S -> aCSb , //Regula aceasta adauga un a si un b
C -> S , //Regula aceasta nu adauga nici un a si nici un b
C -> bSb, //Regula aceasta adauga doi de b
CS -> b } //Regula aceasta adauga un b
Daca doresc sa am in sirul final un numar echilibrat de a si de b ce reguli ar trebui sa folosesc, tinand cont ca nu am reguli al caror efecte sa se compenseze intre ele ?
Doar S -> ab, //Regula aceasta adauga un a si un b
S -> aCSb , //Regula aceasta adauga un a si un b
C -> S , //Regula aceasta nu adauga nici un a si nici un b
Atat.
Cum regula a doua creaza doi neterminali iar conform regulilor 3 si 1 acestia produc macar un a si un b, de cate ori ESTE NECESAR sa aplicam regula 2 pentru a obtine 3 de a si 3 de b in sirul final ?
Ati raspuns cat :
a) o data
b) de doua ori
c) de trei ori
Corect : o data.
S=> aCSb => aSSb // obligatoriu asa ca sa obtin 3 de a si 3 de b
...
dar in acest caz aplicand regula 1 de doua ori:
S=> aCSb => aSSb =>aababb
ordinea a-urilor si b-urilor dorita de noi nu se obtine.
Concluzia: In singurul caz in care am obtine 3 de a si 3 de b, sirul ar fi
aababb si nu ababab, deci ababab nu apartine limbajului.
Atentie: Acest gen de exercitii pot fi uneori foarte grele, in afara cazului cand reusim sa obtinem cuvantul dorit, prin derivare, caz in care nu mai e nevoie sa demonstram nimic.
Un exercitiu asemanator, dar cu o gramatica monotona:
S->ab
S-> abSS
S ->bbS
Fie un cuvant format din 6 litere, a-uri si b-uri numarate impreuna. Prezentati o metoda generala de a stabili daca acel cuvant apartine limbajului.
Indicatie: generati toate cuvintele pina la lungimea = 6, prin backtracking.
O simpla inspectie a multimii va decide daca cuvantul dorit e acolo sau nu.
Sa incercam ceva si din alta carte (D.Mircea, pg 21-22 ex3, cei de la FR au cartea).
Enunt comun: Gasiti gramatici pentru generarea urmatoarelor limbaje;
Varianta (s): L = {A,B,C, ....Z}
Indicatie: daca limbajul e finit, e suficient sa derivam din S, direct, toate variantele de texte ce se vor obtine, fiindca gramatica astfel obtinuta ramane tot finita.
Limbajul nostru are numarul de texte produse |L| = | {A,B,C, ....Z}| = 26 , finit in orice caz, si oricum am lua alfabetul, cu litere romanesti sau fara.
Concluzia: regulile vor fi:
S ->'A'
S->'B'
S->'C'
...
S ->'Z' ceea ce se mai putea scrie:
S-> 'A'|'B'| ...|'Z'.
Sa incercam ceva si din alta carte (D.Mircea, pg 21-22 ex3, cei de la FR au cartea).
Enunt comun: Gasiti gramatici pentru generarea urmatoarelor limbaje;
Varianta (r): L = {w | w octet ce reprezinta un numar par} - probabil cu alfabetul 0,1.
Solutie: Octetul are 2 la puterea 8 = 256 de variante de a fi scris, cele pare sunt 128, deci putem face o gramatica cu 128 de reguli, exact ca la ex anterior.
Solutia2: Octetul binar care reprezinta un numar pare (e cam la fel ca numarul scrierea zecimala a unui numar multiplu de zece) se termina cu 0 si are la inceput zerouri si unitati in numar de 7.
Partea intai: sapte cifre care pot fi zerouri sau unitati, le notam cu C.
partea a doua: un zero.
S -> AB
A ->CCCCCCC
B -> 0
C -> 0|1
Alfabet: {0,1}
Neterminali: {S,A,B,C}
Intrebare de control: Puteti simplifica setul de reguli pina ajungeti la o singura regula ?
Pauza s-a terminat, intram, ca la meci in prelungiri, stiu, aveti curs la 3!
Oricum, blog-ul va asteapta si dupa curs.
Sa incercam ceva si din alta carte (D.Mircea, pg 21-22 ex3, cei de la FR au cartea).
Enunt comun: Gasiti gramatici pentru generarea urmatoarelor limbaje;
Varianta (q): L ={w0w' | w din {0,1}*, w' este w scris invers }
Solutie: Sa vedem intai cateva cuvinte din limbajul L:
L = { 0, 000, 101, 0010100, samd}
Observati cum 0-ul initial tot produce cate o cifra, aceeasi, simultan in stanga si dreapta...ca si cum ar fi un neterminal. De unde ne vine imediat ideea:
S -> 0S0
S -> 1S1
S -> 0
Acestea-s toate regulile ? Da.
Sa incercam ceva si din alta carte (D.Mircea, pg 21-22 ex3, cei de la FR au cartea).
Enunt comun: Gasiti gramatici pentru generarea urmatoarelor limbaje;
Varianta (p): L = { w din {0,1}* | w contine maxim 2 de 0 }
Solutie: Aici avem un cuvant format din 5 parti:
- ce e inainte de primul 0 si e format numai din 1 sau nu este deloc
- primul 0
- ce e dupa primul 0 si e format numai din 1 sau nu este deloc
- al doilea 0
- ce e dupa al doilea 0 si e format numai din 1 sau nu este deloc
sau din trei parti:
- ce e inainte de primul 0 si e format numai din 1 sau nu este deloc
- primul 0
- ce e dupa primul 0 si e format numai din 1 sau nu este deloc
sau dintr-o parte
- un sir de 1
S -> X | Y | Z - cele trei variante
X -> U0U0U
Y -> U0U
Z -> U
U ->U1
U ->1
Simtiti cum functioneaza ?
Sfarsit pentru azi.
Niciun comentariu:
Trimiteți un comentariu