summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--programme-inf105.tex35
1 files changed, 10 insertions, 25 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex
index 909924c..a65fc55 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -102,39 +102,23 @@ peut décider algorithmiquement si deux expressions rationnelles sont
\thingy TD sur les automates finis et langages rationnels.
-\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 sans
-démonstration de langage intrinsèquement ambigu).
+\thingy Grammaires hors contexte, langages algébriques (=définis par
+une grammaire hors contexte). Dérivations\footnote{On pourra même
+ sauter complètement la notion de dérivation et définir le langage
+ engendré par une grammaire à travers les arbres d'analyse.}. Arbre
+d'analyse (=de dérivation). Ambiguïté (grammaires inambiguës et
+ambiguës).
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.
-\thingy L'intersection d'un langage algébrique et d'un langage
+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).
-
L'appartenance d'un mot au langage défini par une grammaire hors
-contexte est algorithmiquement décidable (l'énoncer et éventuellement
-expliquer une approche possible\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) ?} si le
-temps le permet).
-
-Selon le temps disponible : 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 et langages algébriques.
+contexte est algorithmiquement décidable (admis sans démonstration).
\thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
@@ -154,7 +138,8 @@ semi-décidables. Un ensemble est semi-décidable ssi il est (vide ou)
\thingy Notion de machine universelle. Indécidabilité du problème de l'arrêt.
-Petit TD sur la calculabilité.
+\thingy TD sur les grammaires hors contexte / langages algébriques, et
+sur la calculabilité.
%