Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
