API 2017 09 15

Page 1

Algoritmi e Principi dell’Informatica Appello del 15 settembre 2017 Esercizio 1 (8 punti) a) Definire l’automa a potenza minima che riconosce il linguaggio L = {wb*wR : w ∈ a+b*} b) Analizzare i seguenti linguaggi e fornire una spiegazione esauriente riguardo alla classe di automi necessaria per il loro riconoscimento. L' = {wa+b*wR : w ∈ a+b*} L'' = {wwRw : w ∈ a+b*} Esercizio 2 (8 punti) Dato un input x ed una TM deterministica y, si definisce lunghezza finita dell’esecuzione di y mediante x il numero totale di transizioni (realizzate da y leggendo l’input x) che portano la macchina y dalla configurazione iniziale ad una configurazione di arresto (se la computazione non termina, la lunghezza finita non è definita). È decidibile stabilire se un generico input x induca in una generica TM y un’esecuzione di lunghezza finita pari? SOLUZIONI: Esercizio 1 a) Le parole del linguaggio L = {wb*wR : w ∈ a+b*} sono della forma ai bj b* bj ai con j≥0 e i>0 ovvero: ai b2j+h ai con h≥0. Pertanto, le parole del linguaggio sono della forma ai b* ai. E’ sufficiente quindi un PDA per riconoscere L. b) Le parole del linguaggio L' = {wa+b*wR : w ∈ a+b*} sono della forma ai bj a+b* bj ai con j≥0 e i>0. Il linguaggio L' è dunque definibile come L' = L1' ∪ L2' con: L1' = {ai a+b* ai : i>0} quando j=0 L1'' = {ai bj a+b* bj ai : i>0, j>0} Entrambi i linguaggi L1' e L1'', considerati singolarmente, sono riconoscibili da un PDA. Tuttavia la loro unione richiede un NPDA. Informalmente, le parole ai a+b* ai sono prefisso delle parole in L1''. Per questo motivo, l’automa non può distinguere il suffisso ai delle parole in L1', il cui riconoscimento richiede lo svuotamento della pila, dal termine a+ presente nelle parole di L1'', che invece non deve modificare il contenuto di pila. Le parole del…