07 07 2014

Pagina 1

Algoritmi e Prin Informatica Appello del 7 Luglio 2014 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1a, 1b 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 singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1a (punti 5) Si consideri il linguaggio Lk, dove k è un parametro, tali che ogni volta che si trovino k a consecutive ne segua immediatamente almeno una b. Si costruisca una rete di Petri che accetti L 3. NB: è preferible che la rete non contenga transizioni che siano sia in ingresso che in uscita al medesimo posto. Esercizio 1b (punti 5) un generico lingu aggio L k per un dato valore del parametro k (la formula deve quindi dipendere da k, variabile libera) 1.a usando variabili intere che indichino la posizione di un caratter e nella stringa e i predicati a(i) e b(i) per indicare che il carattere in posizione i-esima è a o b, rispettivamente. Ad esempio la formula a(1) b(2) indica che la stringa deve inziare con ab. NB: qualora fosse utile si può fare uso del predicato (indefinit carattere in posizione i: per convenzione si può assumere che valga (0) e che per una stringa lunga n valga (a(n) b(n)) (n+1). Esercizio 2 (punti 7) Una macchina di Turing Mi (che calcola la funzione fi) è detta riproducibile se esiste un'altra macchina di Turing Mj (che calcola la funzione fj) tale per cui fi=fj. alfabeto di due caratteri {0, 1}. Al suo interno siano: elle funzioni calcolate da macchine di Turing riproducibili. G l'insieme delle funzioni calcolate da macchine di Turing riproducibili e con meno di 10 stati. H l'insieme delle funzioni calcolate da macchine di Turing…