Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 2 3 febbraio 2018 Esercizio 1 ( 8 punti) Sia L il linguaggio costituito da tutte e sole le stringhe costruite sull’alfabeto { a , b } con almeno due simboli ‘ a ’. Si specifichi in logica del prim’ordine il predicato unario ℓ , che indica che il suo argomento è una stringa appartenente a L . Oltre ai connettivi logici, quantificatori e punteggiatura consentiti nella logica del prim’ordine, nella specifica si può fare u so esclusivamente dei seguenti simboli : • la funzione di concatenazione tra stringhe (da indicarsi con il consueto simbolo ‘ • ’ e notazione infissa); • le costanti a e b , che denotano le corrispondenti stringhe di un carattere ; • la costante ε , che denota l a stringa vuota ; • il predicato binari o = di uguaglianza . Nome: Matricola: Firma: Esercizio 2 ( 8 punti) Un automa (macchina) si dice p ari se accetta solo stringhe di lunghezza pari. Per ciascuno dei seguenti problemi, dire se sono decidibili o meno, motivando la risposta. 1. Stabilire se un generico automa a stati finiti è pari. ☐ Decidi bile ☐ Non decidi bile Motivo: 2. Stabilire se un a generic a macchina di Turing è pari. ☐ Decidibile ☐ Non decidibile Motivo: Soluzione 1 " x ( ℓ ( x ) « $ y $ z $ w ( x = y • a • z • a • w Ù p ( y ) Ù p ( z ) Ù p ( w ) )) " x ( p ( x ) « x = ε Ú $ y ( p ( y ) Ù ( ( x = y • a ) Ú ( x = y • b ) ) ) ) Soluzione 2 Il punto 1 è decidibile. Si consideri infatti un automa a stati finiti D che riconosce tutte e sole le stringhe di lunghezza dispari (sull’alfabeto di riferimento). Dato un generico automa a stati finiti A, è sempre possibile costruire un altro automa a st ati finiti B che riconosce il linguaggio L(B) = L(D) Ç L(A), grazie alla proprietà di chiusura dei linguaggi regolari rispetto all’intersezione. Ora, l’automa A è pari se e solo se L(B) è vuoto, e la vuotezza di un linguaggio regolare è un problema notoria mente decidibile. Il punto 2 è in decidibile per il teorema di Rice. La “parità” di una macchina di Turing è certamente una proprietà della funzione da essa calcolata, in quanto non esiste una funzione calcolata da una macchina di Turing pari che sia anche calcolata da una macchina di Turing non pari. Basta quindi constatare che l’insieme di funzioni calcolate da macchine di Turing pari non è né vuoto né l’insieme di tutte le funzioni computabili per concludere che l’insieme degli indici di macchine di Turin g pari non è ricorsivo .