Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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,…
First page of the document.
