Fondamenti di Informatica, 7 Ottobre 2014

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici o qualsivoglia app per 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, 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) Si dimostri, descrivendo l'isomorfismo di Cantor, che N (i numeri naturali) ed NxN (l'insieme delle coppie di numeri naturali) hanno la stessa cardinalita'.

    (b) Si definisca una codifica (e decodifica) per l'insieme {a,c,b,d}+ utilizzando l'isomorfismo di Cantor.

    (c) Si dimostri che esistono linguaggi che non possono essere generati da alcuna grammatica.
    Esercizio 2
    (a) Fornire la definizione di Macchina Astratta e descriverne le componenti.

    (b) Come e' possibile realizzare una macchina astratta? Cosa si intende per organizzazione a livelli di un sistema di calcolo?

    (c) E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio C++?
    Motivare brevemente la risposta.
    Esercizio 3
    Si consideri la seguente grammatica G=({1,0}, {S,A,B}, P, S), dove P e' composto dalle produzioni 
    S --> A | B 
    
A --> 0 | A1 
    
B --> 011C | 111C 
    
C --> ε | 01C
    Modificare le produzioni di G in modo che venga generato lo stesso linguaggio, ma la grammatica sia lineare destra.