Cette page contient les ressources pédagogiques du cours de Langages Formels des années précédentes. Pour l’année actuelle, ça se passe sur cette page.

Automne 2023

Enseignant : Arnaud Casteigts
Assistant : Alexandre-Quentin Berger
Monitrices : Léonie Dezempte et Léa Heiniger

Préambule : [slides]
Personnages : [1] - [2] - [3] - [4] - [5] - [6] - [7] - [8] - [9] - [10] - [11] - [12]
Cours 1 : Concepts de base : [notes de cours] - [vidéo] - [quiz]
Cours 2 : Automates finis (déterministes) : [notes de cours] - [vidéo] - [quiz]
Cours 3 : Non-déterminisme : [notes de cours] - [vidéo] - [quiz]
Cours 4 : Expressions régulières : [notes de cours] - [vidéo] - [quiz]
Cours 5 : Lemme de l’étoile : [notes de cours] - [vidéo]
Cours 6 : Grammaires formelles : [notes de cours] - [vidéo] - [quiz]
Cours 7 : Automates à pile : [notes de cours] - [vidéo]
Cours 8 : Équivalence AP - GHC : [notes de cours] - [vidéo]
Cours 9 : Lemme de l’étoile (hors-contexte) : [notes de cours] - [vidéo]
Cours 10 : Machines de Turing (déterministes) : [notes de cours] - [vidéo]
Cours 11 : Machines de Turing (divers) : [notes de cours] - [vidéo]
Cours 12 : Universalité et indécidabilité : [notes de cours] - [vidéo]

Pour aller plus loin

Introduction to the Theory of Computation (Michael Sipser)
(dont sont issus certains exemples du cours)