Mathematics

FLAVIO D'ALESSANDRO
FLAVIO D'ALESSANDRO

General targets: acquisition of basic knowledge in automata theory.

Specific targets:

Knowledge and understanding: at the end of the course, students will be acquainted with the notions of deterministic and complete automaton, recognizable language, non-deterministic automaton, and rational language, together with theorems describing some fundamental properties, of algebraic and combinatorial nature, of such structures (description of languages accepted by finite automata in term of finite index congruences, rational operations in the free semigroup of strings, non deterministic models and minimal automata).

Apply Knowledge and understanding: at the end of the course, students will be able to solve simple problems of automata theory, by using algebraic and combinatorial techniques: construction of automata for the acceptance of languages, decidability and algorithmic properties of automata, tools to verify the non-recognazibility of formal languages.

Analytical and judgment abilities: successful students will be able to manipulate the basic objects of the theory and they will be able to understand the proofs of some theorems that are relevant in the theory of automata. Moreover they will be able to analyse relations with topics of mathematical theory of formal languages and theory of codes.

Communication skills: the student will be able to present, in a written classwork, his knowledge of the theory and the solutions of the exercises.

Learning skills: the acquired knowledge and skills will permit the student to study, at individual level or in a course taught in the LM, more advanced aspects of automata theory and of mathematical theory of formal languages.

As a prerequisite, the student should be familiar with some basic notions of abstract algebra and, in particular, with those ones of congruence and morphism of algebraic structures, and with the algebraic structures of semigroup, group and ring. Such knowledge is a precondition to attend the course. It is very useful the knowledge of some basic notions of Discrete mathematics and in particular with that of graph. No propedeutical course is expected for this course.

First part: Elements of semigroup theory and first results of Automata theory (20 hours)

Basic notions of semigroups; congruences and morphisms of semigroups; recognizable sets of
semigroups; rational sets of semigroups; the Burnside problem for semigroups and groups
(outline); finite semiautomata; finite automata; Myhill and Nerode theorems; closure
properties of recognizable languages with respect to the Boolean set operations;
pumping lemma and applications; incomplete and non deterministic automata;
closure properties of recognizable languages with respect to the concatenation of
words, the star, and the shuffle operations; rational languages and some basic properties;

Second part: fundamental results of Automata theory (28 hours)

locally testable languages and Medvedev theorem; Kleene's theorem; rational
languages and right (or left) linear grammars; 2-way automata and Rabin and Shepherdson
theorem; rational and recognizable relations of free monoids; Elgot and Mezei theorem; the
Cross-Section theorem of Eilenberg; congruences of semiautomata and automata; minimal
and connected automata; morphisms of semiautomata and automata; minimal automata and
the equivalence theorem; Moore and Conway algorithm; rational expressions; rational
identities; extended rational expressions; the star-height of rational expressions; the extended
aperiodical languages; aperiodical monoids; star-free languages and Schutzenberger theorem;
Mc Naughton star-height conjecture and some theorems of Hennemann (outiline).

Aldo de Luca, Flavio D'Alessandro, Teoria degli Automi Finiti, Collana UNITEXT, Springer Italia, Milano, 2013

oral exam