The aim of this course is to give a mathematical approach to finite automata. At the end, students should master some fundamental algorithms about finite automata and regular languages: determinisation, minimisation, conversion of a regular expression to a finite automaton and vice versa (Kleene's theorem) and be prepared to address applications of automata theory to mathematics and computer science.
Detailed program of the course:
1. Words, languages, automata
Automata and recognisable languages
2. Operations on languages:
Product and star
Residuals of a language
3. From rational expressions to automata
4. From automata to languages
McNaughton and Yamada algorithm
A graphical method of resolution
5. Minimal automata
Minimal complete automaton
Students of degrees or masters related to mathematics and algebraic theory of automata and formal languages. Specially indicated for students of mathematics, starting from the second course of the degree.
The evaluation of this course will be continuous and based on exercises proposed during the course.
Xaro Soler Escrivà (Departamento de Matemáticas, Universidad de Alicante).
Jean-Éric Pin (Université Paris-Diderot and CNRS, Francia). Link to https://www.irif.fr/~jep/
Languages of teaching:
English and Spanish
From 04/02/2020 to 27/02/2020, Tuesdays and Thursdays from 16:00 to 18:30.