Fondamenti di Informatica, 6 Dicembre 2021

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, sulla chat pubblica di Teams del corso.

    • 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) Descrivere, nel linguaggio dell'aritmetica di Peano, le formule ben formate P(x) e Q(x,y,z) corrispondenti, rispettivamente, alle seguenti relazioni sui numeri naturali: (c) Fornire una deduzione nella logica proposizionale in deduzione naturale per il teorema `
    ((A∧B) → C)) → (A → (B → C))
    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)