Fondamenti di Informatica (parte MADONIA), 24 Giugno 2025 Non ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini osmartphone(questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Esercizio (a) - Dare la definizione di Automa a Stati Finiti Deterministico e di Automa a Stati Finiti Non Deterministico e di linguaggio riconosciuto da ciascuno dei due modelli. - Si fornisca un Automa a Stati Finiti, sullalfabeto {a, b}, che riconosca il linguaggio denotato dalla seguente espressione regolare bab(ab)*. Esercizio (b) - Dare la definizione di linguaggio rappresentato (o denotato) da una espressione regolare. - Determinare lespressione regolare per il linguaggio L di tutte le stringhe, sullalfabeto {a, b}, che cominciano per bb e contengono la stringa aa come sottostringa. Esercizio (c) - Dare la definizione di grammatica di tipo 3 e di linguaggio generato da una grammatica. - Si fornisca una grammatica di tipo 3 che generi il linguaggio L, sullalfabeto {a, b}, cos definito L = {anbm con n, m >0}. Esercizio (d) - Dare la definizione di Macchina di Turing deterministica e di linguaggio accettato da una Macchina di Turing deterministica. - Dare la definizione di linguaggio strettamente di tipo n.