1. Je m'inscris

  Le lien vers le cours sera disponible quand nous aurons fini le chapitre.

1. PCP - Preuve de correction partielle de programmes par la méthode de Floyd-Dijkstra-Hoare
2. AEF - Automates à nombre d'états fini
3. GTD - Grammaires et Traitement de données
4. PARSER - Parsers which compute (en anglais)
5. TP & PROJET

  Preuve de correction partielle de programmes par la méthode de Floyd-Dijkstra-Hoare

1. Principe de recherche et de preuve d'invariants
2. Application à un algorithme complexe : la recherche d'un élément par dichotomie dans un tableau trié

  Les langages infinis et leurs représentations finies

1. Automates à espace d'états fini (AEF)
• Définition, Intersection, Complémentaire, Union, Restriction (voir outils)
• Automates minimaux & minimisation (voir outils)
• Automates non-déterministes & déterminisation (voir outils)
• Implantation d'automates déterministes et non-déterministes (voir outils)
• Applications des automates à espace d'états fini
2. Expression régulières, Équations d'Arden
3. Grammaires
   • Grammaires génératives
   • Grammaires avec attributs synthétisés/hérités (en anglais)

  Pour aller plus loin

1. Limitations des AEF : langages irréguliers
2. Automates à une pile et Grammaires de type 2
3. Extensions possibles des automates
   • Automates de Büchi
   • Automates d'arbres
   • Transducteurs et additionneurs