Automates et languages - INF 232

INF 232Automates et langagesYassine LakhnechYassine.Lakhnech@imag.frAutomates et Langages Start – p.1/102Bibliographie•J. Hopcroft, R. Motwani, J. Ullman, Introduction to AutomataTheory, Languages and Computation, 2nd edition,Addison-Wesley, 2001•P. Wolper. Introduction à la calculabilité - Paris :InterEditions, 1991.•Cl.Benzaken, Systèmes Formels, Masson, 1991.Automates et Langages Start – p.2/102Auomates d’états finisAutomates et Langages Start – p.3/102Les objectifs de ce cours•Méthodologies et approche scientifique:◦La modélisation mathématiques de problèmesinformatiques.◦La recherche de solutions.◦L’analyse des solutions.◦La présentation des solutions.•Connaissances spécifiques:◦Différents formalismes pour la définition des langagesformelles: automates, expressions régulières etgrammaires.◦Leur étude d’un point de vue algorithmique: problèmesde décision.◦L’étude de leur pouvoir expressif.Automates et Langages Start – p.4/102´ ´L’exemple d’une transaction electroniqueNous voulons modéliser une transaction à laquelle participent:•un client,•un marchand et•une banque.Le client veut acheter une marchandise chez la marchand et lapaye à l’aide d’une monnaie (chèque) éléctronique.Une monnaie éléctronique est tout simplement une sorte dechèque qu’on peut envoyer par email.Automates et Langages Start – p.5/102Les actionsLes actions de ces trois participants sont les suivantes:•Le client peut payer sa marchandise en ...