 | |
| INFO0213-2 | Automata and formal languages theory
 |
|
| Duration : | 30h Th, 10h Pr, 20h Mon. WS |
|
| Credits/ECTS : |
| Master in Mathematical Sciences, in-depth approach, 1st year | | Premier quadrimestre | | 10 |
|
| Master in Mathematical Sciences, didactic approach, 1st year | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité spécialisée en gestion, 1st year | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 1st year | | Premier quadrimestre | | 10 |
|
| Master in Mathematical Sciences, specialized approach, 1st year | | Premier quadrimestre | | 10 |
|
| Master in Mathematical Sciences | | Premier quadrimestre | | 10 |
|
|
|
| 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 (finite automata, pushdown automata). 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 (unavoidable subwords, patterns, periodic or recurrent 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, asymptotic estimate, .... 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 but we will sometimes refer to material from graph theory or computability. |
|
| 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. Personal homework during the year could be asked. |
|
| Written notes : | Lecture notes are available (in french) on http://www.discmath.ulg.ac.be/ (http:///) |
|
| 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. The final note will possibly include personal works. |
|
| 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/ |
|
|
| |
