Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
