Fondamenti di Informatica, 30 Gennaio 2018

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.
  • 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) Dare la definizione di espressione regolare. Scrivere inoltre l'espressione regolare  che rappresenta il linguaggio di tutte le stringhe sull'alfabeto {a,b,c,d} che terminano con "abb".

    (b) Sia G=({a,b,c},{S,A,B},P,S) dove P contiene le seguenti regole 
    S -> Ac,
A -> AB | B,
B -> aAb | ab.
    Dimostrare che la stringa aaabbbc appartiene al linguaggio generato da G.

    (c) Dimostrare che il linguaggio 
    L = {ahbk | h,k>0, h>k}
    non e' regolare.
    Esercizio 2
    (a) Fornire la definizione di sistema formale consistente.
    Dato un sistema formale D ed un insieme M di fbf, cosa significa che M e' una teoria in D? Cos'e' la teoria pura di D?

    (b) Fornire la definizione di regola derivabile.
    Sia CL' il sistema formale CL in cui, al posto delle regole (Congr1) e (Congr2) ci sia la seguente regola: 
                     M=N      P=Q
              -----------------  (CONGR)
                    MP= NQ
    DImostrare che sia (Congr1) che (Congr2) sono derivabili in CL'.
    Ricordiamo tra gli assiomi di CL c'e quello di riflessivita' e che le regole di CL sono: 
     P = Q                P = Q  Q = R              R = R'  (PR) = (QR)               R = R'  (RP) = (RQ)
-------- (Symm)      --------------- (Trans)    --------------------- (Congr1)    --------------------- (Congr2) 
 Q = P                   P = R                     (PR) = (QR')                       (RP) = (R'Q)
    (c) Dimostrare nel sistema di deduzione naturale per la logica del primo ordine che
    ∀ x.(A(x) → B(x)) ⊢ ¬ ( A(c) ∧ ¬B(c) )
    dove c e' un simbolo di costante della segnatura.
    Se nella deduzione proposta si utilizzano regole di inferenza che hanno vincoli di applicabilita', descrivere tali vincoli e indicare perche' sono soddisfatti.
    Esercizio 3
    Descrivere un efficiente algoritmo di conversione da base 2 a base 8 e giustificarne formalmente la correttezza.