Fondamenti di Informatica (parte Madonia)
15 Luglio 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. 

(a) Dire perche' i linguaggi generabili 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ⁿbⁿ | n≥0} non e' regolare.

Descrivere la Macchina di Turing che riconosca tale linguaggio. 

(c) Fornire l'automa a stati finiti deterministico che riconosca il linguaggio (a*bb)+c. 

(d) Dimostrare che, dato un alfabeto non vuoto, esiste almeno un linguaggio su tale alfabeto non generabile da una grammatica di Chomsky.