Automates et grammaires (A&G) - KAIN5M06

Objectif(s)

L'enseignement « Automates et Grammaires » comporte 4 volets :

• La présentation de résultats fondamentaux de l'informatique
  • une technique de preuve de correction de programmes,
  • différents modèles de calculs (séquentiel, parallèle, non-déterministe),
  • comment réaliser, en un temps fini, des opérations sur des données infinies (les langages représentés sous forme d'automates)
  • la récursivité

• L'illustration des ces notions dans le cas des automates et des grammaires

• Un exemple concret d'utilisation récente des automates
  vérification de drivers, protocoles médicaux, personnage autonome dans les jeux vidéo, ...

• Un exemple concret d'utilisation des grammaires attribuées

Compétences visées

• savoir prouver qu'un programme est correct
• savoir programmer à l'aide d'un automate
• savoir écrire un analyseur/traducteur simple

Contenu(s)

• Preuve de correction partielle de programmes par la technique de Floyd-Hoare-Dijkstra
  comment être sûr que un programme fait bien ce qu'on attend. Autrement dit, monterez-vous dans l'avion dont vous avez programmé le pilote automatique ?
• Automates (à nombres d'états finis/à pile, déterministes/non-déterministes)
  quel est le modèle de calcul d'un processeur ? y'a t'il des langages (des modèles) plus puissants que d'autres ?
• Représentations équivalentes (des grammaires régulières = équations d'Arden = expressions régulières = automates à nombre d'états fini)
  Comment passent-on d'une description lisible par un humain à une version utilisable par un processeur ?
• Application et implantation des automates
  Les automates sont utilisés pour programmer (des analyseurs lexicaux, des micro-controlleurs, des interfaces, des protocoles, des jeux,...), pour piloter (des chaines de production, des systèmes cyber-physiques,...) et pour vérifier (des drivers, des politiques de sécurité ...) en fait on en trouve un peu partout.
• Grammaires attribuées et génératives
  Les grammaires sont le quotidien des informaticiens qui ne cessent de traduire un langage ou des données d'un format vers un autre.
• Application (mini-projet)
  Implantation d'un traducteur de format de données à l'aide d'un générateur d'analyseurs syntaxiques (ANTLR ou JavaCC)

Connaissance de bases d'un langage de programmation impérative tel que C