Ce cours s’intéresse aux automates finis comme premier modèle de calcul:

  • notion de reconnaissabilité: quels sont les langages reconnus par automates finis? Langages réguliers, lemme de l’étoile.
  • robustesse du modèle: équivalence des automates finis déterministes et non-déterministes, existence d’un automate déterministe minimal.
  • applications: expressions régulières, grammaires, validation syntaxique par automate fini, programmation (grep, etc)
  • ouverture: grammaires hors contexte et automates à pile, en ouverture vers les cours de compilation, et de calculabilité et complexité, en 2ème année

Supports

Supports de cours

  1. Automates finis
  2. Non-déterminisme et déterminisation
  3. Automate minimal et minimisation
  4. Expressions régulières, langages réguliers et théorème de Kleene
  5. Langages non-réguliers et lemme de l’étoile
  6. Grammaires
  7. Introduction aux automates à pile

Supports de TD

Ressources supplémentaires

Vous pouvez utiliser l’outil JFLAP pour construire et simuler les automates finis, et leur appliquer les algorithmes vus en cours (déterminisation, minimisation, etc), ainsi que pour manipuler les grammaires et les automates à pile.