 | | |
| 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 | | First semester | | 8 |
|
| Master in Mathematical Sciences, didactic approach, 1st year | | First semester | | 8 |
|
| Master in Mathematical Sciences, professional focus in management, 1st year | | First semester | | 8 |
|
| Master in Mathematical Sciences, professional focus in computer science, 1st year | | First semester | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en statistiques, 1st year | | First semester | | 8 |
|
| Master in Mathematical Sciences, specialized approach, 1st year | | First semester | | 8 |
|
| Master in Mathematical Sciences | | First semester | | 8 |
|
|
|
| Lecturer : | Michel Rigo |
|
Language(s) of instruction :
|
| French language |
|
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, graph theory , group theory (or abstract algebra) and theory of computation. |
|
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/ (http:///) |
|
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. |
|
Organizational remarks :
|
| Some useful informations are given on
http://www.discmath.ulg.ac.be/ |
|
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 exercices) |
|
|
|
| |
