Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 funzioni ausiliari. Soluzione Esercizio 1 a) Ricadiamo chiaramente nelle ipotesi di applicazione del teorema di Rice: l’insieme di funzioni considerate non è né l’insieme vuoto (c’è almeno una macchina di Turing che accetta almeno una stringa), né l’insieme di tutte le funzioni computabili (non tutte le macchine di Turing accettano almeno una stringa), pertanto l’insieme S non è ricorsivo. b) Per stabilire che S è ricorsivamente enumerabile si può, ad esempio, mostrare che S è l’insieme di definizione di una funzione f (parziale e) computabile. Tale funzione f è implementata da una macchina di Turing che procede come segue. Per un dato indice i, simula il comportamento di della i-esima macchina di Turing Mi; partendo da n=0 e m=1, verifica, per ogni stringa x di lunghezza n, se in m passi Mi accetta x, e procede enumerando (n,m) con la solita tecnica diagonale (0,1), (1,1), (0,2), (2,1), (1,2), (0,3), … fino a che non trova una stringa accettata da Mi, se esiste. Si noti che, fissato n, è sempre possibile enumerare tutte le stringhe di lunghezza n in tempo finito. Pertanto, se esiste una stringa di lunghezza n’ accettata da Mi in un numero di passi m’, questa viene prima o poi enumerata con il procedimento sopra illustrato; se non esiste, tale procedimento non termina. c) Il complemento di S non può essere ricorsivamente enumerabile. Se lo fosse, sia S sia il suo complemento sarebbero ricorsivamente enumerabili (vedi punto precedente), pertanto si potrebbe concludere che S è ricorsivo, ma al punto a) abbiamo mostrato che non lo è. d) L’insieme S1 è esplicitamente definito come il complemento ℕ- S di S, cioè l’insieme degli indici che non stanno in S. L’insieme S2 è definito come l’insieme degli indici che godono della proprietà opposta (l’opposto di accettare almeno una stringa è non accettare alcuna stringa) di quella goduta dagli indici che stanno in S, e quindi è ancora una volta il complemento di S. L’insieme S3 invece non è il complemento di S, infatti una stessa macchina di Turing può accettare una stringa (e quindi avere l’indice in S) e non accettarne un’altra (e quindi avere l’indice anche in S3). Esercizio 2 (8 punti) L(G) è chiaramente il linguaggio {aa.ancbnbc | n ≥ 0}. Il predicato ℓ(x), che indica l’appartenenza di x a L(G), può essere quindi espresso dalla formula seguente: ∀x( ℓ(x) ↔ ((x = aacbc) ∨ ∃ y, z, w (y = aazcwbc ∧ ℓ(y) ∧ x = aaazcwbbc))))