diff options
| -rw-r--r-- | programme-inf105.tex | 16 |
1 files 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 |