API 2023 01 10

Pagina 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 10 gennaio 2023 Informatica teorica Esercizio 1 (8 punti) Si considerino i linguaggi seguenti: • L1 = {anbncn | n > 0} • L2 = {b}∗.{a, b, c}+ Per ciascuno dei linguaggi indicati di seguito, utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che lo caratterizzi: 1. L = L1 \ L2, dove il simbolo \ indica la differenza insiemistica; 2. L′ = L1 ∪ L2. Chi ha diritto alla riduzione del 30% svolga unicamente il punto 1. Soluzione Il linguaggio sottraendo ( L2) contiene tutte le stringhe di almeno un carattere e quindi contie- ne anche tutte le stringhe del linguaggio minuendo ( L1), pertanto L ` e il linguaggio vuoto. Per caratterizzarlo, ` e sufficiente una formula MFO insoddisfacibile, come la seguenteφL: φL : ∃x(a(x) ∧ ¬a(x)). Per lo stesso motivo, abbiamo L′ = L2, che ` e chiaramente regolare, in quanto specificato dall’e- spressione regolare (b)∗.(a|b|c)+. Tuttavia ` e possibile caratterizzareL′ anche mediante una formula MFO, ad esempio con la formula φL′ seguente: φL′ : (a(0) ∨ b(0) ∨ c(0)) ∧ ∀x(a(x) ∨ b(x) ∨ c(x)). Esercizio 2 (8 punti). Si assuma che le macchine di Turing su alfabeto binario calcolino funzioni da Z a Z, interpretando le stringhe sul nastro come numeri in complemento a 2 codificati con il numero minimo di bit necessari. Si considerino i seguenti insiemi e si dica se essi sono ricorsivi, motivando la risposta: 1. S1 = {i | ∃x : fi(x) > 0} 2. S2 = {i | ∃x : fi(x) ≤ 0} 3. S3 = S1 ∪ S2 4. S4 = S1 ∩ S2 1/4 Soluzione Sono tutti non ricorsivi per il teorema di Rice, come spiegato in dettaglio nel seguito. 1. S1 contiene tutti e soli gli indici delle funzioni che hanno valore positivo per almeno un input. Questo insieme non ` e banale in quanto contiene, ad esempio,…