Obiettivi generali: acquisire conoscenze di base in teoria degli automi.


Obiettivi specifici:

Conoscenza e comprensione: al temine del corso lo studente avrà acquisito familiarità con i concetti di automa deterministico e completo, di linguaggio riconoscibile, di automa non deterministico, di linguaggio razionale e di teoremi che descrivono alcune proprietà fondamentali di natura algebrica e combinatoria di queste strutture
(descrizione dei linguaggi accettati da automi in termini di congruenze di indice finito,
di operazioni razionali nel mondi libero delle stringhe su di un alfabeto dato, di modelli
non deterministici e di automi minimali).



Applicare conoscenza e comprensione: al temine del corso lo studente sarà in grado di risolvere semplici problemi che richiedano l'uso di tecniche combinatorie e algebriche di teoria degli automi: costruzione di automi per il riconoscimento di linguaggi, proprietà algoritmiche e di decidibilità, strumenti per verificare la non riconoscibilità di linguaggi.

Capacità critiche e di giudizio: Gli studenti che abbiano superato l'esame avranno maturato dimistichezza con gli oggetti basilari della teoria. In particolare, saranno in grado di leggere criticamente le dimostrazioni dei risultati della teoria esposti nel corso e di analizzare relazioni ed analogie con argomenti di teoria matematica dei linguaggi formali e di teoria dei codici.

Capacità comunicative: capacità di esporre in forma scritta i risultati teorici e la soluzione degli esercizi proposti nella prova di esame.

Capacità di apprendimento: le conoscenze acquisite permetteranno uno studio, individuale o impartito in un corso di LM, di aspetti più specialistici di teoria degli automi e di teoria matematica dei linguaggi formali.