1. Scrieți o funcție care fiind dat un neterminal produce
lista tuturor șirurilor de simboluri în care se poate
transforma neterminalul după ce se aplică n
producții (oricare, în orice ordine).
Scrieți mai întâi o funcție care ia un șir de simboluri și returnează lista șirurilor în care se poate transforma, aplicând o singură regulă.
2. Scrieți o funcție care calculează mulțimea tuturor simbolurilor terminale cu care poate începe fiecare neterminal. Porniți de la mulțimea vidă pentru fiecare simbol, și actualizați, parcurgând fiecare producție, până ajungeți la un punct fix (nu mai obțineți nicio modificare).
3. O expresie se poate scrie în formă postfix, de exemplu 3 2 + 5 - (adică (3 + 2) - 5) sau 3 2 5 + -, adică 3 - (2 + 5), după gramatica:
Expr ::= numar Rest Rest ::= ε | Expr op RestScrieți o funcție care citește de la intrare o expresie în formă postfix cu operanzi întregi și returnează valoarea ei.
4. Un tip de gramatici sunt L-sistemele, cu care se pot descrie fractali. Alegeți unul din exemplele date și scrieți un program care dezvoltă de n ori simbolul inițial pentru a desena fractalul (vezi și exemplele de la primul curs).