API 2022 07 12

Pagina 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 12 luglio 2022 Informatica teorica - Tempo a disposizione: 1 ora Esercizio 1 (8 punti) Si costruisca una grammatica o automa o formula logica a potenza minima per il seguente linguaggio: {a2nΣ+b3n | n > 0} ∪ {Σ+b3n | n > 0}, con Σ = {a, b}. Soluzione Il linguaggio ` e aperiodico (o “star-free”), in quanto {a2nΣ+b3n | n > 0} ⊂ { Σ+b3n | n > 0} = Σ+.b3. Si pu` o dunque esprimere con la seguente formula MFO: ∃y(y > 0 ∧ b(y) ∧ b(y + 1) ∧ b(y + 2) ∧ last(y + 2)). Esercizio 2 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga solo il punto 3. 1. Dire se ` e decidibile il problema di stabilire se due programmi, uno scritto in C e uno scritto in Java, calcolano la stessa funzione. 2. Dire se ` e decidibile il problema di stabilire se due programmi, entrambi scritti in C, sono identici, salvo per il fatto che i nomi delle variabili usate sono diversi tra un programma e l’altro. 3. Dire se ` e decidibile il problema di stabilire se, dato un programma C che fa uso di puntatori, esiste un’esecuzione in cui, ad un certo punto, due variabili puntano entrambe allo stesso indirizzo (fenomeno dell’aliasing). Soluzione 1. L’equivalenza di programmi C e Java ` e indecidibile, si pu` o vedere riducendo il problema dell’equivalenza tra due programmi C a quella tra un programma C e un programma Java: ogni programma C pu` o essere trasformato in un equivalente programma Java, e se fosse decidibile l’equivalenza tra programma Java e programma C, allora potremmo anche decidere l’equivalenza tra programmi C, che non ` e possibile. 1/4 2. Il problema ` e decidibile, in quanto si tratta di leggere i 2 programmi parola per parola. Laddove si trovano dichiarazioni di variabili (che devono essere in corrispondenza una…