API 2018 01 31

Pagina 1

Algoritmi e Principi dell’Informatica Appello del 31 gennaio 2018 Esercizio 1 (7 punti) Sia L il linguaggio generato dalla seguente 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 C0 (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, C0 sui compiti dei propri studenti. Il Prof. Halting aveva però già implementato un programma, chiamato H0 (sempre scritto in un linguaggio Turing-completo), con la stessa finalità e si chiede se i due programmi (C0 e H0) 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 C0 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 C0. 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 C0? ☐ Decidibile ☐ Non decidibile Perché? c) Dopo mesi di alacre lavoro, il Dr.…