Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 prima e dopo il simbolo c. Soluzione Esercizio 2 Il problema 1 è decidibile: la MT si arresta in 0 mosse se e solo se lo stato iniziale è anche finale, il che si può verificare tramite banale ispezione del diagramma degli stati della macchina. (Si noti inoltre che il problema è indipendente dall’input.) Il problema 2 è decidibile: basta verificare che la MT si arresti entro una mossa per le sole stringhe di lunghezza minore o uguale a 1, cioè in un numero finito di casi: infatti, entro una mossa la MT può al massimo ispezionare un carattere della stringa di ingresso. Il problema 3 è indecidibile: si tratta infatti di verificare se la MT calcoli una funzione totale, il che è notoriamente indecidibile. Il problema 3 è anche notoriamente non semidecidibile, mentre i problemi 1 e 2 sono semidecidibili poiché sono anche decidibili.