summaryrefslogtreecommitdiffstats
path: root/programme-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'programme-inf105.tex')
-rw-r--r--programme-inf105.tex21
1 files changed, 12 insertions, 9 deletions
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