 | |
| 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 | | 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 in Mathematical Sciences, specialized approach, 1st year | | First semester | | 8 |
|
| Master in Mathematical Sciences | | First semester | | 8 |
|
|
|
| Holder(s) : | Michel Rigo |
|
| Language : | 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. 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 automata, pushdown automata). 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,... |
|
| 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, etc. 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, théorème de Chomsky-Schützenberger. |
|
| Prerequisites : | Basic material from any courses in graph theory , group theory (or abstract algebra) and theory of computation. |
|
| 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 homeworks during the year may 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/ |
|
|
| |
