Automates Finis


Ce cours traite des automates "accepteurs", permettant de déterminer si une suite de symboles correspond ou non à un langage donné. Par exemple pour déterminer si une suite de chiffres et opérateurs correspond à une formule arithmétique, si une suite de commandes correspond à un usage normal d'une machine, ...


Le cours débute par une série de définitions et propriétés permettant de caractériser un automate.

Son utilisation pour la reconnaissance, ou acceptation, d'une suite de symbole est ensuite décrite. Différentes méthodes sont présentées, selon que l'automate respecte ou non certaines propriétés (déterministe ou non, complet ou non).


Vient ensuite la description de traitements usuels effectués sur les automates. On s'intéresse à deux types de traitements :

- ceux permettant de modifier un automate tout en acceptant le même langage (par exemple comment transformer un automate afin qu'il soit déterministe) ;

- ceux permettant d'effectuer des modifications simples au langage que l'on souhaite reconnaître (par exemple élimination du mot vide dans le langage reconnu par l'automate, ou construction d'un automate dont les mots reconnus sont formés par la concaténation de mots eux-mêmes reconnus par deux autres automates).


Enfin, la relation entre automate fini et expression rationnelle est abordé. Nous voyons des techniques permettant de passer de l'un à l'autre :

- construction automatique d'un automate fini reconnaissant le langage décrit par une expression rationnelle ;

- identification d'une expression rationnelle correspondant au langage reconnu par un automate.