Langages formels (11X003)

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

Pages du cours

• sur moodle (supports, informations, modalités d’examens, etc.)
• sur unige (informations administratives)

Notes de cours

• 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)