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 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…
First page of the document.
