Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 , 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 si provano tutte le (finite) stringhe di lunghezza n. In questo modo, è possibile testare tutte le stringhe in ingresso con un qualunque numero di passi su entrambe le macchine, e se esiste una stringa accettata da entrambe, prima o poi lo si scoprirà.