-1-INF 421 Luc MarangetAutomatesLuc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-AutomatesTr`es utilis´es en informatique.◮ V´erifications de circuits (quand ce sont des automates !).◮ Recherche efficace dans le texte (moteur de recherche sur leweb, egrep, ...).◮ V´erification des protocoles de communication.◮ Compilation (reconnaissance des mots du langage compil´e).◮ Biologie (motifs dans les s´equences d’ADN).◮ Mod´elisation des calculs possibles (d´ecidabilit´e), Ici lesautomates (finis) d´efinissent la classe de ce qu’il est possible defaire simplement (disons sans ´ecrire dans la m´emoire).-3-Automate finis d´eterministes (DFA)Un DFA est un quintuplet (Σ,Q,δ,q ,F) ou`0◮ Σ est un alphabet;◮ Q est un ensemble fini d’´etats;◮ δ :Q×Σ→Q est la fonction (partielle) de transition;◮ q est l’´etat initial;0◮ F⊆Q est un ensemble d’´etats finaux.-4-Exemple simple de DFAId´ealement, on exprime les automates par des dessins :ab1ba2 3c0bb4q\c a b c0 1 4Ici Q ={0,1,2,3,4}, q = 0, F ={3}, et δ =01 2 2 2...-5-Notation compacteTransitions ´etiquet´ees par des ensembles de caract`eres.1a-cab0 2 3bb4La transition not´ee a-c compte pour trois.-6-Ex´ecution d’un DFA◮ D´emarrer dans l’´etat initial.◮ Lire les caract`eres de l’entr´ee en effectuant les transitions (NB :si blocage, ´echec).`◮ A la fin le mot lu est reconnu si l’´etat courant est final.-7-Exemple (utile ?) de DFACet ...