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 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,…
First page of the document.
