Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
