Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 31 gennaio 201 8 Esercizio 1 ( 7 punti) Si a L il linguaggio generato dalla s eguente grammatica G : S - > T1T1T1T T - > 0T | 1T | ε Di che tipo è la grammatica G? A quale famiglia di linguaggi appartiene L? Si specifichi una grammatica G’ a potenza generativa minima che genera il linguaggio L’, complemento di L: Di che tipo è la grammatica G’? A quale famiglia di linguaggi appartiene L’? Nome: Matricola: Firma: Esercizio 2 (9 punti) Il Dr. Correction ha approntato un programma , chiamato C 0 (scritto in un linguaggio Turing - completo), che riceve in ingresso un compito di informatica teorica (opportunamente codificato come sequenza di bit) e restituisce in uscita il voto corrispondente. Il Dr. Correction ha testato, con soddisfazione, C 0 sui compiti dei propri studenti. Il Prof. Halting aveva però già implementato un prog ramma, chiamato H 0 (sempre scritto in un linguaggio Turing - completo ) , con la stessa finalità e si chiede se i due programmi ( C 0 e H 0 ) valutino tutti i compiti possibili esattamente allo stesso modo. Si supponga che i compiti possibili siano un’infinità numerabile. a) È decidibile il quesito del Prof. Halting ? ☐ Decidibile ☐ Non decidibile Perché? Il programma C 0 diventa molto popolare , ma il suo utilizzo è a pagamento. Per questo motivo, molti docenti si cimentano nell’implementazione di programmi per la correzione di compiti di informatica teorica (PCCIT) che si comportino esattamente come C 0 . Non essendo però certi dell’attendibilità della propria implementazione, si chiedono se ci sia un modo per verificarla. b) È decidibile il problema di stabilire se un generico PCCIT valuti tutti i compiti esattamente allo stesso modo di C 0 ? ☐ Decidibile ☐ Non decidibile Perché? c) Dopo mesi di alacre lavoro, il Dr. Correction riesce a dimostrare che C 0 restituisce sempre un voto a fronte di qualunque compito di informatica teorica. Alla luce di questo fatto, dire se cambierebbero (e come) le risposte pe r i punti a) e b) . Soluzione 1 G è una grammatica non contestuale (tipo 2). Il linguaggio L (l’insieme delle stringhe con al meno tre caratteri “1”) è però regolare (oltre ad essere non contestuale). Poiché la famiglia dei linguaggi regolari è chiusa rispetto alla complementazione, anche L’ (l’insieme delle stringhe con al più due caratteri “1”) sarà necessariamente regolare. È sufficiente allora che G’ sia una grammatica regolare come la seguente: S - > ε | 0S | 1T T - > ε | 0T | 1R R - > ε | 0 R Soluzione 2 Punto a: la domanda è chiusa, quindi il problema è decidibile. Punto b: stando al testo, un generico PCCIT è assimilabile a un generico programma/funzione implementato con una macchina di Turing. Pertanto, il problema è indecidibile per il teorema di Rice (l’insieme di indici di macchine di Turing che calcolano la specifica funzione calcolata da C 0 non è ricorsivo). Punto c: no n cambia nulla. La domanda chiusa (a) resta chiusa. L’insieme di indici di macchine di Turing che calcolano la specifica funzione calcolata da C 0 è comunque non ricorsivo per il teorema di Rice.