API 2017 02 20

Page 1

Algoritmi e Principi dell’Informatica Appello del 20 febbraio 2017 Esercizio 1 (9 punti) Si consideri l’insieme S definito nel modo seguente: S = { i | i è l’indice di una macchina di Turing che accetta almeno una stringa } Per le domande seguenti, barrare la risposta corretta e motivare opportunamente. a) S è ricorsivo? ☐ Sì ☐ No Motivo: b) S è ricorsivamente enumerabile? ☐ Sì ☐ No Motivo: c) Il complemento di S è ricorsivamente enumerabile? ☐ Sì ☐ No Motivo: Si considerino ora gli insiemi seguenti: • S1 = { i | i è un numero naturale e non è l’indice di una macchina di Turing che accetta almeno una stringa } • S2 = { i | i è l’indice di una macchina di Turing che non accetta alcuna stringa } • S3 = { i | i è l’indice di una macchina di Turing in cui almeno una stringa non è accettata } Nome: Matricola: Firma: d.1) S1 rappresenta il complemento di S? ☐ Sì ☐ No Motivo: d.2) S2 rappresenta il complemento di S? ☐ Sì ☐ No Motivo: d.3) S3 rappresenta il complemento di S? ☐ Sì ☐ No Motivo: Esercizio 2 (8 punti) Si consideri la grammatica G seguente (con le usuali convenzioni alfabetiche): S → aaAbc A → aAb | c Si specifichi in logica del prim’ordine un predicato unario ℓ che indica che il suo argomento è una stringa del linguaggio generato da G. Oltre a connettivi logici, quantificatori, punteggiatura e variabili (si può sottintendere che assumano valori in {a,b,c}*), si può fare uso esclusivamente dei simboli seguenti: • le costanti a, b, c; • il simbolo di concatenazione tra stringhe ‘.’ (usato con notazione infissa; si può darne per scontata l’associatività, se ne può anche omettere la scrittura quando ciò non generi dubbi interpretativi: ad esempio, ab abbrevia a.b); • il simbolo di uguaglianza ‘=’. E’ possibile (ma non richiesto, né necessario) definire predicati e…