Saltar apartados

A mathematical course on finite automata

MATHEMATICAL ASPECTS OF AUTOMATA THEORY

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

 

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.

 

Teachers:

  • 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

 

Schedule:

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

 

ECTS credits:

2 ECTS credits for undergraduate students.

 

Price:

50€

 

Preinscription:

From 04/12/2019 to 31/01/2020.

 

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: informacio@ua.es, and for enquiries on this web server: webmaster@ua.es

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