RESPONSABLE : Michaël Périn

INTERVENANTS : Michaël Périn

INGÉNIEUR POLYTECH'GRENOBLE
  filière INFO
  3ème Année


TITRE DU COURS : Automates et Langages

 . VOLUME :  9 CM d'1h30, 9 TD de 2h00, 3h de TP

 . PAS DE PRÉREQUIS


OBJECTIFS 

 * Le cours présente quelques résultats fondamentaux sur les grandes questions de l'informatique :
  . différents modèles de calculs
  . le non-déterminisme
  . la preuve de correction de programmes 

  Les langages réguliers et de leurs multiples représentations sont
  utilisés pour illustrer un concept important de l'informatique :
  l'utilisation d'une modèle de calcul comme moyens de représenter de
  manière finie et et de manipuler en temps fini, une infinité de
  données.

  Différents modèles de calculs sont présentées :
   . 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 (selon la classification de Chomsky)
   . grammaires attribuées

  avec leurs propriétés, leurs limitations et leurs applications comme
  outils pratiques d'analyse lexicale, d'analyse syntaxique,
  d'implantation de moniteur,  et comme supports de modélisation, de
  raisonnment sur la correction de programme et de vérification de programmes.


 * Le cours prend soin de donner des applications concrètes de chacun des modèles :
   . implantation d'une interface complète (pas d'interaction non spécifiée) au moyen
     d'automate (à pile si nécessaire)
   . implantation de traducteurs et de traitement de données au moyen de grammaires attribuées

 
 * L'étude des modèles de calculs met en lumière la démarche de l'informaticien :

  - le choix d'une représentation de donnée : représentations finies 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 ces représentations
  - les traductions entre représentations équivalentes

 * Ce cours donne les bases nécessaires pour aborder le domaine de la vérification de programmes 

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



BIBLIOGRAPHIE

 LIVRES ET OUVRAGES

  - Introduction à la calculabilité, Pierre Wolper, Inter-Éditions
  

 DOCUMENTS ÉLECTRONIQUES

  - Notes de cours, exercices de TD et annales d'examens sont disponibles sur le site du cours 

     http://www-verimag.imag.fr/~perin/