Logică și structuri discrete - Exerciții cu gramatici

1. Arbori de derivare. Pentru gramatica de șiruri de paranteze echilibrate de la curs, desenați arbori de derivare pentru toate șirurile de lungime 6 (trei perechi de paranteze).
Puteți găsi o relație de recurență pentru numărul șirurilor cu n perechi de paranteze ?

2. Scrierea de gramatici Definiți o gramatică care descrie valori de tip listă în ML (scrise cu paranteze drepte și punct-virgulă). Folosiți un terminal elt pentru elementele listei.
Definiți apoi o gramatică care permite și folosirea lui :: pentru a compune valori de tip listă.

3. Gramatici pentru expresii Simplificați gramatica pentru expresii aritmetice de la curs, considerând doar adunarea și înmulțirea, și fără paranteze (cazul general e o sumă de produse).
Încercați să scrieți un program care citește o astfel de expresie de la intrare și îi returnează valoarea.

4. Prioritatea operatorilor În C, operatorii relaționali <, <=, >, >= au precedență mai mare decât operatori de comparație == și !=. Toți acești operatori sunt asociativi la stânga.
Scrieți o gramatică neambiguă pentru expresiile formate pornind de la numere ca terminali și folosind doar operatorii amintiți (fără paranteze). Gramatica poate fi și recursivă la stânga.
E adevărat că 3 == 3 == 3 > 2 > 1 == 1 ?

5. Fractali și L-sisteme. Un tip de gramatici sunt L-sistemele, cu care se pot descrie fractali. Studiați unul din exemplele date pentru a înțelege acest mod de descriere.


Marius Minea
Last modified: Sat Dec 9 12:15:00 EET 2017