Automates et Grammaires

Ce cours présente quelques résultats fondamentaux de l'informatique

• une technique de preuve de correction de programmes
• l'utilisation du calcul comme moyens de représenter de manière finie, et de manipuler en temps fini, une infinité de données. Les langages réguliers et de leurs multiples représentations sont utilisés pour illustrer un concept.
• le non-déterminisme : ses avantages et ses inconvénients
• différents modèles de calcul avec leurs propriétés, leurs limitations et leurs applications 
• automates à nombre d'états fini
• automates à une pile
• automates de Von Neumann (= graphe de contrôle d'un programme impératif)
• grammaires génératives
• grammaires attribuées

Le cours prend soin de donner des applications concrètes de chacun des concepts

• des utilisations des grammaires : 
• les outils d'analyse lexicale et d'analyse syntaxique,
• l'implantation de traducteurs et de traitement de données au moyen de grammaires attribuées

• des utilisations des automates :
• l'implantation de moniteurs, 
• la modélisation d'interfaces complètes, 
• la réalisation de comportements simples dans un jeu vidéo
• la preuve de correction de programmes impératifs
• opérateurs numériques classiques
• recherche dichotomique d'un élément dans un tableau trié
• multiplication par 2 par décalage d'un bit

Ce cours donne les bases théoriques 

• de la vérification de programmes
• de l'étude des modèles de calculs 

Il met en lumière la démarche de l'informaticien

• le choix d'une représentation de donnée : la représentation finie d'une collection infinie de données
• l'interprétation sémantique de cette représentation
• la définition d'opération de manipulation algorithmique de cette représentation
• les traductions entre représentations équivalentes

CONTENU DU COURS

• Preuve de correction partielle de programmes par la technique de Floyd-Hoare-Dijkstra
• Automates déterministes (ou non), à nombres d'états finis, à pile
• Représentations équivalentes : équations d'Arden, expressions régulières, automates à états finis, grammaires de type 3
• Application et implantation des automates
• Langages réguliers/irréguliers
• Grammaires attibuées, génératives

Le métier Jacquard est un métier à tisser mis au point par le Lyonnais Joseph Marie Jacquard en 1801¹, premier système mécanique programmable avec cartes perforées. Un intermédiaire entre automates et machines de Turing.