Fondamenti di Informatica, 22 Giugno 2016

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone. 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, comunicarlo immediatamente al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.
  • 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 e la definizione formale di linguaggio accettato da un automa.

    (b) Fornire la definizione formale di Grammatica di Chomsky. Definire formalmente le grammatiche di tipo 0,1,2 e 3.

    (c) Data una funzione di transizione δ di un automa a stati finiti, definire la funzione δ e dimostrare formalmente che, preso uno stato q e due stringhe x ed y,
    δ(q,xy) = δ(δ(q,x), y)
    Esercizio 2
    (a) Cosa significa, nel calcolo proposizionale (logica proposizionale), che una formula α e' conseguenza tautologica di un insieme di formule Γ ( Γ |= α) ?
    E' vera la seguente affermazione?
    p → (p → q) |= p → q
    dove p e q sono variabili proposizionali.


    (b) Fornire la definizione di Clausola di Horn. Da cosa e' composto un programma Prolog? Su quale proprieta' logica e' basato il funzionamento di Prolog?

    (c) Sappiamo di avere la funzione + tra le funzioni parziali ricorsive. Definiamo ora
    g(x) = μ{ y | +(y,x)=0 }
    e definiamo anche
    h(v,w) = g(+(v,w))
    Consideriamo ora la seguente funzione
    q(x) = μ{ y | h(y,x)=0 }
    Cosa calcola g, cosa calcola h?
    Qual e' il valore di q(0)?
    Qual e' il valore di q(2)?
    Come vengono calcolati?
    Esercizio 3
    Descrivere la forma dei giudizi (asserzioni) nella Semantica Operazionale Strutturata ed il loro significato. Fornire inoltre una delle regole della semantica operazionale strutturata del linguaggio WHILE, descrivendone il significato (regole senza descrizione del significato non verranno prese in considerazione)