Fondamenti di Informatica, 19 Dicembre 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 Automa a stati finiti deterministico e Automa a stati finiti non deterministico.
    (b)
    Fornire l'automa a stati finiti deterministico che riconosca il linguaggio (a*bb)+c.
    (c)
    Dimostrare che il complemento di un linguaggio regolare e' regolare.
    Esercizio 2
    (a)
    Discutere delle differenze tra programmazione imperativa (imperative programming) e funzionale (functional programming).
    (b)
    Definire informalmente la relazione di α-equivalenza tra lambda-termini. Fornire la stessa definizione in modo formale.
    (c)
    Enunciare il teorema di Church-Rosser e dimostrare la proprieta' di unicita' delle forme normali per il lambda-calcolo. Dedurre poi da quest'ultima la proprieta' di consistenza per la teoria della β-equivalenza.
    Esercizio 3
    Descrivere l'algoritmo che, dato un numero naturale n, fornisca la sua rappresentazione posizionale in base B. Dimostrarne la correttezza.