Fondamenti di Informatica, 24 Giugno 2019 

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone (questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.

Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati. 

I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum. 

Esercizio 1 

(a) Fornire la definizione formale di Macchina di Turing deterministica. 

(b) Sia L il linguaggio di tutte le stringhe sull’alfabeto {a,b} che hanno il carattere “b” in penultima posizione. 

Scrivere un’espressione regolare che denota il linguaggio L;  Definire una grammatica che genera il linguaggio L;  Costruire un automa a stati finiti NON DETERMINISTICO che accetta il linguaggio L;  Costruire un automa a stati finiti DETERMINISTICO che accetta il linguaggio L.  

(c) Si consideri la seguente Macchina di Turing

M=< Γ, blank, Q, q₀, F, δ > 

con Γ = {a, b, c} Q = {q₀, q₁, q_F} F = {q_F} e la funzione δ così definita

            a              b              c               blank

q₀     q₁ | a |D      q₀ | b | D     q₀ | c | D      q_F | blank |I

q₁     q₀ | a |D

Dire se la stringa “aabcaa” e’ accettata o rifiutata da M. Giustificare la risposta.

Esercizio 2 

(a) Sia α una formula ben formata della logica dei predicati del prim'ordine (calcolo dei predicati) rispetto una data segnatura Σ e sia A_Σ una struttura.

Dare le definizioni di:

• α e' soddisfacibile in A_Σ 
• α e' vera in A_Σ 
• α e' soddisfacibile 

(b) Sia {{M⁰,A⁰,I⁰, F⁰}, {persona¹, conoscente², cittadino²} } una segnatura per la logica del primo ordine (calcolo dei predicati). Si consideri la struttura che ha come supporto l'insieme di tutte le persone e di tutti gli stati ed in cui si interpreta

• M come Mario 
• A come Antonio 
• I come l'Italia 
• F come la Francia 
• persona(x) come "x e' una persona"; 
• conoscente(x,y) come "x conosce y"; 
• cittadino(x,y) come "x e' cittadino di y". 

Scrivere la fbf il cui valore di verita' in tale struttura coincide con quello della seguente frase in italiano:

Mario e ad Antonio hanno alcuni conoscenti italiani in comune, ma entrambi conoscono dei francesi. 

(Si hanno a disposizione entrambi i quantificatori e tutti i connettivi logici) 

(c) Si consideri la segnatura del precedente esercizio.

Fornire delle strutture (non banali) nelle quali le seguenti formule risultino vere e strutture nelle quali risultino false. 

∀ x. ∀ y.conoscente(x,y)

∃ z. ∀ x. (persona(x) \/ cittadino(F,z)) 

Esercizio 3 

Il seguente λ-termine e' normalizzabile. Mostrare tutti i passi di β-riduzione che portano alla sua forma normale.

(λx.xxy)(λxy.xyy)