API 2018 02 23

Pagina 1

Algoritmi e Principi dell’Informatica Appello del 23 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 uso 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 la stringa vuota; • il predicato binario = di uguaglianza. Nome: Matricola: Firma: Esercizio 2 (8 punti) Un automa (macchina) si dice pari 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. ☐ Decidibile ☐ Non decidibile Motivo: 2. Stabilire se una generica 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 stati 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…