24 02 2014

Pagina 1

Algoritmi e principi dell’Informatica Recupero prima prova in itinere − 24 Febbraio 2014 Avvisi importanti La prova è riservata ai laureandi che non abbiano superato la prima prova in itinere La durata della prova di recupero è di 1 ora Esercizio 1 (punti 7/15-esimi) Si dica, giustificando brevemente le risposte, se le seguenti affermazioni sono vere o false: 1. Dato un qualsiasi automa a pila A, sia deterministico che nondeterministico, esiste sempre un automa a pila, sia deterministico che nondeterministico, che riconosce il complemento di L(A). 2. Dato un qualsiasi automa a pila A, sia deterministico che nondeterministico, esiste sempre una macchina di Turing, che riconosce il complemento di L(A). Esercizio 2 (punti 8/15-esimi) Si consideri l’alfabeto A = {a,b}. Per una stringa s costruita su A* chiamiamo massima sequenza ciascuna sottostringa non nulla t di s i cui caratteri siano tutti uguali e che non sia né seguita né preceduta da un ulteriore carattere uguale ai precedenti o ai seguenti. Ad esempio, nella stringa abbaaaa le massime sequenze sono a, bb, aaaa. 1) Si specifichi in logica del prim’ordine un predicato ternario same(s,c,n) che è vero se e solo se la stringa s è di n caratteri, tutti uguali al carattere c. (Nota: c è rappresentato come una stringa di un solo carattere.) 2) Si fornisca una specifica in logica del prim’ordine del predicato binario maxSeq(t,s) che è vero se è solo se t è una massima sequenza per s. Nella specifica, si faccia ricorso al predicato same definito al punto precedente. Nota bene: nella scrittura delle formule si può fare ricorso esclusivamente alle seguenti funzioni, predicati e costanti la cui definizione può essere data per scontata e quindi da non specificare ulteriormente: • s = t (predicato di uguaglianza: vero se e solo…