API 2021 01 27

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al T ema d’esame 27 Gennaio 2021 1 Informatica teorica Esercizio 1 Si considerino i seguenti linguaggi sull’alfabeto A ={a, b, c}: L1 = A∗·{ b}− (A∗· (A−{ a})· A∗·{ b}) (1) L2 = A∗− (A∗· (A−{ b})· A∗) (2) L3 = L1· L2 (3) dove∗ ` e la stella di Kleene,− ` e la differenza insiemistica e· ` e la concatenazione. Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggio L3. Soluzione Si pu` o facilmente verificare che L1 = a∗· b e L2 = b∗. Pertanto L3 = a∗· b+. `E quindi un linguaggio regolare (caratterizzato, per l’appunto, dall’espressione regolare data). Tuttavia si tratta anche di un linguaggio di tipo star-free, poich´ e, come si vede dalle espressioni originali, la stella di Kleene ` e applicata solo sull’intero alfabeto A. Si pu` o quindi formalizzare il linguaggio L3 mediante una formula MFO, come segue: ∃x(x = 0∧ (a(x)∨ b(x))) all’inizio c’` e una a o una b ∧ ∀x(a(x)→∃ y(y = x + 1∧ (a(y)∨ b(y)))) dopo una a c’` e unaa o una b ∧ ∀x(b(x)→ (last(x)∨∃ y(y = x + 1∧ b(y)))) dopo una b c’` e unab o ` e l’ultimo carattere ∧ ∃x(b(x)∧ last(x)) l’ultimo carattere ` e una b (congiunto ridondante) Esercizio 2 1. Dire se ` e decidibile il problema di stabilire se, data una MT deterministica e una sequenza di suoi stati, esiste una stringa x in ingresso tale che la MT attraversa esattamente, uno per uno, la sequenza di stati desiderata durante il riconoscimento di x. 2. Dire se ` e semidecidibile il problema del punto 1. 3. Dire se ` e decibile il problema di stabilire se, data una MT deterministica e una sequenza di suoi stati, esiste una stringa x in input tale che la MT, durante il riconoscimento x, attraversa gli stati desiderati nell’ordine desiderato, ma potrebbe, tra uno stato…