From 834717ef2c2ed8eb7c9c7384db92843257312b8b Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 30 Jan 2017 17:29:22 +0100
Subject: Clarifications on curriculum.

---
 programme-inf105.tex | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

(limited to 'programme-inf105.tex')

diff --git a/programme-inf105.tex b/programme-inf105.tex
index f6ae6d8..078715b 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -74,12 +74,14 @@ 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.
+Les langages rationnels sont reconnaissables.  Automate de Thompson
+d'une expression rationnelle.
 
 Automates à transitions étiquetées par des expressions rationnelles
 (informellement), équivalence avec les autres sortes d'automates,
 équivalence avec les expressions rationnelles (par élimination des
-états).  Équivalence entre langages rationnels et reconnaissables.
+états =algorithme de Kleene).  Équivalence entre langages rationnels
+et reconnaissables.
 
 
 \thingy Énoncé et démonstration du lemme de pompage pour les
@@ -91,7 +93,7 @@ DFA minimal\footnote{On conviendra d'utiliser la notion d'automate
   puits.} (=canonique).  Algorithme de minimisation.
 
 
-\thingy TD sur les automates finis.
+\thingy TD sur les automates finis et langages rationnels.
 
 
 \thingy TP sur les expressions régulières et automates finis.
@@ -118,14 +120,15 @@ algébrique (admis sans démonstration).
 
 (Selon le temps disponible.)  L'appartenance d'un mot au langage
 défini par une grammaire hors contexte est algorithmiquement
-décidable\footnote{Par ex., esquisser comment on peut mettre la
-  grammaire sous forme normale de Chomsky et utiliser l'algorithme de
-  programmation dynamique (CYK) ?}.  Quelques notions sur l'analyse
-syntaxique en pratique : notion d'analyseurs descendants et
-ascendants.
+décidable\footnote{Par ex., en montrant qu'on peut trouver une
+  grammaire monotone équivalente ; ou bien esquisser comment on peut
+  mettre la grammaire sous forme normale de Chomsky et utiliser
+  l'algorithme de programmation dynamique (CYK) ?}.  Quelques notions
+sur l'analyse syntaxique en pratique : notion d'analyseurs descendants
+et ascendants (sans entrer dans les détails).
 
 
-\thingy TD sur les grammaires hors contexte.
+\thingy TD sur les grammaires hors contexte et langages algébriques.
 
 
 \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
-- 
cgit v1.2.3

