From 4777fa3b773734118eb294e814a47c14f2fec64a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 29 Oct 2017 15:59:33 +0100
Subject: Clarify course curriculum.

---
 programme-inf105.tex | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

(limited to 'programme-inf105.tex')

diff --git a/programme-inf105.tex b/programme-inf105.tex
index 078715b..b0291de 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -35,7 +35,7 @@
 %
 %
 \begin{document}
-\title{THL (Théorie des langages)\\Programme indicatif}
+\title{THL (Théorie des langages)\\Programme du cours}
 \author{David A. Madore}
 \maketitle
 
@@ -74,8 +74,9 @@ reconnaissables.
 
 \thingy Stabilité des langages reconnaissables par complémentaire,
 union, intersection ; stabilité par concaténation et étoile de Kleene.
-Les langages rationnels sont reconnaissables.  Automate de Thompson
-d'une expression rationnelle.
+Les langages rationnels sont reconnaissables.  Automate de Glushkov
+\emph{ou} (au choix) automate de Thompson d'une expression
+rationnelle.
 
 Automates à transitions étiquetées par des expressions rationnelles
 (informellement), équivalence avec les autres sortes d'automates,
@@ -90,7 +91,11 @@ langages rationnels (=reconnaissables).
 DFA minimal\footnote{On conviendra d'utiliser la notion d'automate
   déterministe \emph{complet}, et la première étape de minimisation
   sera de compléter l'automate en lui ajoutant éventuellement un
-  puits.} (=canonique).  Algorithme de minimisation.
+  puits.} (=canonique).  Algorithme de minimisation (=algorithme de
+Moore).  (On insistera plus sur l'aspect algorithmique que sur la
+formulation théorique du théorème de Myhill-Nerode.)  Conséquence : on
+peut décider algorithmiquement si deux expressions rationnelles sont
+équivalentes.
 
 
 \thingy TD sur les automates finis et langages rationnels.
@@ -116,7 +121,8 @@ grammaire à un DFA ou NFA.
 L'intersection d'un langage algébrique et d'un langage rationnel est
 algébrique (admis sans démonstration).
 
-Énoncé du lemme de pompage pour les langages algébriques.
+Lemme de pompage pour les langages algébriques (admis sans
+démonstration, mais on peut esquisser l'idée).
 
 (Selon le temps disponible.)  L'appartenance d'un mot au langage
 défini par une grammaire hors contexte est algorithmiquement
-- 
cgit v1.2.3

