Fondamenti di Informatica, 20 Settembre 2011

Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.
  • Occorre essersi prenotati sul portale studenti del nostro ateneo. Se cio' non e' stato fatto, comunicatelo immediatamente al docente o all'assistente in aula.
  • 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.
    Fornire inoltre l'automa a stati finiti che riconosca lo stesso linguaggio, ma produca un output {0,1} ad ogni passaggio di stato, in modo tale che nella transizione finale venga prodotto un '1' se e solo se la stringa accettata contiene un numero dispari di 'a' (non e' rilevante l'output prodotto nelle altre transizioni).
    (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.