diff options
Diffstat (limited to 'programme-inf105.tex')
| -rw-r--r-- | programme-inf105.tex | 73 |
1 files changed, 27 insertions, 46 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex index e4ab97a..a65fc55 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,43 +102,23 @@ 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). +\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). - -\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). - -Lemme de pompage pour les langages algébriques (admis sans -démonstration, mais on peut esquisser l'idée). +L'intersection d'un langage algébrique et d'un langage +rationnel est algébrique (admis sans démonstration). 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 @@ -155,10 +136,10 @@ 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. +\thingy TD sur les grammaires hors contexte / langages algébriques, et +sur la calculabilité. % |