Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 linguaggio L'' = {wwRw : w ∈ a+b*} sono della forma ai bj bj ai ai bj, ovvero: ai b2ja2i bj. In questo caso, il linguaggio richiede una MT. Esercizio 2 Riduzione di HALT a P 1. Se My non è completa, costruisco M'y completa in cui ogni run o termina in accettazione o va in loop. Altrimenti, M'y = My 2. Costruisco una M''y in cui ogni stato q di M'y è raddoppiato in e e definisco la funzione di transizione di stato di M''y in questo modo: q -[…]→ q' in M'y allora • -[…]→ . Inoltre, se q è di accettazione in M'y allora è di accettazione. Da , mediante opportune transizioni (che coprono tutte le combinazioni di simboli possibili ottenibili sui nastri), M''y va in uno stato di accettazione (creato apposta per gestire i run accettanti di lunghezza dispari di M'y che in M''y hanno dunque lunghezza pari). Lo stato iniziale di M''y è . Quindi, dato input generico x, M''y o va in loop oppure accetta con un run di lunghezza pari. Risolvere P su M''y equivale a stabilire se My termina su x.