10 09 2012

Page 1

Algoritmi e Principi dell’Informatica Appello del 10 Settembre 2012 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1, 2 e 3 in 1h e 45 min. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3,4 e 5 in 1h e 45 min. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 7/30-esimi) Si considerino le seguenti grammatiche e i linguaggi da esse generati; si indichi, per ognuna di esse, qual è il tipo di automa a potenza minima (all’interno delle “famiglie” tradizionali: a stati finiti, a pila deterministici, a pila nondeterministici, macchine di Turing) che riconosce il linguaggio. 1. S → a X b | b X a X → a X b | b X a | c 2. S → X | Y X → a Y b | ab Y → b X a | ba 3. S → a X b | b Y a X → a S b | ab Y → b S a | ba 4. S → X | Y X → a Y b | b Y a Y → b X a | a X b Esercizio 2 (punti 8/30-esimi) Dire se le seguenti funzioni sono calcolabili, motivando adeguatamente la risposta: 1) f(x,y) è indefinita, se la y-esima MT (sia essa a nastro singolo) termina e durante tutta la computazione con ingresso x non esce mai dalle celle utilizzate per memorizzare la stringa x e le due celle contenenti blank immediatamente prima e dopo x, altrimenti è pari a 0; 2) g(z) = 1 se la funzione calcolata dalla z-esima MT è diversa dalla f del punto 1, 0 altrimenti. Esercizio 3 (punti 3/30-esimi) Si descriva a grandi linee una MT che accetti il Linguaggio 3 dell’Esercizio 1 e se ne valuti la complessità temporale. La descrizione della macchina può essere anche informale ma sufficientemente precisa da permettere la valutazione della complessità…