API 2023 02 10

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 10 febbraio 2023 Informatica teorica Esercizio 1 (8 punti) Si consideri il linguaggio L = {0n | n ∈ N e 0n appare nell’espansione decimale di π}. Il linguaggio L ` e regolare? Si motivi esaurientemente la risposta. Soluzione Si danno solamente due casi: 1. esiste una sequenza “massima” 0 k che appare nell’espansione decimale di π tale per cui la sequenza 0m, con m > k , non appare nell’espansione decimale di π; 2. qualunque sequenza di 0, di qualunque lunghezza, appare nell’espansione decimale di π. In entrambi i casi il linguaggio ` e regolare, in quanto esprimibile mediante un’espressione regolare. Nel primo caso, l’espressione regolare ` eε|0|00| . . . |0k; nel secondo, 0 ∗. Esercizio 2 (8 punti). Dato un linguaggio L definito su un alfabeto I, si consideri l’ipotetica macchina di Turing ML a k nastri, che ignora la stringa in input e stampa sul nastro di output la sequenza l0 ⋄ l1 ⋄ l2 ⋄ . . ., dove li ∈ L, i ∈ N e ⋄ ` e un simbolo non presente inI. Le parole di L compaiono una ed una sola volta nell’output di ML, in un ordine non noto a priori. 1. Si dimostri che, se ML esiste, allora L ` e semidecidibile. 2. Si consideri il caso in cui ML esiste e le parole li ∈ L compaiono in ordine lessicografico nel nastro di output di ML. Si indichi se L ` e decidibile, semidecidibile o indecidibile e lo si dimostri. Chi ha diritto alla riduzione del 30% della prova, svolga unicamente il primo dei due punti. Soluzione 1. L’esistenza di ML consente di ricavare direttamente un semi-algoritmo (ovvero una procedura algoritmica di decisione che termina unicamente nel caso in cui la risposta sia 1) che calcola la funzione caratteristica di L (ovvero la funzione che vale 1 se x ∈ L, 0 altrimenti), cL(x), se x appartiene…