Fondamenti di Informatica, 1 Febbraio 2016
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.
Occorre essersi prenotati sul portale studenti del nostro
ateneo. Se cio' non e' stato fatto, comunicarlo immediatamente
al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.
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 {{},{S1, P1, A2}} una segnatura dove S e P sono simboli
predicativi unari, mentre A e'
un simbolo predicativo binario.
Si consideri la struttura che ha come supporto l'insieme delle persone ed in cui
si interpreta
- S(x) come "x e' uno studente";
- P(x) come "x e' un professore";
- A(x,y) come "x apprezza y".
Scrivere la fbf il cui valore di verita'
in tale struttura
coincide con quello della seguente frase in italiano
:
Alcuni studenti apprezzano tutti i professori, altri no.
(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.