 |  |  |  |  |
| | |
||||
| INFO0213-1 | Automates et langages formels
[ english version ]
| |||||
| ||||||
| Durée : | 30h Th, 10h Pr | |||||
| ||||||
| Crédits/ECTS : |
| |||||
| ||||||
| Titulaire(s) : | Michel Rigo | |||||
| ||||||
| ||||||
| Aperçu général : | On présente quelques notions fondamentales de la théorie des langages formels et de combinatoire sur les mots. On étudie les langages réguliers et algébriques en insistant sur leurs aspects théoriques mais aussi algorithmiques. Ces concepts trouvent en particulier de nombreuses applications en informatique (théorique) comme par exemple l'analyse syntaxique, la vérification ou encore la compilation mais aussi en mathématiques : systèmes de numération et théorie élémentaire des nombres, logique, théorie des graphes, combinatoire, ... | |||||
| ||||||
| Objectif du cours : | Dans ce cours, on introduit la notion de langage formel (constitué de mots finis sur un alphabet fini). Cette présentation est illustrée par quelques résultats classiques en combinatoire sur les mots. On s'intéresse tout d'abord aux langages possédant les propriétés syntaxiques les plus simples, à savoir les langages réguliers. Les thèmes abordés sont : expressions régulières, automates finis déterministes, automates non déterministes, automate minimal et congruence de Nerode, minimisation d'automates, expressions sans étoile, monoïde syntaxique, théorèmes de stabilité, théorèmes de gonflement, problème de dénombrement, .... Une large part du cours est consacrée à la présentation théorique de ces concepts. On donnera néanmoins quelques applications en algorithmique du texte mais aussi en arithmétique par l'intermédiaire des systèmes de numération. Dans la deuxième partie, on présente les langages algébriques : grammaires hors contexte, arbres de dérivation, théorème de Parikh et ensembles semi-linéaires, langages commutatifs, formes normales, automates à pile, langages de Dyck,... | |||||
| ||||||
| Pré-requis : | Aucun pré-requis. | |||||
| ||||||
| Organisation : | Le cours est consacré principalement aux aspects théoriques des langages formels. Les séances de répétition permettent de présenter la résolution d'exercices mais surtout l'illustration et la concrétisation des concepts vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. | |||||
| ||||||
| Notes de cours : | Des notes de cours seront distribuées aux étudiants lors du premier cours. | |||||
| ||||||
| Evaluation : | L'examen en session comporte une partie orale et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. | |||||
| ||||||
| Contacts : | M. Rigo Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be | |||||
| ||||||
| Remarques : | Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ | |||||
| ||||||
ULg : Administration de l'Enseignement et des Etudiants - Affaires Académiques
Responsable de l'information : Monique Marcourt, direction A.E.E.
Date de validité des données : 27/02/2006
Réalisation SEGI