Fondamenti di Informatica, 27 Febbraio 2018

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, sul Forum.

Esercizio 1
(a) Fornire le definizioni di grammatiche di Chomsky di tipo 0, 1, 2 e 3.
(b) Costruire l'automa a stati finiti deterministico che accetta il linguaggio delle stringhe sull'alfabeto {a,b} con un numero pari di 'a' e un numero pari di 'b'.
(consideriamo pari il numero 0)
(b)B Costruire l'automa a stati finiti deterministico che accetta il linguaggio delle stringhe sull'alfabeto {a,b} con un numero dispari di 'a' e un numero dispari di 'b'.
(c) Sia G₁ = ({a, b}, {S,A}, P₁, S), dove P₁ sono le produzioni

S → Ab | b
A → aAa | aa

e sia G₂ = ({a, b}, {S,A}, P₂, S), dove P₂ sono le produzioni

S → Ab
A → Aaa | ε

Dimostrare che G₁ e G₂ sono equivalenti.

Esercizio 2
(a) Descrivere brevemente le caratteristiche principali dei linguaggi di programmazione funzionali, evidenziando le differenze con quelli imperativi.
(b) Sia {{M⁰,A⁰,I⁰, F⁰}, {persona¹, conoscente², cittadino¹} } una segnatura per la logica del primo ordine (calcolo dei predicati). Si consideri la struttura che ha come supporto l'insieme di tutte le persone e di tutti gli stati ed in cui si interpreta

M come Mario
A come Antonio
I come l'Italia
F come la Francia
persona(x) come "x e' una persona";
conoscente(x,y) come "x conosce y";
cittadino(x,y) come "x e' cittadino di y".

Scrivere la fbf il cui valore di verita' in tale struttura coincide con quello della seguente frase in italiano:

Tutti i conoscenti comuni a Mario e ad Antonio sono italiani, ma Mario ha anche conoscenti francesi.

(Si hanno a disposizione entrambi i quantificatori e tutti i connettivi logici)
(b)B Sia {{M⁰,A⁰,I⁰, F⁰}, {persona¹, conoscente², cittadino¹} } una segnatura per la logica del primo ordine (calcolo dei predicati). Si consideri la struttura che ha come supporto l'insieme di tutte le persone e di tutti gli stati ed in cui si interpreta

M come Mario
A come Antonio
I come l'Italia
F come la Francia
persona(x) come "x e' una persona";
conoscente(x,y) come "x conosce y";
cittadino(x,y) come "x e' cittadino di y".

Scrivere la fbf il cui valore di verita' in tale struttura coincide con quello della seguente frase in italiano :

Tutti i conoscenti comuni a Mario e ad Antonio sono francesi, ma Mario ha anche conoscenti italiani.

(Si hanno a disposizione entrambi i quantificatori e tutti i connettivi logici)
(c) Definire la relazione di conseguenza tautologica nella Logica Proposizionale (Calcolo Proposizionale) e dimostrare che non e' vero che, prese due fbf A e B, vale la seguente proprieta':

Se ( ⊨ A implica ⊨ B ) allora A ⊨ B

Esercizio 3
Supponiamo di estendere la sintassi del linguaggio WHILE, aggiungendo la produzione

<test> → ALL=0

Si vuole fare in modo che la condizione ALL=0 risulti vera quando tutte le variabili del programma sono uguali a zero.
Estendere la SOS di WHILE con opportuni assiomi e/o regole di inferenza in modo da tener conto di tale nuovo possibile test.
Esercizio 3B
Supponiamo di estendere la sintassi del linguaggio WHILE, aggiungendo la produzione

<test> → ALL≠0

Si vuole fare in modo che la condizione ALL≠0 risulti vera quando tutte le variabili del programma sono diverse da zero.
Estendere la SOS di WHILE con opportuni assiomi e/o regole di inferenza in modo da tener conto di tale nuovo possibile test.