Fondamenti di Informatica, 20 Settembre 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 sostituzione nel λ-calcolo.
    (b) Calcolare la forma normale (mostrando la computazione eseguita) del λ-termine
    and T T
    dove
    and e' λab.abF
    T e' λxy.x
    F e' λxy.y

    (c) Enunciare e dimostrare il Lemma di Unicita' delle forme normali utilizzando il Teorema di Confluenza.
    Esercizio 2
    (a) Fornire la definizione di espressione regolare. Fornire inoltre l'espressione regolare
    che rappresenta il linguaggio di tutte le stringhe lunghe 3 sull'alfabeto {a,b,c,d}.

    (b) Sia G1 una grammatica con il seguente insieme di produzioni:
    S --> aS | b
    e sia G2 una grammatica con il seguente insieme di produzioni:
    S --> b | Ab
    A --> Aa | a
    Dimostrare che G1 e G2 sono equivalenti.

    (c) Dimostrare che il linguaggio
    L = {ahbk | h,k>0, h>k}
    non e' regolare.
    Esercizio 3
    Fornire la definizione di codice in complemento a 2 per i numeri interi.