summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-03-22 15:29:23 +0100
committerDavid A. Madore <david+git@madore.org>2021-03-22 15:29:23 +0100
commita53a9ae2de99004ed4aa42628c5fb1a2719a4a6e (patch)
treeb782ac10f60fe254f759011c86b4549a6e2adcaa
parent45e407ab8196ae62128261c238e7f92ace86378b (diff)
downloadinf105-a53a9ae2de99004ed4aa42628c5fb1a2719a4a6e.tar.gz
inf105-a53a9ae2de99004ed4aa42628c5fb1a2719a4a6e.tar.bz2
inf105-a53a9ae2de99004ed4aa42628c5fb1a2719a4a6e.zip
Reorganize syllabus.
-rw-r--r--programme-inf105.tex46
1 files changed, 21 insertions, 25 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex
index e4ab97a..909924c 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -59,35 +59,36 @@ et notions sur les mots : concaténation de deux mots, longueur d'un
mot ; préfixe, suffixe, facteur, sous-mot et mot miroir.
Opérations sur les langages : opérations booléennes (complémentaire,
-union, intersection), concaténation, étoile de Kleene. Définition des
-langages rationnels. Expressions rationnelles.
+union, intersection), concaténation, étoile de Kleene.
+\thingy Définition des langages rationnels. Expressions rationnelles.
-\thingy Automates finis : automates déterministes (DFA), automates
-déterministes à spécification incomplète, automates non déterministes
-(NFA), automates non déterministes à transitions spontanées
-($\varepsilon$-NFA).
+Automates finis : automates déterministes (DFA), automates
+déterministes à spécification incomplète (DFAi), automates non
+déterministes (NFA), automates non déterministes à transitions
+spontanées ($\varepsilon$-NFA).
-Équivalence entre ces différentes sortes d'automates. Langages
-reconnaissables.
+\thingy Équivalence entre DFA, DFAi, NFA et $\varepsilon$-NFA.
+Langages reconnaissables.
-
-\thingy Stabilité des langages reconnaissables par complémentaire,
+Stabilité des langages reconnaissables par complémentaire,
union, intersection ; stabilité par concaténation et étoile de Kleene.
+
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
+\thingy 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 =algorithme de Kleene). Équivalence entre langages rationnels
et reconnaissables.
-
-\thingy Énoncé et démonstration du lemme de pompage pour les
+Énoncé et démonstration du lemme de pompage pour les
langages rationnels (=reconnaissables).
+\thingy Exemples d'utilisation du lemme de pompage.
+
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
@@ -101,25 +102,21 @@ peut décider algorithmiquement si deux expressions rationnelles sont
\thingy TD sur les automates finis et langages rationnels.
-\thingy TP sur les expressions régulières et automates finis.
-
-
\thingy Grammaires hors contexte\footnote{Je propose pour gagner du
temps de ne faire que mentionner au passage le fait qu'il existe des
grammaires plus générales, sans entrer dans les détails.}, langages
algébriques (=définis par une grammaire hors contexte). Dérivations,
dérivations gauches et droites. Arbre d'analyse (=de dérivation).
-Ambiguïté (grammaires inambiguës et ambiguës, exemple de langage
-intrinsèquement ambigu).
+Ambiguïté (grammaires inambiguës et ambiguës, exemple sans
+démonstration de langage intrinsèquement ambigu).
-
-\thingy Stabilité des langages algébriques par réunion, concaténation
+Stabilité des langages algébriques par réunion, concaténation
et étoile de Kleene. Les langages rationnels sont algébriques :
d'après ce qu'on vient de dire et directement en associant une
grammaire à un DFA ou NFA.
-L'intersection d'un langage algébrique et d'un langage rationnel est
-algébrique (admis sans démonstration).
+\thingy L'intersection d'un langage algébrique et d'un langage
+rationnel est algébrique (admis sans démonstration).
Lemme de pompage pour les langages algébriques (admis sans
démonstration, mais on peut esquisser l'idée).
@@ -155,10 +152,9 @@ ensemble est décidable ssi lui et son complémentaire sont
semi-décidables. Un ensemble est semi-décidable ssi il est (vide ou)
énuméré par une fonction calculable.
-Notion de machine universelle. Indécidabilité du problème de l'arrêt.
-
+\thingy Notion de machine universelle. Indécidabilité du problème de l'arrêt.
-\thingy TP sur les grammaires hors contexte avec JavaCC.
+Petit TD sur la calculabilité.
%