API 2022 08 31

Pagina 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 31 agosto 2022 Informatica teorica Esercizio 1 (7 punti) L = {anbmcod; n, m, o ∈ N, n ≥ 1, o ≥ 0, m = 2n + o}. Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggio L. Soluzione Il linguaggio ` e libero dal contesto, riconoscibile da un automa a pila deterministico. Riscrivere la definizione come L = {anb2nbocod; n, o ∈ N, n ≥ 1} rende evidente la natura del linguaggio. Per riconoscerlo ` e sufficiente impilare un simbolo per ogni a, spilarne uno ogni due b, fino a quando la pila ` e vuota. Per le b successive, impilare un simbolo per ogni b e spilare un simbolo per ogni c effettua il conteggio del valore o, al termine del quale ` e sufficiente riconoscere la presenza della singola d. q0 q1 q2 q3 q4 q5 aZ0/Z0A aA/AA bA/A bA/εbA/A bZ0/Z0B dZ0/Z0 bB/BB cB/ε cB/ε dZ0/Z0 Esercizio 2 (9 punti). Chi ha diritto alla riduzione del 30% della prova svolga unica- mente il punto 1. 1. `E possibile determinare se una generica macchina di Turing universale si arresta per ogni ingresso? 2. `E possibile trovare, data la terza (secondo l’enumerazione di G¨ odel) macchina di Turing universale M, almeno un ingresso per cui essa non si arresta? 3. `E possibile, data la macchina di Turing universale M di cui sopra, dire se essa si arresta per un generico ingresso n? Soluzione 1/5 1. S` ı: ` e possibile infatti stabilire che una qualunque MTU non si arresta per qualche input. Una MTU ` e in grado di emulare il comportamento di qualunque altra MT, il cui comportamento ` e codificato in parte del suo nastro di ingresso. Esiste quindi almeno un ingresso n che corrisponde a una MT che non si arresta per alcun input. Di conseguenza, non ` e vero che la MTU si arresta per ogni…