Computer Engineering - Algoritmi e Principi dell'Informatica

First partial exam

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 è defin ita 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 seguen te 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 che, se xw è l’indice della stringa w nell’enumerazione delle stringhe di I*, f(xw) = 1 se w è accettata, 0 altrimenti”. Nella fattispecie, il linguaggio definito da F è il linguaggio vuoto (in posizione 1 ci dovrebbero essere sia a che c, che è impossibile), quindi il problema dato coincide con il decidere se la MT calcola la funzione indefinita ovunque oppure no, che è indecidibile per il teorema di Rice (si chiede di decidere l’insieme delle funzioni contente la sola funzione indefinita ovunque, che ovviamente non è un insieme vuoto, né l’insieme di tutte le funzioni computabili). 2. In questo caso la funzione è banalmente computabile, perché corrisponde alla funzione costante uguale a 0, in quanto, per quanto detto al punto 1, nessuna funzione calcolabile fy ha le caratteristiche desiderate (detto in altro modo, g(x) è la funzione caratteristica di un insieme di funzioni che è vuoto, quindi di nuovo per il teorema di Rice è ca lcolabile).