Fondamenti di Informatica, 14 Giugno 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.
E' obbligatorio essersi prenotati sul portale studenti del nostro
ateneo. In caso contrario non si puo' sostenmere l'esame.
I risultati
verranno indicati nella pagina web del corso.
Date ed orari degli orali, sul Forum.
Esercizio 1
(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 2
(a)
Nel contesto della Logica Proposizionale (Calcolo Proposizionale),
fornire le definizioni di
- assegnamento proposizionale
- tautologia
- fbf (formula ben formata) soddisfacibile
- fbf contraddittoria
(b)
Sia {{},{scontato1, pv1, alcoolico1, costapiu1}}
una segnatura per la logica del primo ordine (calcolo dei predicati).
Si consideri la struttura che ha come supporto l'insieme di tutti i prodotti ed in cui
si interpreta
- scontato(x) come "x e' scontato";
- pv(x) come "x e' un prodotto in vendita";
- alcoolico(x) come "x e' alcoolico";
- costapiu(x) come "x costa piu' di venti euro".
Scrivere la fbf il cui valore di verita'
in tale struttura
coincide con quello della seguente frase in italiano
:
Tra i prodotti in vendita sono scontati
tutti e soli quelli che costano piu di
venti euro e non sono alcoolici
(Si hanno a disposizione entrambi i quantificatori e tutti i connettivi logici)
(c)
In deduzione naturale, dimostrare che, nel caso in cui x ∉FV(β)
|-- (∀x.(α → β)) → ((∃x. α)→ β)
Specificare in quale punto della deduzione fornita risulti indispensabile
l'utilizzo della condizione x ∉FV(β)
Esercizio 3
Fornire la definizione di codice a lunghezza variabile e descrivere un codice ad espansione.