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