Fondamenti di Informatica, 31 Gennaio 2013
Non e' ammesso l'uso di alcun testo, appunti o
calcolatrici. 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)
Descrivere il sistema formale del Calcolo dei Predicati (Logica dei Predicati del primo ordine).
(b)
Dare la definizione di Teoria e di Teoria Pura.
Dimostrare che una Teoria Pura e' una Teoria.
(c)
Dimostrare che la formula ben formata
(∀ x.∃ y. ¬P(x,y) ) → ∃ y. ¬P(y,c)
dove c e' una costante,
non e' un teorema della Logica dei Predicati del primo ordine.
Esercizio 2
(a)
Dire perche' i linguaggi derivabili con grammatiche
con produzioni della forma
A → α B | β
(dove α β sono stringhe di terminali),
sono generabili con grammatiche con produzioni
della forma
A → aB | b
(dove a e b sono simboli terminali).
(b)
Dimostrare che il linguaggio {ahbk | h,k≥0 , h>k }
non e' regolare.
Descrivere la Macchina di Turing che riconosca tale linguaggio.
(c)
Dimostrare che, dato un alfabeto non vuoto, esiste almeno un linguaggio su tale alfabeto
non generabile da una grammatica di Chomsky.
Esercizio 3
Si consideri il seguente lambda-termine:
(λw.wx)(λy.yx)
Qual e' l'insieme delle sue variabili libere? e quale quello delle sue variabili legate?
Mostrare il procedimento
per arrivare alla sua forma normale, se quest'ultima esiste.