Saltar apartados

A mathematical course on finite automata


Objectives of the course:

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

  • Words
  • Languages
  • Rational languages
  • Automata and recognisable languages
  • Some algebra
  • Exercises

2. Operations on languages:

  • Boolean operations
  • Product and star       
  • Residuals of a language
  • Asynchronous automata   
  • Exercises

3. From rational expressions to automata

  • Local languages    
  • Glushkov's algorithm
  • Exercises

4. From automata to languages

  • Extended automata 
  • McNaughton and Yamada algorithm
  • Linear equations
  • A graphical method of resolution
  • Kleene's theorem
  • Exercises

5. Minimal  automata

  • Minimal complete automaton
  • Minimal automaton 
  • Hopcroft's algorithm
  • Double inversion   
  • Exercises

Get a glimpse of this PDF to have an overwiew of the course.


Aimed at:

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.


Evaluation criteria:

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


Languages of teaching:

English and Spanish



From 02/02/2020 to 25/02/2020, Tuesdays and Thursdays from 16:00 to 18:30.



ECTS credits:

2 ECTS credits for undergraduate students.


Pre-registering will be available from january 8th, 2021 on.




Initially, the course will be presential. But according to COVID19, it could become online.



Department of Mathematics

Universidad de Alicante
Carretera de San Vicente del Raspeig s/n
03690 San Vicente del Raspeig
Alicante (Spain)

Tel: (+34) 96 590 3531

Fax: (+34) 96 590 3531

For further information:, and for enquiries on this web server:

Carretera San Vicente del Raspeig s/n - 03690 San Vicente del Raspeig - Alicante - Tel. 96 590 3400 - Fax 96 590 3464