API 2017 02 09 Recupero

Page 1

Algoritmi e Principi dell’Informatica 9 febbraio 2017 Esercizio 1 (8 punti) Si considerino i due seguenti problemi: P1 = determinare se una generica macchina di Turing accetta al più 100 stringhe diverse. P2 = determinare se una generica macchina di Turing accetta più di 100 stringhe diverse. Rispondere, fornendo opportune motivazioni, ai seguenti quesiti: • P1 è decidibile? • P2 è decidibile? • P1 è semidecidibile? • P2 è semidecidibile? Nome: Matricola: Firma: Esercizio 2 (8 punti) Definire in logica del prim’ordine un predicato binario prefisso che è vero se e solo se entrambi i suoi argomenti sono stringhe costruite sull’alfabeto A={a,b} e il primo argomento è un prefisso proprio del secondo. Ad esempio: • prefisso(a,b) è falso; • prefisso(ab,aba) è vero; • prefisso(ab,ab) è falso (ab non è un prefisso proprio di ab); • prefisso(a,ac) è falso (le stringhe non sono entrambe costruite sull’alfabeto A). Oltre ai soliti connettivi, quantificatori, variabili e punteggiatura, si può fare uso esclusivamente dei seguenti simboli: • le costanti a e b, che indicano i caratteri alfabetici; • la costante ε, che indica la stringa vuota; • il predicato = di uguaglianza tra stringhe; • la funzione unaria testa, che restituisce il primo carattere del suo argomento ed è definita solo per stringhe non vuote o ad esempio, testa(abb) = a, mentre testa(ε) = ⊥ • la funzione unaria coda, che restituisce la stringa composta da tutti i caratteri del suo argomento tranne il primo ed è definita solo per stringhe non vuote o ad esempio, coda (abb) = bb, mentre coda (ε) = ⊥ Soluzioni che usino altri simboli e convenzioni non saranno prese in considerazione. Si possono naturalmente definire altri predicati di comodo, purché rispettino le convenzioni suindicate. Soluzione Esercizio 1 (8 punti)…