Duration
30h Th, 20h Pr
Number of credits
| Bachelor in mathematics | 5 crédits |
Lecturer
Language(s) of instruction
French language
Organisation and examination
Teaching in the first semester, review in January
Schedule
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 using "blackboard and chalk" or beamer, interacting with students. During exercises sessions, students could face exercises that must be solved.
Mode of delivery (face to face, distance learning, hybrid learning)
Blended learning
Additional information:
Lectures are mainly dedicated to theoretical aspects. Pratical 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.
The course will be organized in face-to-face except maybe for some parts where podcasts will be available.
Part of the exercises will consists in homeworks.
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).
Any session :
- In-person
written exam ( open-ended questions ) AND oral exam
- Remote
written exam ( open-ended questions )
- If evaluation in "hybrid"
preferred in-person
Additional information:
The final examination is divided into an oral part and a written exam. The oral exam is devoted to the theory but also direct applications of the theory (student may be asked to solve a small exercise on the blackboard or on a sheet of paper). The written exam evaluate the comprehension of the material of the exercice sessions.
Work placement(s)
Organisational remarks and main changes to the course
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@uliege.be