API 2019 04 17

Page 1

Algoritmi e Principi dell'Informatica Prima Prova in Itinere 17 Aprile 2019 Il tempo a disposizione è di 1h30’. Esercizio 1 (punti 5) Sia h l’omomorfismo (cioè una funzione tale che h(x.y) = h(x).h(y), per x, y stringhe) definito da: h(1) = 1, h(0) = e. Si scriva un automa o grammatica a potenza minima per il linguaggio: L1 = {w.h(w) | w Î {0, 1}+}. Esercizio 2 (punti 6) Si consideri il problema di stabilire se, date due generiche macchine di Turing M1 e M2, esista una stringa accettata da entrambe. a. Tale problema è decidibile? b. E’ semidecidibile? Si consideri il problema di stabilire se il linguaggio accettato da una MT è vuoto. c. Tale problema è decidibile? d. E’ semidecidibile? Motivare opportunamente le proprie risposte. Esercizio 3 (punti 6) a. Si consideri il linguaggio L1 dell’esercizio 1. È possibile esprimere L1 con una formula MFO (logica monadica del prim’ordine)? In caso positivo, si scriva la formula, in caso negativo si motivi la risposta. b. Come cambia la riposta al punto a) se considero il linguaggio L2 = h(L1) = {h(x) | x Î L1}? Tracce di Soluzioni Esercizio 1 Il linguaggio richiede un automa a pila non-deterministico, perché deve identificare la metà degli 1 presenti e, di lì in poi, non ammettere caratteri 0. Esercizio 2 a) Il problema 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…