Fondamenti di Informatica, 27 Febbraio 2023

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 {a^hb^k | 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.