Automata and formal languages

Duration

30h Th, 20h Pr

Number of credits

Lecturer

Julien Leroy

Language(s) of instruction

French language

Organisation and examination

Teaching in the first semester, review in January

Schedule

Schedule online

Units courses prerequisite and corequisite

Prerequisite or corequisite units are presented within each program

Learning unit contents

We present some fundamental notions in formal languages theory and combinatorics on words. We introduce classical results in the combinatorial theory of finite and infinite words (words generated by iterated morphism, topology on infinite words, the overlap-free Thue-Morse word,...). Then we study regular and context-free languages insisting both on theoretical aspects and the corresponding algebraic structures as well as on algorithmic aspects (finite automaton, theory of the minimal automaton, syntactic monoid, growth function, pushdown automaton). These concepts have many applications in (theoretical) computer science like syntactical analysis, verification or compiling but also in mathematics : number systems, number theory, logic, graph theory, combinatorics,...

Learning outcomes of the learning unit

At the end of this course, the student will master the main concepts arising in combinatorics on words and formal language theory. The student will have at his/her disposal a set of theoretical results that he/she will be able to prove, often with a constructive proof. In particular, he/she will be able to obtain regular expressions respecting particular syntactical criteria, build deterministic or non-deterministic automata, find the minimal automaton of a given language, give explicitely the Nerode congruence or the syntactic monoid of a language, minimize automata, decide whether or not a regular language is star-free. Moreover, the student will handle stabilization theorems and pumping lemmas to prove the (non-)regularity of a language. He/she will be able to study the growth (or complexity) function of a language and gain insight about its asymptotic behavior. For context-free languages, the student will be able to build context-free grammars, derivation trees, make use of Parikh's theorem, have a grasp on semi-linear sets, derive some normal forms for a given grammar (in particular, Chomsky normal form), build push-down automata, prove and use Chomsky-Schützenberger's theorem. Finally, the acquired tools may be used in text algorithms, for compiling, or in arithmetics using numeration systems.

Prerequisite knowledge and skills

Basic material from any courses in linear algebra and group theory (or abstract algebra). Having attended lectures on graph theory and theory of computation is an advantage (but it is not a prerequisite).

Planned learning activities and teaching methods

Theoretical lectures interacting with students. During exercises sessions, students are facing exercises that must be solved.

Mode of delivery (face-to-face ; distance-learning)

Lectures are dedicated to theoretical aspects of formal languages. Practical sessions are devoted to solve exercises and to enlighten the concepts presented during the lecture. Detailed schedule will be given at the beginning of the academic year. Personal homeworks during the year may be asked.

Recommended or required readings

Lecture notes are available (in french) on http://www.discmath.ulg.ac.be/ Lectures notes are sufficient. Additional material for those wanting to broaden their knowledge:

• J. Sakarovitch, Elements of automata theory, Cambridge Univ. Press (2009).
  
• T. A. Sudkamp, Languages and Machines, An Introduction to the Theory of Computer Science, second edition, Addison-Wesley (1997).

• J. Berstel, D. Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007).
  
• J. Shallit, A second course in formal languages and automata theory, Cambridge Univ. Press (2008).
  
• A. Mateescu, A. Salomaa, Formal Languages: an Introduction and a Synopsis, Handbook of Formal Languages, vol. 1, Springer, (1997). 

• S. Yu, Regular Languages, Handbook of Formal Languagues, vol. 1, Springer, (1997).
• D. Perrin, Les débuts de la théorie des automates, Technique et Science Informatique14 (1995).
  
• G. Lallement, D. Perrin, Marcel-Paul Schützenberger (1920-1996), Semigroup Forum55 (1997).
  
• J.-M. Autebert, Langages algébriques, études et recherches en informatique, Masson (1987).

Assessment methods and criteria

The final examination is in two parts. An oral part devoted to the theory (mainly statements and proofs of theorems and discussion) but also direct applications of the theory. The written part is dedicated to the resolution of exercises and problems. The final note will possibly include personal works.

Work placement(s)

Organizational remarks

Some useful informations are given on http://www.discmath.ulg.ac.be/ In particular, one has access to the log of the year and also the ones of previous years. This course is organized on academic years starting on an even year (for instance 2018-2019).

Contacts

J. Leroy Institut de Mathématique (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 - E-mail : J.Leroy@ulg.ac.be

Items online