diff options
| -rw-r--r-- | programme-inf105.tex | 35 |
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é. % |