API 2016 07 14

Pagina 1

Appello del 14 luglio 2016 - Algoritmi e Principi dell’Informatica Esercizio 1 (8 punti) Progettare un automa a potenza minima che accetti il linguaggio seguente L = { wi c wi+1R | wi, wi+1∈{0, 1}* e, per ogni k, wk è la codifica binaria dell’intero k>0, senza zeri iniziali } Per esempio, 1011c0011∈L, poiché 1011 è la codifica binaria di 11 (undici in base dieci) e 1100 è la codifica binaria del numero 12 (dodici). Fornire una giustificazione adeguata della scelta del tipo di automa, cioè del fatto che non esista un automa di potenza inferiore che riconosca il linguaggio. Qual è il tipo di automa a potenza minima che accetta la seguente variante, L1, del linguaggio? L1 = { wi c wi+1 | wi, wi+1∈{0, 1}* e, per ogni k, wk è la codifica binaria dell’intero k>0, senza zeri iniziali} Fornire una giustificazione informale della propria risposta. Esercizio 2 (8 punti) Indicare, giustificando opportunamente la risposta, quali dei problemi seguenti sono decidibili: 1. Stabilire se una generica MT si arresta immediatamente (compiendo 0 mosse) per ogni ingresso. 2. Stabilire se una generica MT si arresta entro 1 mossa per ogni ingresso. 3. Stabilire se una generica MT si arresta per ogni ingresso. Dire inoltre quali dei problemi elencati sono semidecidibili. Soluzione Esercizio 1 Il DPDA in figura accetta il linguaggio. Nessun FSA può accettare il linguaggio, poiché è necessaria una quantità illimitata di memoria. Notare quanto segue: Il successore di 1011 è 1100, quindi 1011c0011 è accettato; Il successore di 11 è 100, quindi 11c001 è accettato; Il successore di 011 è 100, ma 011c001 non è accettato a causa degli zeri iniziali. Il linguaggio L1 può essere solo accettato da una TM, poiché un PDA non può usare la sua memoria per confrontare I bit corrispondenti nelle due stringhe…