Fondamenti di Informatica, 4 Luglio 2018

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, q0, F, δ >
    con Γ = {a, b, c} Q = {q0, q1, qF} F = {qF} e la funzione δ così definita 
                a              b              c               blank

q0     q1 | a |D      q0 | b | D     q0 | c | D      qF | blank |I

q1     q0 | 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:
    (b) Sia {{M0,A0,I0, F0}, {persona1, conoscente2, cittadino2} } 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 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)