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