From 4777fa3b773734118eb294e814a47c14f2fec64a Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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