API 2016 09 01

Page 1

Algoritmi e Principi dell’Informatica Appello del 1 Settembre 2016 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singoli eser cizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (9 punti) 1. Si costruisca un automa, preferibilmente a minima potenza riconoscitiva, che accetti il linguaggio L1 Ž {a,b}* costituito da tutte e sole le stringhe w tali che, se w contiene la sottostringa aa, allora la sua lunghezza è dispari. 2. Si determini la famiglia di automi a potenza riconoscitiva minima -o minimale- tale che un suo membro riconosca il linguaggio L2 Ž {a,b,c}*, costituito da tutte e sole le stringhe w tali che w includa la string a canc (per qualche n > 0) e, successiv amente, la string a ba2nb (la stringa w può contenere altre sottostringhe oltre alle suddette canc e ba2nb). a. Si costruisca un automa in tale famiglia che riconosca L2; b. Si costruisca una grammatica , preferibilmente a minima potenza generativa, che generi L2. Esercizio 2 (8 punti) Per entrambi i punti seguenti si assuma che L sia un linguaggio infinito costruito su un alfabeto A. 1. Sia L un linguaggio ricorsivo. Esiste necessariamente una enumerazione algoritmica E che enumera tutte le stringhe di L in ordine lessicografico? Motivare brevemente la risposta. 2. Sia E una enumerazione algoritmica E che enumera tutte le stringhe di un linguaggio L in ordine lessicografico. L è necessariamente ricorsivo? Motivare brevemente la risposta. Esercizio 3 (7 punti)…