Fondamenti di Informatica, 5 Settembre 2022
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, sulla chat pubblica di Teams del corso.
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.
(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.