Fondamenti di Informatica, 6 Luglio 2012

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)
    Descrivere il formalismo delle funzioni primitive ricorsive e delle funzioni parziali ricorsive.
    (b)
    Si supponga di aver definito la funzione primitiva ricorsiva f, di due argomenti, che calcola la somma.
    Si consideri quindi la seguente definizione della funzione primitiva ricorsiva g: 
     g(0,x) = C10(x)
 g(y+1,x) = q(y,g(y,x),x)
    dove q e' definita da 
     q(y,z,x) = f(P32(y,z,x),P33(y,z,x))
    Dire, giustificando la risposta, cosa calcola g.
    Si consideri inoltre la seguente definizione della funzione primitiva ricorsiva t: 
     t(0) = C01
 t(y+1) = u(y,t(y))
    dove u e' definita da 
     u(y,z) = g(S(P21(y,z)),P22(y,z))
    Dire, giustificando la risposta, cosa calcola t.
    Ricordiamo che la funzione di base Pkj e' definita da Pkj(n1,..,nk) = nj.
    Inoltre, la funzione di base costante Ckh e' definita da Ckh(n1,..,nk) = h.
    La funzione unaria di base S calcola invece il successore.
    (c)
    Enunciare e discutere brevemente del I Teorema di Incompletezza di Goedel.
    Esercizio 2
    (a)
    Cosa si intende, in generale, per "semantica operazionale strutturata" dei linguaggi di programmazione? Che forma hanno i giudizi (asserzioni) derivabili nella semantica operazionale strutturata del linguaggio WHILE? Come e' definita la nozione di validita' per i giudizi di tale sistema formale?
    (b)
    Descrivere in dettaglio il significato della seguente regola della semantica operazionale del linguaggio WHILE:

    n ≥ 1     a, begin δ1 end ⇓ a'      a', begin δ2;..;δn end ⇓ b
    _________________________________________________________________

    a, beginδ1;δ2;..;δn end ⇓ b

    Servono altre regole per completare la semantica del costrutto beginδ1;δ2;..;δn end ? Se si, perche' e quali sono? se no, giustificare il motivo per cui la regola sopra descritta e' sufficiente.

    (c)
    Supponiamo di estendere il linguaggio WHILE con una istruzione case che abbia la seguente sintassi:
    case Xj =
        n1: δ1;
         .....
        nk: δk;
        otherwise: δk+1
    end
    L'esecuzione di un'istruzione case consiste nel controllare se la variabile Xj contenga uno tra i valori n1,..,nk, nel qual caso viene eseguita l'istruzione corrispondente, altrimenti viene eseguita l'istruzione δk+1.
    Scrivere uno o piu' assiomi e/o regole di inferenza che formalizzino la semantica dell'istruzione case
    Esercizio 3 Definire la grammatica regolare G che genera il linguaggio sull'alfabeto {a,b} composto dalle stringhe caratterizzate dal fatto che il penultimo carattere è b.
    Definire inoltre una grammatica lineare sinistra equivalente a G.
    Definire poi un ASFD che riconosca le stringhe del linguaggio generato da G.