Théorie des langages formels

Durée

30h Th, 30h Pr

Nombre de crédits

Enseignant

Julien Leroy

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

Langue française

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

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 avec "tableau et craies" ou projection, en interaction avec les étudiants. Dans les séances d'exercices, les étudiants pourront être face à des exercices qu'ils doivent résoudre.

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

Le cours est consacré principalement aux aspects théoriques. Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou 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.

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 et une partie écrite. L'examen oral porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau ou sur feuille un petit exercice). L'examen écrit porte sur la matière des répétitions.

Stage(s)

Remarques organisationnelles

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@uliege.be

Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session de mai-juin

Méthodes d'apprentissage mises en œuvre : enseignement à distance

Le cours théorique se poursuit via la publication régulière de podcasts sur le site institutionnel de l'Université. Ces podcasts sont réalisés en français. Des listes d'exercices sont envoyées par mail aux étudiants. Par la suite, un correctif de ces exercices est également envoyé.

Matière de l'évaluation

L'examen portera sur toute la matière vue au cours théorique ou aux séances d'exercices. Les questions consisteront en des résolutions d'exercice ou en des applications directes de la théorie. Certaines démonstrations ou parties de démonstrations pourront être demandées.

Méthodes d'évaluation

L'évaluation consistera en un examen écrit à distance. Le titulaire du cours enverra un mail aux étudiants à l'horaire prévu. L'examen sera attaché à ce mail sous forme de document pdf. Il y aura plusieurs questionnaires différents. Les étudiants doivent envoyer leurs réponse électroniquement, sous la forme d'un scan ou de photos lisibles de leur copie à l'adresse j.leroy@uliege.be, avant la fin du temps imparti. L'étudiant qui enverrait sa copie en retard se verra proposé un examen oral à distance supplémentaire le surlendemain de l'évaluation écrite. Celui-ci portera sur la copie écrite de l'étudiant, mais pourra aussi inclure d'autres questions.

Contact

Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session août-sept

Matière de l'évaluation

Similaire à la session de juin.

Méthodes d'évaluation (et plateforme utilisée)

Similaire à la session de juin.

Contact(s)