Fondamenti di Informatica, 2 Marzo 2017
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)
Fornire le definizioni formali di: grammatica, derivazione diretta, derivazione, forma di frase
e linguaggio generato da una grammatica.
(b)
Il linguaggio
{akbn | n ≥0, k≤ n}
e' regolare?
In caso di risposta affermativa, fornire un automa a stati finiti che lo riconosca. In caso di risposta
negativa, dimostrare formalmente che non e' regolare.
(c)
Dimostrare che l'insieme dei linguaggi di tipo 3 e' numerabile.
Esercizio 2
(a)
Fornire le definizioni di:
- Segnatura Σ per la logica dei predicati del prim'ordine
(calcolo dei predicati);
- Struttura
AΣ per una segnatura Σ;
-
Interpretazione di fbf su una struttura AΣ.
(b)
Dimostrare in deduzione naturale che
A→C, B→C |- (A∨B)→C
(c)
Enunciare il Primo teorema di incompletezza di Goedel e descrivere brevemente le
idee fondamentali della dimostrazione.
Esercizio 3
Supponiamo di voler utilizzare un codice a lunghezza variabile con quattro
formati predefiniti:
4 bit
8 bit
12 bit
16 bit
Dire, giustificando le risposte, qual e' la cardinalita' massima di un insieme per il quale si possa definire
un codice ad espansione nel caso di:
1) formati multipli predefiniti
2) espansione con cifra di espansione
3) espansione con configurazione di espansione