API 2021 06 14

Page 1

Algoritmi e Principi dell’Informatica T ema d’esame del 14 Giugno 2021 1 Informatica teorica Esercizio 1 (8 punti + bonus) Si consideri il linguaggio L1 =¬L2, dove L2 = (ab)+. a) Si definisca L1 nella logica MFO, se possibile, altrimenti se ne motivi l’impossibilit` a. b) Bonus. Con riferimento alle propriet` a dei linguaggistar-free, si chiarisca se ` e possibile fornire un’espressione insiemistica per L1 facendo uso del simbolo dell’insieme vuoto (∅), degli insiemi di una singola lettera ({a} e{b}), degli operatori di unione (∪), intersezione (∩), complemento (¬) e concatenamento (·), senza usare gli operatori di Kleene ( ∗ e +). Suggerimento: si noti che ¬∅ ={a, b}∗. Soluzione a) Si pu` o definire L1 in MFO mediante la formula seguente: ¬( ∃x(x = 0∧ a(x)) ∧ ∀x(a(x)→∃ y(succ(x, y)∧ b(y))) ∧ ∀x((b(x)∧¬ last(x))→∃ y(succ(x, y)∧ a(y))) ∧ ∃x(last(x)∧ b(x)) ) b) Un’espressione per L1 che non usi gli operatori di Kleene ` e la seguente: (¬∅·{ a}·{ a}·¬∅ ) (parole che hanno due a consecutive) ∪ (¬∅·{ b}·{ b}·¬∅ ) (che hanno due b consecutive) ∪ ¬({a}·¬∅ ) (parole che non iniziano con a) ∪ ¬(¬∅·{ b}) (parole che non finiscono con b) 1/3 Esercizio 2 (8 punti, solo a) e b) per studenti con riduzione della prova) Nel corso di Prova finale di API si richiede di sviluppare in C una funzione f da N a N. Un generatore di test, fornito agli studenti, enumera gli input per f e i corrispondenti output attesi. a) `E decidibile il problema di stabilire se la codifica di f fatta da un generico studente ` e corretta rispetto ad ogni possibile caso di test fornito dal generatore? b) Ada e Pasquale si sono consultati prima di scrivere le proprie implementazioni. `E decidibile il problema di stabilire se le loro codifiche di f sono equivalenti? c) `E semidecidibile il problema del punto a)? †…