 | | |
| INFO0213-2 | Automata and formal languages theory
|
|
| Duration : | 30h Th, 10h Pr, 20h Mon. WS |
|
| Number of credits : |
| Master in Mathematical Sciences, in-depth approach, 1st year | | 8 |
|
| Master in Mathematical Sciences, didactic approach, 1st year | | 8 |
|
| Master in Mathematical Sciences, professional focus in management, 1st year | | 8 |
|
| Master in Mathematical Sciences, professional focus in computer science, 1st year | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en statistique, 1st year | | 8 |
|
| Master in Mathematical Sciences, specialized approach, 1st year | | 8 |
|
| Master in Mathematical Sciences | | 8 |
|
|
|
| Lecturer : | Michel Rigo |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| Teaching in the first semester, review in January |
|
Course 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 course :
|
| 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. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| 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" 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. |
|
Contacts :
|
| M. Rigo
Institute of Mathematics (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
|
| Items online : |
|
| Lecture notes |
| Syllabus (theory and statements of exercises) |
|
|
|
| |
