2017-2018 / INFO0213-2

Automates et langages formels

Durée

30h Th, 20h Pr

Nombre de crédits

 Master en sciences mathématiques, à finalité8 crédits 
 Master en sciences mathématiques8 crédits 

Enseignant

Michel Rigo

Langue(s) de l'unité d'enseignement

Langue française

Organisation et évaluation

Enseignement au premier quadrimestre, examen en janvier

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

On présente quelques notions fondamentales de la théorie des langages formels et de combinatoire des mots. Le cours débute par quelques résultats classiques en combinatoire des mots finis et infinis (mots engendrés par morphisme itéré, topologie sur les mots infinis, mot de Thue-Morse sans chevauchement,...). Ensuite, on étudie les langages réguliers et algébriques en insistant sur les aspects théoriques fondamentaux et les structures algébriques sous-jacentes, mais aussi algorithmiques (automate fini, théorie de l'automate minimal, fonction de croissance, monoïde syntaxique, automate à pile). 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 des nombres, logique, théorie des graphes, combinatoire, ...

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

Au terme de ce cours, l'étudiant maîtrisera les principaux concepts issus de la combinatoire des mots et de la théorie des langages formels. L'étudiant disposera d'un ensemble de résultats théoriques pour lesquels il sera capable d'en fournir des preuves, le plus souvent constructives. En particulier, ceci lui permettra de fournir des expressions régulières respectant un critère syntaxique donné, construire des automates finis déterministes ou non, obtenir l'automate minimal d'un langage donné, expliciter la congruence de Nerode et le monoïde syntaxique d'un langage, minimiser des automates, décider si un langage régulier est sans étoile. En outre l'étudiant sera capable d'exploiter des théorèmes de stabilité ou de gonflement pour prouver la (non)-régularité d'un langage. Il/elle sera à même d'étudier la fonction de croissance (ou de complexité) d'un langage et d'en tirer des renseignements asymptotiques. Pour les langages algébriques, l'étudiant sera capable de construire des grammaires hors contexte, des arbres de dérivation, tirer parti du théorème de Parikh, appréhender les ensembles semi-linéaires, mettre une grammaire sous diverses formes normales (en particulier, la forme normale de Chomsky), contruire des automates à pile, démontrer et utiliser le théorème de Chomsky-Schützenberger. Enfin, les outils acquis doivent pouvoir être appliqués en algorithmique du texte ou en compilation, mais aussi en arithmétique par l'intermédiaire des systèmes de numération.

Savoirs et compétences prérequis

Notions élémentaires vues dans les cours d'algèbre linéaire et de théorie des groupes. Avoir suivi des cours de théorie des graphes et/ou de calculabilité est un atout (mais n'est pas nécessaire).

Activités d'apprentissage prévues et méthodes d'enseignement

Cours théorique en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre.

Mode d'enseignement (présentiel ; enseignement à distance)

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. La réalisation de travaux personnels en cours d'année peut être envisagée.

Lectures recommandées ou obligatoires et notes de cours

Des notes de cours seront distribuées aux étudiants lors du premier cours. Elles sont aussi téléchargeables sur http://www.discmath.ulg.ac.be/ Les notes de cours sont suffisantes. Quelques compléments pour approfondir :

  • J. Sakarovitch, Elements de théorie des automates, Vuibert, Paris, (2003).
  • T. A. Sudkamp, Languages and Machines, An Introduction to the Theory of Computer Science, second edition, Addison-Wesley (1997).
  • J. Berstel, D. Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007).
  • J. Shallit, A second course in formal languages and automata theory, Cambridge Univ. Press (2008).
  • A. Mateescu, A. Salomaa, Formal Languages: an Introduction and a Synopsis, Handbook of Formal Languages, vol. 1, Springer, (1997).
  • S. Yu, Regular Languages, Handbook of Formal Languagues, vol. 1, Springer, (1997).
  • D. Perrin, Les débuts de la théorie des automates, Technique et Science Informatique14 (1995).
  • G. Lallement, D. Perrin, Marcel-Paul Schützenberger (1920-1996), Semigroup Forum55 (1997).
  • J.-M. Autebert, Langages algébriques, études et recherches en informatique, Masson (1987).

Modalités d'évaluation et critères

L'examen en session comporte une partie orale (énoncés et preuves de résultats, avec discussion) 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 cote finale pourra, le cas échéant, prendre en compte des travaux personnels.

Stage(s)

Remarques organisationnelles

Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ On peut en particulier y consulter le journal de bord de l'année en cours et aussi celui des années précédentes. Ce cours est organisé les années académiques débutant une année paire (par ex. 2018-2019).

Contacts

J. Leroy Institut de Mathématique (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 - E-mail : J.Leroy@ulg.ac.be
M. Rigo Institut de Mathématique (B37) -Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be

Notes en ligne

Notes de cours
Syllabus (théorie et énoncés d'exercices)