thumb|upright=1.5|Fig. 1 : Une hiérarchie d'automates.
Un automate fini ou automate avec un nombre fini d'états (en anglais ou ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie. Un automate fini est une construction mathématique abstraite, susceptible d'être dans un nombre fini détats, mais étant à un moment donné dans un seul état à la fois ; l'état dans lequel il se trouve alors est appelé l'« état courant ». Le passage d'un état à un autre est activé par un événement ou une condition ; ce passage est appelé une « transition ». Un automate particulier est défini par l'ensemble de ses états et l'ensemble de ses transitions.
On rencontre couramment des automates finis dans de nombreux appareils qui réalisent des actions déterminées en fonction des événements qui se présentent. Un premier exemple est le distributeur automatique de boissons qui délivre l'article souhaité quand le montant introduit est approprié. D'autres exemples sont les ascenseurs qui savent combiner les appels successifs pour s'arrêter aux étages intermédiaires, les feux de circulation qui savent s'adapter aux voitures en attente, les digicodes qui analysent la bonne suite de chiffres.
Les automates finis peuvent modéliser un grand nombre de problèmes, parmi lesquels la conception assistée par ordinateur pour l'électronique, la conception de protocoles de communication, l'analyse syntaxique de langages. Dans la recherche en biologie et en intelligence artificielle, les automates finis ou des hiérarchies de telles machines ont été employés pour décrire des systèmes neurologiques. En linguistique, ils sont utilisés pour décrire les parties simples de grammaires de langues naturelles. En vérification de programmes (model checking), des automates finis, avec parfois un nombre très important d'états (des milliards), sont employés.
Vus comme un modèle de calcul, les automates finis ont un potentiel faible ; ils ont bien moins de puissance de calcul qu'une machine de Turing. En d'autres termes, il y a des tâches qu'un automate fini ne peut pas accomplir alors qu'un automate à pile ou une machine de Turing le peuvent. Ceci est principalement dû au fait qu'un automate fini a une mémoire limitée à son nombre d'états.
L'étude des automates finis est une branche de la théorie des automates.
Exemples
Un premier exemple : un portillon thumb|upright=0.5|left|Un portillon. Un exemple très simple d'un mécanisme que l'on peut modéliser par un automate fini est un portillon d'accès...
Un portillon, utilisé dans certains métros ou dans d'autres établissements à accès contrôlés, est une barrière avec trois bras rotatifs à hauteur de la taille. Au début, les bras sont verrouillés, bloquent l'entrée et empêchent les usagers de passer. L'introduction d'une pièce de monnaie ou d'un jeton dans une fente du portillon (ou la présentation d'un ticket ou d'une carte) débloque les bras et permet le passage d'un et un seul usager à la fois. Une fois l'usager entré, les bras sont à nouveau bloqués jusqu'à ce qu'un nouveau jeton soit inséré.
Un portillon, vu comme un automate fini, a deux états : verrouillé ( en anglais) et déverrouillé ( en anglais).
Deux « entrées » peuvent modifier l'état : la première si l'on insère un jeton dans la fente (entrée jeton) et la deuxième si l'on pousse le bras (entrée pousser). Dans l'état verrouillé, l'action de pousser n'a aucun effet : quel que soit le nombre de fois que l'on pousse, l'automate reste verrouillé. Si l'on insère un jeton, c'est-à-dire si l'on effectue une « entrée » jeton, on passe de l'état verrouillé à l'état déverrouillé. Dans l'état déverrouillé, ajouter des jetons supplémentaires n'a pas d'effet, et ne change pas l'état. Mais dès qu'un usager tourne le bras du portillon, donc fournit un pousser, la machine retourne à l'état verrouillé. thumb|center|upright=2|Fig. 2 : Diagramme d'état d'un portillon. On peut représenter l'automate par un graphe orienté, appelé un diagramme états-transitions, comme donné ci-dessus. Chaque état est représenté par un sommet (visualisé par un cercle). Les arcs (représentés par des flèches) montrent les transitions d'un état à un autre. Chaque flèche porte une entrée qui déclenche la transition. Les données qui ne provoquent pas de changement d'état, comme un jeton pour l'état déverrouillé, sont représentées par des arcs circulaires (des boucles) qui tournent autour de l’état. La flèche qui entre dans l'état verrouillé'' depuis le point noir sert à indiquer que cet état est l'état initial, au début de la modélisation. {| class="wikitable" ! État courant ! Entrée ! État suivant ! Sortie |- | rowspan="2"|verrouillé | jeton || déverrouillé || Déverrouille le portillon pour qu'un usager puisse passer |- | pousser || verrouillé || Rien |- | rowspan="2"|déverrouillé | jeton || déverrouillé || Rien |- | pousser || verrouillé || Quand l'usager est passé, verrouille le portillon |} L'automate d'un portillon peut être représenté par une table de transition d'états qui montre, pour chaque état, le nouvel état et la sortie (l'action) pour une entrée donnée. Un autre exemple : le loup, la chèvre et le chou thumb|upright=1.5|Le loup, la chèvre et le chou. Chaque état représente ce que le passeur a déjà transporté (le chou est noté « S »). L'exemple que voici illustre les possibilités qui s'offrent à un passeur qui doit faire traverser, d'une rive à l'autre, un loup, une chèvre et un chou (c'est une variante des nombreux problèmes de passage de rivière). Sa barque ne lui permet que d'emporter un seul des trois objets à la fois et il ne peut laisser ensemble loup et chèvre ni chèvre et chou. Dans le diagramme ci-contre, un état représente ce que le passeur a déjà pu transporter sur l’autre rive (« P » représente le passeur, « L » le loup, « C » la chèvre, et le chou a été noté par « S ») : au début rien, à la fin tout. Sur les flèches, les objets transportés (et lui-même). Une des deux séquences de transport est CPLCSPC, l'autre est CPSCLPC. On néglige les aller-retour-aller inutiles.
Concepts et terminologie Un état est la description de la configuration d'un système en attente d'exécuter une transition. Une transition est un ensemble d'actions à exécuter lorsqu'une condition est remplie ou lorsqu'un événement est reçu.
Exemple : une chaîne audio peut être dans un état « radio » et, quand elle reçoit un stimulus du genre « suivant », passe à la station radio suivante. Si le système est dans l'état « CD » et reçoit le stimulus « suivant », il passe à la piste suivante du CD en cours. Les mêmes stimuli peuvent donc déclencher des actions différentes, si l'état courant n'est pas le même.
Dans certaines représentations de machines finies, il est possible d'associer des actions à un état : action d'entrée : réalisée lorsque l'on « entre » dans l'état ; action de sortie : réalisée lorsque l’on « quitte » l'état ; action de transition : réalisée lors d'une transition
Représentations
Table états-transitions
Plusieurs types de tables de transition d'état sont utilisées. Ces diagrammes sont très populaires en UML notamment. La représentation la plus courante est illustrée ci-dessous ; la combinaison de l'état courant (par exemple B) et d'une entrée (par exemple Y) montre l'état suivant (dans l’exemple C). L'information complète associée à une action n'est pas décrite dans la table et peut être ajoutée par des annotations. Une définition d'une machine finie avec actions est possible au moyen de tables de transition dans le modèle plus élaboré d'Ne pas confondre avec machine virtuelle..
{| class="wikitable" |+ Table de transitions |- ! style="background:linear-gradient(to top right,#f2f2f2 49%,#aaa,#f2f2f2 51%)"|EntréeÉtat || Entrée X || Entrée Y || Entrée Z |- | État A | … || … || … |- | État B | … || État C || … |- | État C | … || … || …
Automates UML thumb|upright=2|Exemple de diagramme UML de fonctionnement d'un four. Le langage de spécification Unified Modeling Language (UML) a une notation propre pour décrire des automates. Ce sont des diagrammes comportementaux particuliers qui permettent de dépasser les limitations de machines finies traditionnelles tout en conservant leurs avantages principaux. Les machines ou automates UML introduisent les notions nouvelles de diagramme de structure composite, d'états hiérarchiques et d'agrégation, tout en étendant la notion d'action. Les machines finies UML ont à la fois les propriétés des machines de Mealy et des machines de Moore décrites plus bas. Elles supportent des actions qui dépendent à la fois de l'état du système et de l'événement déclenchant, comme dans les machines de Mealy, et aussi des actions d'entrée et de sortie associées à des états, comme dans les machines de Moore.
Machines SDL thumb|upright=1.5|Exemple d'une machine finie en SDL. lang=fr|thumb|Fig. 3 : Exemple d'un automate fini à deux états. Le langage de spécification et de description appelé Specification and Description Language ou SDL est une norme élaborée par l'Union internationale des télécommunications (UIT).. La norme contient un ensemble de symboles graphiques permettant de décrire les actions dans une transition : envoi d'un message ; réception d'un message ; démarrage d'un temporisateur (timer) ; arrêt d'un temporisateur ; lancement d'une machine concurrente ; prise de décision. Un SDL contient des types de base, mais surtout des types de données abstraits (TDA) et une syntaxe de manipulation qui permet de décrire le système de manière formelle, possiblement de manière complète et non ambiguë.
Autres diagrammes d'états Il existe de nombreuses variantes de diagrammes d'états-transitions, comme le diagramme d'un automate à deux états donné plus haut.
Utilisation Les automates sont des systèmes réactifsUn système réactif est un système qui est en interaction permanente avec son environnement, et dont le rythme est imposé par cet environnement., réagissant aux impulsions reçues. Ils jouent un rôle important dans de nombreux champs différents, comprenant l'électrotechnique, la linguistique, l'informatique , la philosophie, la biologie, les mathématiques, et la logique. Les automates finis constituent une classe d'automates étudiée en théorie des automates et en informatique théorique.
En informatique, les automates finis sont largement utilisés en modélisation du comportement d'applications, en conception matérielle, en électronique numérique, en génie logiciel, en compilation, en protocoles de communication, dans l'étude des modèles de calcul et des langages formels. Les dictionnaires linguistiques aussi peuvent être représentés par un automate fini. Le gain de place, pour un dictionnaire de Scrabble anglais, peut atteindre 80 %, et encore plus pour des dictionnaires de mots fléchés du français.
Classification Les automates finis peuvent être classés principalement en deux catégories, les accepteurs et les transducteurs. Les accepteurs analysent la structure de la donnée fournie, et l'acceptent si elle est conforme à la spécification décrite par l'automate. Les transducteurs au contraire traduisent une chaîne de symboles en une autre, là encore selon l'algorithme codé dans l'automate. Dans certains cas, on peut rencontrer des variantes appelées classificateurs et séquenceurs...
Accepteurs ou reconnaisseurs thumb|upright=1.5|Fig. 4 : Automate accepteur : analyse du mot « nice ».