API 2020 09 07

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al T ema d’esame 07 Settembre 2020 1 Informatica teorica Esercizio 1 Siano A ={0, 1, 2} e B ={0, 1}. Si considerino i linguaggi L1 ={x1xR| x∈ A+} e L2 = B+212B+. 1. Si dica quali sono i modelli a potenza minima per L1 ed L2, motivando adeguatamente la risposta. 2. Si descriva il funzionamento di un automa (o si definisca una grammatica) a potenza minima per l’intersezione tra L1 e L2. Soluzione 1. Rispettivamente automa a pila non deterministico e automa a stati finiti. 2. Solito automa a pila deterministico che impila i caratteri in B, fino ad arrivare al primo 2; dopo il secondo 2 spila controllando la corrispondenza col carattere letto. Esercizio 2 Si dica, motivando opportunamente la risposta, se i problemi seguenti sono decidibili: 1. Stabilire se, dato un generico automa a stati finiti, esso riconosce tutte le stringhe in A∗, con A ={0, 1}; 2. Stabilire se, dato un generico automa a stati finiti, esso riconosce tutte e sole le stringhe che codificano numeri primi espressi in notazione binaria, con A ={0, 1}. Come cambierebbe la risposta ai quesiti precedenti se fosse data una macchina di Turing al posto di un automa a stati finiti? Soluzione 1. Decidibile poich´ e ` e decidibile l’equivalenza tra FSA, quindi basta disegnarne uno che accetti tutto A∗. 2. Decidibile poich´ e la risposta ` e sempre no (nessun FSA ` e in grado di riconoscere il linguaggio dato). Le varianti con TM sono tutte indecidibili per il teorema di Rice. 1/3 2 Algoritmi e strutture dati Esercizio 1 Si considerino i formalismi delle Macchine di Turing deterministiche a 1 nastro di memoria (MT-1) e degli Automi a 2 Pile deterministici (A2P). Un A2P ` e un automa a pila deterministico che ha a disposizione una pila aggiuntiva. Mostrare come una MT-1 pu` o…