API 2017 04 26

Page 1

Algoritmi e Principi dell'Informatica Prima prova in itinere - 26 aprile 2017 Tempo a disposizione: 1h30 Esercizio 1 (11 punti) Si consideri il linguaggio L fatto di tutte e sole le stringhe sull’alfabeto { a,b} della forma bbwbb, dove w ∈ (ba)+ (cioè è tale che le a compaiono in tutte e sole le posizioni pari della sottostringa). 1. Si scriva una grammatica che genera il linguaggio L, e che faccia uso del minor numero possibile di simboli nonterminali. 2. La grammatica definita al punto 1 è a potere generativo minimo tra quelle che generano L? Se non lo è, scriverne una che genera L e ha potenza minima tra quelle che generano L. 3. Si scriva un automa che riconosce il linguaggio L’ fatto di tutte e sole le stringhe della forma bbwbbwbb, laddove w è definita come sopra. L’automa deve essere a potere riconoscitivo minimo tra quelli che riconoscono L’. Esercizio 2 (6 punti) 1. Dire se è decidibile il problema di stabilire se una generica macchina di Turing riconosce il linguaggio definito dalla seguente formula MFO F: ∃x (x = 1 ∧ a(x)) ∧ ∀x,y (y = x+1 ⇒ (x = 0 ⇒ b(x)) ∧ (b(x) ⇒ c(y))) 2. Dire se è computabile la seguente funzione: g(x) = 1 se la funzione fx calcolata dalla x-esima Macchina di Turing è tale che: fx(y) = 1 se la y-esima MT accetta il linguaggio definito da F, fx(y) = 0 altrimenti 0 altrimenti Soluzioni Esercizio 1 1. S → bbAbb A → baA | ba 2. La grammatica definita al punto 1 non è quella a potere espressivo minore, perché il linguaggio è riconoscibile da un FSA, quindi generabile da una grammatica regolare. La grammatica desiderata è la seguente: S → bA A → bB B → bC C → aB | aD D → bE E → b 3. Esercizio 2 1. Il problema non è decidibile. Si può riformulare il problema “la stringa w è accettata dalla MT M?” come “la MT M calcola una funzione f(xw) tale…