API 2018 01 17

Page 1

Algoritmi e Principi dell’Informatica Appello del 17 gennaio 2018 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 e 5 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (8 punti) Si consideri il linguaggio L costruito su un alfabeto che comprende, tra gli altri, anche i simboli i, f, e u, e fatto di tutte e sole le parole in cui ogni simbolo f è preceduto da almeno un simbolo i, e tra un simbolo i ed il successivo f c'è esattamente un simbolo u (oltre potenzialmente ad altri simboli, ovviamente diversi da f). Inoltre, ogni parola del linguaggio L deve terminare con un simbolo f. 1. Dire qual è il formalismo (o quali sono i formalismi, se più di uno) a potere espressivo minimo tra quelli visti a lezione (automi, grammatiche, logiche) che è in grado di esprimere il linguaggio L. 2. Formalizzare il linguaggio L nel formalismo (o in uno solo dei formalismi, se più di uno) individuato al punto 1. Esercizio 2 (8 punti) 1. Dire se è decidibile il problema di stabilire se, data una generica grammatica regolare G, esiste una sequenza di produzioni che portano ad una parola fatta solo di simboli terminali. Dire se il problema è semidecidibile. 2. Dire se è decidibile il problema di stabilire se, data una generica grammatica non ristretta G, esiste una sequenza di produzioni che portano ad una parola fatta solo di simboli terminali. Dire se il problema è semidecidibile. Esercizio 3 (6 punti) Sia A = {a, b, c} un alfabeto; si considerino gli omomorfismi h', h''…