Fondamenti di Informatica (parte Madonia)
15 Luglio 2024
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, su Teams.
(a)
Fornire le definizioni di grammatiche di Chomsky di tipo 0, 1, 2 e 3.
(b)
Costruire l'automa a stati finiti deterministico che accetta il linguaggio delle stringhe sull'alfabeto {a,b} con un numero pari di 'a' e un numero pari di 'b'.
(consideriamo pari il numero 0)
(c)
Costruire l'automa a stati finiti deterministico che accetta il linguaggio delle stringhe sull'alfabeto {a,b} con un numero dispari di 'a' e un numero dispari di 'b'.
(d)
Sia G1 = ({a, b}, {S,A}, P1, S), dove P1 sono le produzioni
S → Ab | b
A → aAa | aa
e sia G2 = ({a, b}, {S,A}, P2, S), dove P2 sono le produzioni
S → Ab
A → Aaa | ε
Dimostrare che G1 e G2 sono equivalenti.