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 Appello del 3 luglio 2017 Esercizio 1 (7 punti) Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggio costituito da tutte e sole le stringhe binarie tali per cui il numero di 0 nella stringa sia divisibile per 5. Nome: Matricola: Firma: Esercizio 2 (9 punti) Si consideri il problema di stabilire se, date due generiche macchine di Turing M1 e M2, esista una stringa accettata da entrambe. Rispondere ai seguenti quesiti fornendo opportune motivazioni. a) Tale problema è decidibile? b) E’ semidecidibile? Soluzione esercizio 1 Espressione regolare: (1*01*01*01*01*01*)* Soluzione esercizio 2 a) Non è decidibile. Supponiamo per assurdo che esista un algoritmo A in grado di risolvere il problema, ossia che, dati due indici i e j, restituisca “vero” se le TM con indici i e j accettano una stringa in comune e “falso” altrimenti. Allora l’algoritmo A sarebbe anche in grado di risolvere il problema quando uno dei due indici è fissato, ad esempio quando j=100. Tuttavia, per il teorema di Rice, l’insieme degli indici delle TM che accettano una stringa in comune con la TM con indice 100 non è ricorsivo e pertanto non è decidibile stabilire se una generica TM accetti una stringa in comune con la TM con indice 100. Quindi non può esistere un algoritmo A in grado di risolvere il problema di partenza. b) Sì, è possibile infatti stabilire un principio enumerativo di tutte le coppie <m,n>, dove m indica il numero di passi in cui le TM vengono messe in esecuzione e n è la lunghezza della stringa da passare in ingresso alle TM; per ciascuna coppia <m,n> si provano tutte le (finite) stringhe di lunghezza n. In questo modo, è possibile testare tutte le stringhe in ingresso con un qualunque numero di…
First page of the document.
