Docente
|
D'ALESSANDRO FLAVIO
(programma)
Prima parte: Elementi di teoria dei semigruppi e prime nozioni di Teoria degli Automi (20 ore)
Elementi di teoria dei semigruppi; congruenze e morfismi di semigruppi; parti riconoscibili di un semigruppo e loro proprietà 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; proprietà di chiusura dei linguaggi riconoscibili rispetto alle operazioni Booleane insiemistiche; teoremi di iterazione; automi incompleti e non deterministici; proprietà di chiusura dei linguaggi riconoscibili rispetto alle operazioni di prodotto, di stella e di shuffle; linguaggi razionali dei monoidi liberi e loro proprietà
elementari.
Seconda parte: risultati fondamentali di Teoria degli Automi (28 ore)
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 equivalenza; algoritmo di Moore e Conway; espressioni razionali; identità 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.
Aldo de Luca, Flavio D'Alessandro, Teoria degli Automi Finiti, Collana UNITEXT, Springer Italia, Milano, 2013
|