18 11 2011

Pagina 1

Algoritmi e Principi dell'Informatica Prima Prova in Itinere 18 Novembre 2011 Esercizio 1 (punti 7/12) Si considerino le seguenti definizioni: 1. Una grammatica si dice lineare a destra se le sue produzioni sono del tipo A ----> Bx, x VT*, oppure, A ----> x, x VT*. 2. Una grammatica si dice lineare a sinistra se le sue produzioni sono del tipo A ----> xB, x VT*, oppure, A ----> x, x VT*. 3. Una grammatica si dice lineare a destra o a sinistra se le sue produzioni sono del tipo A ----> Bx, x VT*, oppure, A ----> xB, x VT*, oppure, A ----> x, x VT*. 4. Una grammatica si dice lineare se le sue produzioni sono del tipo A ----> yBx con y, x VT*, oppure, A ----> x, x VT*. Si confrontino tra loro le potenze generative (le famiglie di lingu aggi generati) delle suddette classi di grammatiche tra loro e con quelle dei seguenti formalismi: a. Automi a stati finiti b. Automi a pila deterministici c. Automi a pila nondeterministici d. Reti di Petri (senza archi inibitori) Nota. Ogni relazione tr a le diverse potenze generative deve essere accompagnata da una breve giustificazione; non è necessario che essa sia una rigorosa dimostrazio ne matematica ma deve essere su fficientemente chiara e convincente. Esercizio 2 (punti 6/12) Nel "problema delle 8 regine" si vogliono posizionare 8 regine su una scacchiera 8 8 (inizialmente vuota) in modo che nessuna regina "attacchi" (ossia si trovi sulla stessa riga, colonna o diagonale di) un'altra regina. Formalizzare tramite logica del prim'ordine una formula ch e specifichi tutti i requisiti del problema (e quindi sia vera se e solo se i pezzi sulla scacchiera corrispondono a una soluzione). Suggerimento: si consiglia di adottare un predicato relativo al posizionamento di una regina sulla scacchiera, ad esempio il predicato ternario p(N, X,…