 | |
| INFO0213-1 | Automata and formal languages theory
 |
|
| Duration : | 30h Th, 10h Pr |
|
| Credits/ECTS : |
|
|
| Holder(s) : | Michel Rigo |
|
| Language : | Langue française |
|
| Course contents : | We present some fundamental notions in formal languages theory and combinatorics on words. We study regular and context-free languages insisting both on theoretical and algorithmic aspects. These concepts have a lot of applications in (theoretical) computer science like syntactical analysis, verification or compiling but also in mathematics : number systems, elementary number theory, logic, graph theory, combinatorics,... |
|
| Course objective : | In this course, we introduce the notion of formal language (made of finite words over a finite alphabet). This presentation is illustrated by some classical examples in combinatorics on words. First, we are interested in languages having the simplest syntactical properties, i.e., the regular languages. The considered topics are : regular expressions, deterministic finite automata, nondeterministic automata, minimal automaton, Nerode congruence, minimizing automata, star-free expressions, syntactic monoid, stabilization theorems, pumping lemmas, enumeration problems, .... The lecture is mainly concerned with theoretical aspects but we will give some examples in text algorithms and arithmetic through number systems. In the second part, we present context-free languages : context-free grammars, derivation trees, Parikh's theorem and semi-linear sets, commutative languages, normal forms, stack automata, Dyck's languages, ... |
|
| Prerequisites : | No specific knowledge is needed. |
|
| Organization : | 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. |
|
| Written notes : | Lecture notes are available (in french) |
|
| Assessment : | The final examination is in two parts. An oral part devoted to the theory (mainly proofs of theorems) but also direct applications of the theory. The written part is dedicated to the resolution of exercises and problems. The expected knowledge needed for this examination will be officially announced during the year. |
|
| 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 |
|
| Remarks : | Some useful informations are given on
http://www.discmath.ulg.ac.be/ |
|
|
| |
