Scheda insegnamento
Teoria degli Automi
| anno accademico: | 2013/2014 |
| docente: | Flavio D'Alessandro |
| corsi di laurea: | Matematica (magistrale) Matematica per le Applicazioni (magistrale) |
| crediti formativi: | 6 (48 ore di lezione) |
| lingua di insegnamento: | italiano |
| periodo: | I sem (30/09/2013 - 17/01/2014) |
Aula ed orario di lezione
Frequenza: consigliata
Obiettivi del corso: Gli Automi sono modelli matematici di macchine digitali di grande interesse sia dal punto di vista teorico che applicativo. La teoria degli Automi Finiti costituisce una delle parti fondamentali dell'Informatica Teorica. In questo corso si fornisce una trattazione matematicamente rigorosa di alcuni risultati classici della teoria degli Automi Finiti e delle macchine sequenziali generalizzate nell'ambito della teoria algebrica dei semigruppi.
Programma di massima del corso: Elementi di teoria dei semigruppi; congruenze e morfismi di semigruppi; parti riconoscibili di un semigruppo e loro proprieta' elementari; parti razionali di un semigruppo; cenni al Problema di Burnside per i semigruppi e per i gruppi; semiautomi finiti; automi finiti; teoremi di Myhill e Nerode; alcune proprieta' di chiusura dei linguaggi riconoscibili; teoremi di iterazione; automi incompleti e non deterministici; proprieta' di chiusura dei linguaggi riconoscibili rispetto alle operazioni di prodotto, di stella e di shuffle; linguaggi razionali dei monoidi liberi e loro proprieta' elementari; linguaggi locali e teorema di Medvedev; teorema di Kleene; linguaggi razionali e grammatiche lineari a destra oppure a sinistra; automi a due vie e teorema di Rabin e Shepherdson; relazioni razionali e riconoscibili di monoidi liberi; teorema di Elgot e Mezei; teorema di Cross-section di Eilenberg; congruenze di semiautomi e di automi; automa connesso e minimale; morfismi di semiautomi e di automi; automa minimale e teorema di equivalenze; algoritmo di Moore e Conway; espressioni razionali; identita' razionali; espressioni razionali estese; star-height delle espressioni razionali; star-height generalizzata; linguaggi aperiodici; monoidi aperiodici; linguaggi senza stella e teorema di Schutzenberger; il problema della star-height estesa: cenni alla congettura di Mc Naughton e ai teoremi di Henneman.
Testo consigliato: F. D'Alessandro, A. de Luca, Teoria degli Automi Finiti, Springer Italia, Milano, 2013
Modalità di erogazione: convenzionale
Risultati di apprendimento - Conoscenze acquisite: Gli studenti avranno acquisito una conoscenza di alcuni risultati fondamentali della Teoria degli automi finiti.
Risultati di apprendimento - Competenze acquisite: Gli studenti saranno in grado di risolvere semplici problemi di Teoria degli automi finiti. Le competenze acquisite permetteranno loro di affrontare lo studio di alcuni problemi riguardanti i linguaggi formali.
Studio personale: la percentuale prevista di studio personale sul totale dell'impegno richiesto è del 65%