08 09 2011

Page 1

Algoritmi e Principi dell'Informatica Parte I Modelli e computabilità Appello dell'8 settembre 2011 Esercizio 1 (12 punti) Si consideri il linguaggio L fatto di tutte e sole le stringhe x {a, b}* in cui ogni prefisso y di x è tale che #b(y) #a(y), laddove con #a(y) e #b(y) si indica, rispettivamente, il numero di a e di b nella stringa y. 1. Si scriva una grammatica che generi L. La grammatica scritta è a potenza minima tra quelle che generano L? Se no, quale è la classe di grammatiche a potenza minima tra quelle che generano L? 2. Si scriva una rete di Petri che riconosca L. La RdP scritta è a potenza minima tra quelle che riconoscono L? Esercizio 2 (10 punti) Si consideri la funzione (parziale) car x : {s, e, b} che descriv e i caratteri di una stringa x. Più precisamente, carx(i) restituisce il carattere in posizione i -esima della stringa x (ed è indefinito se x non ha carattere in posizione i-esima). Si consideri la seguente specifica logica di un linguaggio L (le stringhe del linguaggio L, cioè , sono tutte e sole quelle che soddisfano le condizioni scritte sotto): n ( n > 0 j (j n carx(j) = ) j (0 j < n carx(j) ) carx(0) e j ( carx(j) = e carx(j+1) = e carx(j-1) e carx(j+2) e carx(j-1) = s )) 1. Descrivere a parole come è fatto L, e dare almeno 2 esempi di s tringhe che appartengono ad L e almeno 2 esempi di stringhe che non appartengono ad L. Gli esempi devono essere tutti significativi, nel senso che devono soddisfare o violare la specifica in modi diversi. 2. Scrivere un automa che riconosce L. L'automa deve essere a potenza minima tra quelli che riconoscono L. Esercizio 3 (11 punti) Il datalog è un linguaggio di interrogazione per basi di dati. Data una query datalog Q, si indica con Q(D) l'insieme di risposte a Q ottenute sul database D. Si parta dalle…