Voir la source de Automate fini

{{2autres|les automates finis|une présentation plus formelle|Automate fini non déterministe||Automate}}
{{Voir homonymes|FSM}}
[[Fichier:Hiérarchie d'automates.svg|thumb|upright=1.5|Fig. 1 : Une hiérarchie d'automates.]]

Un '''automate fini''' ou '''automate avec un nombre fini d'états''' (en anglais ''{{Langue|en|finite-state automaton}}'' ou ''{{Langue|en|finite state machine}}'' ou ''FSM'') est un modèle [[Mathématiques|mathématique]] de calcul, utilisé dans de nombreuses circonstances, allant de la conception de [[programme informatique|programmes informatiques]] et de circuits en [[logique séquentielle]] aux applications dans des [[Protocole de communication|protocoles de communication]], en passant par le [[Contrôle de processus|contrôle des processus]], la [[Linguistique informatique|linguistique]] et même la [[biologie]]. Un automate fini est une construction mathématique abstraite, susceptible d'être dans un nombre fini d'''[[État (informatique)|é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 exemple est un [[Distribution automatique|distributeur automatique]] de boissons qui délivre l'article souhaité quand le montant introduit est approprié. D'autres exemples sont les [[ascenseur]]s qui savent combiner les appels successifs pour s'arrêter aux étages intermédiaires, les [[feu de circulation|feux de circulation]] qui savent s'adapter aux voitures en attente, les [[Serrure à combinaison|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 [[Protocole de communication|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 [[Neurologie|systèmes neurologiques]]. En [[linguistique]], ils sont utilisés pour décrire les parties simples de [[grammaire]]s de [[Langage humain|langues naturelles]]. En vérification de programmes (''[[Vérification de modèles|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 pourront. Ceci est principalement dû au fait qu'un automate fini a une [[mémoire (informatique)|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 ===
[[Fichier:Torniqueterevolution.jpg|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]]<ref name="Koshy">{{Ouvrage | langue=en | prénom1=Thomas | nom1=Koshy | titre=Discrete Mathematics With Applications | éditeur=Academic Press | année=2004 | pages=762 | isbn=978-0-12-421180-3 | isbn10=0-12-421180-1 | lire en ligne=https://books.google.com/?id=90KApidK5NwC&pg=PA762&dq=state+machine+turnstile#v=onepage&q=state%20machine%20turnstile&f=false}}.
</ref>{{,}}<ref name="⁇⁇⁇?">{{Lien web 
  | langue = en
  | format = pdf
  | nom = Wright | prénom = David R.
  | titre =  Finite State Machines | série = CSC215 Class Notes
  | éditeur = North Carolina State University| année = 2005
  | url = http://www4.ncsu.edu/~drwrigh3/docs/courses/csc216/fsm-notes.pdf}}.
</ref>.

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é''''' ({{Citation étrangère|langue=en|locked}} en anglais) et '''''déverrouillé''''' ({{Citation étrangère|langue=en|unlocked}} en anglais)<ref name="Koshy" />. 

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é'''''.
[[Fichier:Automate de portillon.svg|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 [[Lexique de la théorie des graphes#S|sommet]] (visualisé par un cercle). Les [[Lexique de la théorie des graphes#A|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'état]]s 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 ===
[[Fichier:ChèvreLoupSalade.jpg|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<ref name="EISI" /> 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, bien entendu, 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''. Bien entendu, 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. Par 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 ===
{{article détaillé| Diagramme états-transitions}}

Plusieurs types de [[Table de transition d'état|tables de transition d'état]] sont utilisées. Ces diagrammes sont très populaires en [[UML (informatique)|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'{{Lien|trad=Virtual finite-state machine|fr=automate fini virtuel}}<ref>Ne pas confondre avec [[machine virtuelle]].</ref>.

:{| class="wikitable"
|+ Table de transitions 
|-
! style="background:linear-gradient(to top right,#f2f2f2 49%,#aaa,#f2f2f2 51%)"|<div style="margin-left:2em;text-align:right;">Entrée</div><div style="margin-right:1em;text-align:left;">État</div> || Entrée X || Entrée Y || Entrée Z
|-
| État A
| … || … || …
|-
| État B
| … || État C || …
|-
| État C
| … || … || …
|}

=== Automates UML ===
[[Fichier:UML state machine Fig5.png|thumb|upright=2|Exemple de diagramme UML de fonctionnement d'un four.]]
Le langage de spécification [[UML (informatique)|Unified Modeling Language]] (UML) a une notation propre pour décrire des automates. Ce sont des [[UML (informatique)#Diagrammes comportementaux|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 (programmation)|agrégation]], tout en étendant la notion d'[[UML (informatique)#Diagrammes d'interaction ou dynamiques|action]]. Les machines finies UML ont à la fois les propriétés des [[Machine de Mealy|machines de Mealy]] et des [[Machine de Moore|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 ===
[[Fichier:SdlStateMachine.png|thumb|upright=1.5|Exemple d'une machine finie en SDL.]]
[[Fichier:Finite state machine example with comments.svg|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)<ref>{{harvsp|id=ITU|texte= UIT : « Z.100 : Langage de description et de spécification »|p=}}.</ref>. 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 [[Type de données|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éactifs]]<ref>Un ''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.</ref>, 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 [[Compilateur|compilation]], en [[Protocole de communication|protocoles de communication]], dans l'étude des modèles de calcul et des [[Langage formel|langages formels]]. Les dictionnaires [[linguistique]]s aussi peuvent être représentés par un automate fini. Le gain de place, pour un dictionnaire de Scrabble anglais, peut atteindre 80 %<ref name="EISI" />, 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''<ref>{{Chapitre |langue=en |prénom1=Robert M. |nom1=Keller |titre ouvrage=Computer Science |sous-titre ouvrage=Abstraction to Implementation |éditeur=Harvey Mudd College |année=2001 |page=480 |isbn= |lire en ligne=http://www.cs.hmc.edu/~keller/cs60book/12%20Finite-State%20Machines.pdf|titre chapitre=Classifiers, Acceptors, Transducers, and Sequencers}}.</ref>{{,}}<ref name="EISI">{{harvsp|id=EISI|texte=Pin, « Automates finis », ''Encyclopédie de l'informatique et des systèmes d'information''|p=}}.</ref>.

=== Accepteurs ou reconnaisseurs ===
[[Fichier:Fsm lisant le mot nice.svg|thumb|upright=1.5|Fig. 4 : Automate accepteur : analyse du mot « nice ».]]
Les '''accepteurs''', également appelés '''reconnaisseurs''' produisent une sortie [[Système binaire|binaire]], indiquant si l'entrée reçue est acceptée ou non. Chaque état d'un tel automate est soit un état d'acceptation, aussi appelé '''final''' ou '''terminal''', ou un état de '''rejet'''. Si l'état courant, après la lecture de la totalité de l'entrée, est un état d'acceptation, l'entrée est acceptée, sinon elle est rejetée. L'entrée est généralement une suite de symboles (des lettres); il n'y a pas d'actions associées. L'exemple de la figure 4 montre un automate fini qui accepte le mot « nice ». Dans cet automate, seul l'état 7 est acceptant.

Une machine peut aussi être décrite comme définissant un [[langage formel]]. Ce langage est composé des mots acceptés par la machine, et d'aucun mot rejeté par elle. Par définition, les langages acceptés par un automate fini sont appelés les langages reconnaissables. Par le [[théorème de Kleene]], ce sont les [[Langage rationnel|langages réguliers]] ou rationnels, décrits par des [[expression régulière|expressions régulières]] ou [[expression rationnelle| rationnelles]].

Le problème de déterminer le langage accepté par un automate fini donné est une instance d'un problème plus général appelé le problème algébrique de cheminement ({{Citation étrangère|langue=en|algebraic path problem}}), qui lui-même est une extension des [[problèmes de cheminement]] dans des graphes dont les arcs portent des poids pris dans un [[demi-anneau]] arbitraire<ref name="PoulyKohlas2012">{{Ouvrage|langue=en|prénom1=Marc|nom1=Pouly|prénom2=Jürg|nom2=Kohlas|titre=Generic Inference|sous-titre=A Unifying Theory for Automated Reasoning|éditeur=John Wiley & Sons|année=2011|pages totales=484|passage=Chapter 6. Valuation Algebras for Path Problems, p. 223 en particulier|isbn=978-1-118-01086-0|présentation en ligne=https://books.google.com/books?id=fbaUmmHzBqwC&printsec=frontcover}}.</ref>{{,}}<ref name="Storer">{{harvsp|Storer|2012|loc=Chapter 10}}.</ref>.

==== État initial ====
L'état initial est en général indiqué en traçant une flèche qui pointe vers cet état « à partir de n'importe où »<ref>{{harvsp|Sipser|2013|p=34}}.</ref>.

==== États d'acceptation, finaux, ou terminaux ====
[[Fichier:DFAexample.svg|thumb|Fig. 5 : Représentation d'un automate fini qui détermine si une suite binaire contient un nombre pair de 0. L'état <math>S_1</math> est final.]]

Un '''état d'acceptation''' (aussi appelé '''état acceptant''', '''final''' ou '''terminal''') est un état dans lequel la machine déclare que la chaîne d'entrée traitée jusqu'alors appartient au langage qu'elle reconnaît. Graphiquement les états d'acceptation sont fréquemment représentés par des cercles doublés. Une autre façon, symétrique à celle adoptée pour l'état initial, consiste à faire sortir une flèche « pointant vers nulle part » d'un tel état<ref name="EISI" />.

L'état initial peut aussi être un état final ; dans ce cas, l'automate accepte la chaîne vide. Si l'état initial n'est pas un état d'acceptation, et s'il n'existe pas d'arc vers un état final, l'automate n'accepte aucun mot.

La figure 5 est l'exemple d'un automate fini déterministe. Cet automate accepte les suites [[Système binaire|binaires]] qui comportent un nombre pair de chiffres 0. L'état ''S''<sub>1</sub> est à la fois l'état initial et l'état terminal. L'automate termine dans l'état ''S''<sub>1</sub> si la chaîne lue contient un nombre pair (éventuellement nul) de 0 : chaque 0 fait basculer d'un état vers l'autre, alors qu'un 1 laisse l'état inchangé. Des exemples de chaînes acceptées sont [[Epsilon|ε]] , le [[mot (mathématiques)|mot vide]], puis 1, 11, 11…, 00, 010, 1010, 10110{{etc.}}


=== Transducteurs ===
[[Fichier:Fsm Moore model door control.svg|thumb|lang=fr|Fig. 6 : Automate transducteur : modèle de Moore.]]
{{article détaillé|Transducteur fini}}

Les [[Transducteur fini|transducteurs finis]] génèrent en sortie des mots en fonction d'un mot d'entrée donné et d'actions associées aux états. Ils sont utilisés par exemple dans des applications de contrôle et dans le domaine de la [[linguistique informatique]]. On distingue deux types de transducteurs, les machines de Moore et les machines de Mealy. Elles diffèrent par les modalités qui déterminent les sorties. On peut démontrer qu'elles ont la même puissance d'expression.

;[[Machine de Moore]]: Dans le modèle de Moore, qui utilise seulement des actions d'entrée, la sortie dépend uniquement de l’état courant. Comparé au modèle de Mealy, le modèle de Moore a l'avantage de la simplicité et de facilité de compréhension. Considérons par exemple une porte d'ascenseur, modélisée par une machine qui reconnaît deux commandes : « ouvrir » et « fermer », commandes qui peuvent être données par un utilisateur. L'action d'entrée (E:) dans l'état d'« en cours d'ouverture » fait démarrer un moteur qui ouvre la porte, et dans l'état « en cours de fermeture » fait démarrer un moteur qui ferme la porte. Les états « ouvert » et « fermé » arrêtent le moteur quand la porte est entièrement ouverte ou entièrement fermée. Ils signalent par ailleurs cette situation vers l’extérieur par « porte ouverte » ou « porte fermée ».

[[Fichier:Fsm mealy model door control.svg|thumb|lang=fr|Fig. 7 : Transducteur : modèle de Mealy.]]
;[[Machine de Mealy]]: Dans le modèle de Mealy, qui utilise également des actions d'entrée, la sortie dépend à la fois de l'entrée et de l'état. L'usage de machines de Mealy réduit souvent le nombre d'états. En contrepartie, le fonctionnement d'un automate est plus complexe et plus difficile à appréhender. La figure 7 montre un automate de Mealy qui a le même comportement que l’automate de Moore. Il y a deux actions d'entrée (I:): « démarrer le moteur pour fermer la porte quand la commande de fermeture arrive », et la commande symétrique pour l'ouverture. Les états intermédiaires « en cours d'ouverture » et « en cours de fermeture » ne sont pas nécessaires.

=== Variantes ===
Les variantes suivantes sont d'un emploi assez rare. Un '''classificateur''' est similaire à un accepteur, mais possède au moins deux états terminaux. Un tel automate peut donc accepter plusieurs langages simultanément, selon la catégorie d'états à laquelle appartient l'état terminal atteint en fin de lecture. Un '''séquenceur''' ou '''générateur''' est un cas particulier d'automate, opérant sur un alphabet d'entrée à une seule lettre. Un tel automate produit une seule séquence qui peut être interprétée comme le résultat d'un transducteur ou d'un classificateur.

Un automate fini avec un état unique est appelé parfois « combinatoire » ; il utilise uniquement des actions d'entrée. Cette notion peut servir lorsque plusieurs automates finis sont censés travailler de concert, en communiquant ; il peut alors être commode de considérer des automates combinatoires comme une brique dans un outil de conception<ref>{{article|langue=en|auteur1=Michael Brutscheck|auteur2=St. Berger|auteur3=M. Franke|auteur4=Andreas Schwarzbacher|auteur5=St. Becker|titre=Structural Division Procedure for Efficient IC Analysis|périodique=''IET Irish'' Signals and Systems Conference (ISSC 2008)|année=2008|lieu=Galway, Irlande|passage=18-23|lire en ligne=http://arrow.dit.ie/engschececon/2/}}.</ref>.

=== Déterminisme ===
Une distinction supplémentaire importante est celle entre automates finis '''déterministes''' et '''non déterministes'''. Dans un automate déterministe, chaque état possède au plus une transition pour chaque symbole d'entrée (et même exactement une dans le cas où l'automate est complet). Dans un automate non déterministe, un symbole d'entrée peut étiqueter une, plusieurs ou aucune transition pour un état donné. Cette distinction est importante en pratique, mais moins en théorie parce qu'il existe un algorithme (la [[construction par sous-ensembles]]) qui permet de transformer un automate fini non déterministe en un automate fini déterministe avec la même fonctionnalité. Toutefois, et c'est là un biais qui peut entraver l'efficacité, l'algorithme de construction par sous-ensembles peut produire un automate dont la taille est exponentielle par rapport à la taille de l'automate de départ. C'est pourquoi certains algorithmes (comme le programme [[grep]] de Unix) tentent des compromis.

== Autres représentations ==

Il existe d'autres moyens de représenter des machines à états. Il existe par exemple des outils de modélisation et de conception de la logique de contrôleurs embarqués. Ils combinent des états hiérarchiques de [[UML (informatique)|UML]], de graphes de flots de contrôle, et des [[Table de vérité|tables de vérité]] en un seul langage, ce qui donne un formalisme différent et un ensemble de sémantiques propre<ref>{{article| langue = en | doi = 10.1145/1086228.1086260| auteur = Grégoire Hamon| année = 2005 | titre =  A Denotational Semantics for Stateflow | journal = International Conference on Embedded Software | pages = 164–172 | lieu = Jersey City, NJ | périodique = ACM }}.</ref>. Ces diagrammes sont similaires aux représentations initialement introduites par David Harel<ref>{{article|langue=en|auteur1=David Harel|lire en ligne=http://www.fceia.unr.edu.ar/asist/harel01.pdf|titre=A Visual Formalism for Complex Systems|périodique=Science of Computer Programming|année=1987|passage=231–274}}.</ref> ; ils supportent des états hiérarchiquement imbriqués, des régions orthogonales au sens de [[UML (informatique)|UML]], des actions sur les états et sur les transitions<ref>{{article|langue=en|auteur1=R. Alur|auteur2=A. Kanade|auteur3=S. Ramesh|auteur4=K. C. Shashidhar|lire en ligne=http://drona.csa.iisc.ernet.in/~kanade/publications/symbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf|titre=Symbolic analysis for improving simulation coverage of Simulink/Stateflow models|périodique=International Conference on Embedded Software|lieu=Atlanta|année=2008|passage=89–98}}.</ref>.

== Modèle mathématique ==
{{article détaillé|Automate fini non déterministe|automate fini déterministe|transducteur fini}}
Les définitions formelles sont les suivantes :

Un '''automate fini déterministe''' <math>\mathcal{A}=(\Sigma, S, s_0, \delta, F)</math> est composé de :
* <math>\Sigma</math>, un [[ensemble fini]], non vide de lettres qui est l’[[alphabet]] d'entrée,
* <math>S</math>, un ensemble fini, non vide d'états, 
* <math>s_0</math>, l'état initial, élément de <math>S</math>. Dans un automate non déterministe, <math>s_0</math> peut être un ensemble d'états.
* <math>\delta</math>, la fonction de transition d'états: <math>\delta: S \times \Sigma \rightarrow S</math> (dans un '''automate non déterministe''', c'est une fonction <math>\delta: S \times \Sigma \rightarrow \mathfrak{P}(S)</math>, donc à valeur dans l'ensemble des parties de <math>S</math>, en d'autres termes <math>\delta</math> retourne un ensemble d'états).
* <math>F</math> est l'ensemble des états terminaux, un sous-ensemble (éventuellement vide) de <math>S</math>.

Pour les automates déterministes ou non, il est fréquent de considérer le cas où <math>\delta</math> est une [[fonction partielle]], donc où <math>\delta(q,a)</math> n'est pas défini pour toute combinaison d'un état <math>q \isin S</math> et d'un symbole <math>a \isin \Sigma</math>. Si <math>\delta(q,a)</math> n'est pas défini, l'automate signale une erreur et l’entrée est rejetée. Cette variante est utile dans la spécification d'une machine, mais certains algorithmes qui nécessitent que les fonctions soient totales, demandent une transformation préliminaire qui, au moyen de l'ajout d'un état supplémentaire, rendent la fonction de transition totale.

Un automate fini est une [[machine de Turing]] très particulière, où la tête ne peut effectuer que des opérations de lecture (et pas d'écriture), et de plus se déplace toujours de la gauche vers la droite (et ne peut donc pas revenir en arrière)<ref>{{Lien web|langue=en
|auteur=Paul E. Black
|date=12 mai 2008
|titre=Finite State Machine
|série=Dictionary of Algorithms and Data Structures
|éditeur=U.S. [[National Institute of Standards and Technology]]
|url=http://www.nist.gov/dads/HTML/finiteStateMachine.html}}.</ref>.

Un '''[[transducteur fini]]''' <math>\mathcal{T}=(\Sigma, \Gamma, S, s_0, \delta, \omega)</math>, est composé de :
* <math>\Sigma</math>, un ensemble fini, non vide de lettres qui est l’[[alphabet]] d'entrée.
* <math>\Gamma</math>, un ensemble fini, non vide de lettres qui est l’[[alphabet]] de sortie.
* <math>S</math>, un ensemble fini, non vide d'états.
* <math>s_0</math>, l'état initial, élément de <math>S</math>. Dans un automate non déterministe, <math>s_0</math> peut être un ensemble d'états.
* <math>\delta</math> est la fonction de transition d'états : <math>\delta: S \times \Sigma \rightarrow S</math>.
* <math>\omega</math> est la fonction de sortie.

Si la fonction de sortie est fonction des états et de l'entrée (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) la définition correspond à celle du [[Machine de Mealy|modèle de Mealy]]; si en revanche la fonction de sortie ne dépend que de l'état, (<math>\omega: S \rightarrow \Gamma</math>), on est en présence du [[Machine de Moore|modèle de Moore]].

Il n'est pas difficile de transformer un automate de Moore en un automate de Mealy en faisant ne dépendre la fonction de sortie que de l’état d'arrivée. La conversion réciproque, d'un automate de Mealy en un automate de Moore, est également possible, mais demande d'introduire des états supplémentaires<ref>{{harvsp|id=Anderson|texte=Anderson, 2006|p=105–108}}.</ref>.

== Optimisation ==
{{Article détaillé|Minimisation d'un automate fini déterministe}}
L'optimisation d'un automate fini signifie ici la recherche d'un automate fini déterministe avec le moins d'états réalisant la même fonction. L'algorithme le plus rapide est l'[[Minimisation d'un automate fini déterministe#Algorithme de Hopcroft|algorithme de Hopcroft]] datant de 1971<ref>{{harvsp|Carton|2008|p=}}.</ref>{{,}}<ref name="BBCF">{{chapitre | langue=en | prénom1=Jean | nom1=Berstel 
 | prénom2=Luc | nom2=Boasson | prénom3=Olivier | nom3=Carton 
 | prénom4=Isabelle | nom4=Fagnot | titre chapitre=Minimization of Automata | arxiv=1010.5318 
 | année=2010 | titre ouvrage=Automata: from Mathematics to Applications
 |éditeur=European Mathematical Society }}.</ref>. D'autres techniques sont l'[[Minimisation d'un automate fini déterministe#Algorithme de Moore|algorithme de Moore]] et un [[Minimisation d'un automate fini déterministe#Algorithme de Brzozowski|algorithme de Brzozowski]]. Les automates finis acycliques, qui reconnaissent des ensembles finis de mots comme des dictionnaires peuvent être minimisés en temps linéaire<ref>{{Article|langue = en| auteur = Dominique Revuz |titre=Minimization of Acyclic automata in Linear Time| périodique= Theoretical Computer Science |volume=92 |date=1992| pages= 181–189 |éditeur= Elsevier |doi=10.1016/0304-3975(92)90142-3}}.</ref>. Des études poussées ont été menées pour la comparaison en moyenne, dans le pire des cas, et pour la [[complexité générique]] de ces méthodes. L'optimisation d'un automate au sens de la recherche d'un automate fini déterministe ou non avec un nombre minimum d'états est plus complexe<ref name="BBCF" />.

== Implémentation ==

=== Applications matérielles ===
[[Fichier:4 bit counter.svg|thumb|Le [[schéma électrique]] pour un compteur [[Transistor-Transistor logic|TTL]] à 4 bits.]]
En [[électronique numérique]], un automate fini peut être construit comme [[circuit logique programmable]], ou un [[automate programmable industriel]], avec des [[Fonction logique|fonctions logiques]] réalisées par [[Bascule (circuit logique)|bascules]] ou [[Relais électromécanique|relais]]. Une implémentation matérielle demande en général un [[Registre de processeur|registre]] pour stocker les variables d'état, un circuit de [[Logique combinatoire (électronique)|logique combinatoire]] qui détermine les transitions d'états, et un deuxième bloc de logique combinatoire qui détermine les sorties de l'automate. Une implémentation courante est le {{Lien|Richards controller}}.

Un cas particulier des automates de Moore, où la sortie est directement connectée aux états, est connu sous le nom d'automate de Medvedev<ref>{{Ouvrage |langue=en |prénom1=Hubert |nom1=Kaeslin |titre=Digital Integrated Circuit Design : From VLSI Architectures to CMOS Fabrication |éditeur=Cambridge University Press |année=2008 |pages totales=845 |page=787 |isbn=978-0-521-88267-5 |lire en ligne=https://books.google.com/?id=gdRStcYgf2oC&pg=PA787&dq=medvedev+fsm#v=onepage&q=medvedev%20fsm&f=false |titre chapitre=Mealy, Moore, Medvedev-type and combinatorial output bits}}.</ref>. Il est par ailleurs recommandé, dans la conception de chipsets, de ne pas placer de circuit logique entre les [[entrées-sorties]] primaires et les registres, afin de minimiser les délais entre [[Chipset|chipsets]] qui sont habituellement longs et ralentissent la fréquence des automates. On peut aussi optimiser les automates en vue de minimiser la consommation d'énergie par des {{Lien|trad=State encoding for low power|langue=en|fr=State encoding for low power|texte=techniques spécifiques}}.

=== Applications logicielles ===
Les concepts suivants sont fréquemment employés dans la construction d'applications utilisant des automates finis :
* {{Lien|trad=Automata-based programming|fr=Programmation fondée sur des automates}}
* {{Lien|trad=Event-driven finite-state machine|langue=en|fr=Automate fini dirigé par événements}}
* {{Lien|trad=Virtual finite-state machine|langue=en|fr=Automate fini virtuel}}
* [[État (patron de conception)]]

=== Automates finis et compilateurs ===
Les automates finis sont souvent utilisés au début du processus de compilation dans les [[compilateur]]s de langages de programmation. Une telle entité peut comporter plusieurs automates finis, qui implémentent l'[[analyse lexicale]].

Partant d'une séquence de caractères, un analyseur lexical construit une suite de lexèmes, tels que les mots réservés, les identificateurs, les littéraux ; à partir de cette suite, l'analyseur syntaxique construit l'arbre syntaxique. L'analyseur lexical et l'analyseur syntaxique gèrent la partie régulière et algébrique de la grammaire d'un langage de programmation<ref>{{harvsp|Aho|Lam|Sethi|Ullman|2007}}.</ref>.

== Articles liés ==
{{début de colonnes|taille=25}}
* [[Automate à jetons]]
* [[Automate à pile]]
* [[Automate à file]]
* [[Automate cheminant]]
* [[Automate d'arbres]]
* {{Lien|langue=en|trad=Communicating finite-state machine|fr=Automates finis communicants}}
* [[Automate fini déterministe]]
* [[Automate fini non déterministe]]
* [[Automate pondéré]] 
* [[Automate quantique]] 
* [[Diagramme états-transitions]]
* [[Discrete Event System Specification]]
* [[État (patron de conception)]]
* [[Intelligence artificielle]] 
* [[Langage rationnel]]
* [[Logique séquentielle]]
* [[Machine à états abstraits]] (ASM)
* [[Machine de Turing]]
* [[Model checking]]
* [[Modèle de Markov caché]]
* [[Réseau de Petri]]
* [[SCXML]]
* [[Specification and Description Language]]
* [[Stratégie de régulation]]
* [[Système de transition d'états]]
* [[Table de décision]]
* [[Théorie des automates]]
* [[UML (informatique)|UML]]
{{fin de colonnes}}

== Notes et références ==
{{Références|taille=25}}

== Bibliographie ==

=== Ouvrages généraux ===

* {{Ouvrage | auteur1=Ferdinand Wagner | auteur2=Ruedi Schmuki | auteur3=Thomas Wagner | auteur4=Peter Wolstenholme | titre=Modeling Software with Finite State Machines | sous-titre=A Practical Approach | éditeur=Auerbach Publications | année=2006 | pages totales=392 | isbn=978-0-8493-8086-0}}.
* {{Ouvrage | auteur1=Christos G. Cassandras | auteur2=Stéphane Lafortune | titre=Introduction to Discrete Event Systems | éditeur=Springer Science & Business Media | année=1999 | pages totales=822 | isbn=978-0-7923-8609-4 | présentation en ligne=https://books.google.com/books?id=IuGo4aRyb00C&printsec=frontcover}}.
* {{Ouvrage | auteur1=Timothy Kam | auteur2=Tiziano Villa | auteur3=Robert K. Brayton | auteur4=Alberto Sangiovanni-Vincentelli | titre=Synthesis of Finite State Machines | sous-titre=Functional Optimization | éditeur=Springer | année=1996 | pages totales=282 | isbn=978-0-7923-9842-4 | présentation en ligne=https://books.google.com/books?id=EckaIiuj2KoC&printsec=frontcover}}
* {{Ouvrage | auteur1=Timothy Kam | auteur2=Tiziano Villa | auteur3=Robert K. Brayton | auteur4=Alberto Sangiovanni-Vincentelli | titre=Synthesis of Finite State Machines | sous-titre=Logic Optimization | éditeur=Springer | année=1997 | pages totales=381 | isbn=978-0-7923-9892-9}}
* {{chapitre|auteur= Yishai A. Feldman |titre chapitre = Finite-state Machines 
 |auteur ouvrage = Allen Kent et James G. Williams  (éditeurs)| titre ouvrage = Encyclopedia of Computer Science and Technology 
 | sous-titre ouvrage = Volume 25 - Supplement 10
 | éditeur = Marcel Dekker | année = 1992 
 | passage = 73-104 | isbn = 0-8247-2275-2 
 | url = https://books.google.com/?id=W2YLBIdeLIEC&printsec=frontcover&dq=%22finite+state+machine%22#v=onepage&q=%22finite%20state%20machine%22&f=false 
 | id=ECST}}
* {{chapitre|auteur= Jean-Éric Pin |titre chapitre = Automates finis 
|auteurs ouvrage =Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs)
|titre ouvrage =Encyclopédie de l'informatique et des systèmes d'information
|éditeur=Vuibert|lieu=Paris|année=2006|pages totales=xxxv+1941 |passage=966-976|isbn=978-2-7117-4846-4|id=EISI}}.
* {{Ouvrage | auteur1=James A. Storer | titre=An Introduction to Data Structures and Algorithms | éditeur=Springer Science & Business Media | année=2012 | pages totales=599 | isbn=978-1-4612-0075-8 | isbn2=146120075X | présentation en ligne=https://books.google.com/books?id=K4vfBwAAQBAJ&printsec=frontcover}}
* {{Compilateurs (Aho, Lam, Sethi, Ullman) 2e édition}}

=== Aspects pratiques ===
* {{Lien web |url= https://www.itu.int/rec/T-REC-Z.100/fr
|titre= Z.100 : Langage de description et de spécification - Présentation générale de SDL-2010
|éditeur= Union internationale des télécommunications
|en ligne le= {{1er}} septembre 2015
|id= ITU
}}.
* {{Ouvrage | auteur1=Miro Samek | titre=Practical Statecharts in C/C++ | sous-titre=Quantum Programming for Embedded Systems | éditeur=CRC Press | année=2002 | pages totales=416 | isbn=978-1-57820-110-5 | lire en ligne=http://www.state-machine.com/psicc/index.php}}.
* {{Ouvrage | langue=en | auteur1=Miro Samek | titre=Practical UML Statecharts in C/C++ | sous-titre=Event-Driven Programming for Embedded Systems | éditeur=Newnes | lieu=Amsterdam | année=2009 | pages totales=712 | isbn=978-0-7506-8706-5 | lire en ligne=http://www.state-machine.com/psicc2/index.ph}}.
* {{Ouvrage | auteur1=Susan H. Rodger | auteur2=Thomas W. Finley | titre=JFLAP | sous-titre=An Interactive Formal Languages and Automata Package | éditeur=Jones & Bartlett Learning | année=2006 | pages totales=192 | isbn=978-0-7637-3834-1 | présentation en ligne=https://books.google.com/books?id=494hTkZ_gu4C&printsec=frontcover}}.
* [[Gérard Berry]] [http://www.college-de-france.fr/site/gerard-berry/course-2015-03-25-16h00.htm ''La vérification de modèles (model checking)''], Leçon du [[Collège de France]] du 25 mars 2015.

=== Automates en informatique théorique ===
<!-- Français-->
<!-- Carton -->
* {{Langages formels, calculabilité et complexité}}
<!-- Perifel -->
* {{Complexité algorithmique (Perifel)}} — (La version électronique est datée de juillet 2015.)
<!-- Sakarovitch -->
* {{Ouvrage | langue=fr | prénom1=Jacques | nom1=Sakarovitch | titre=Éléments de théorie des automates | éditeur=Vuibert | lieu=Paris | année=2003 | pages totales=816 | isbn=978-2-7117-4807-5 | isbn10=2-7117-4807-3 | zbl=1188.68177}}
<!-- Gérard Berry -->
* {{Ouvrage | langue=fr | auteur1=Gérard Berry | titre=L’informatique du temps et des événements | sous-titre=Leçon inaugurale prononcée le jeudi 28 mars 2013 | éditeur=Collège de France | année=2013 | pages totales=88 | isbn=978-2-7226-0277-9}} 
<!-- Par ordre alphabétique-->
<!-- Anderson -->
* {{Ouvrage | id=Anderson | auteur1=James A. Anderson | auteur2=Thomas J. Head | titre=Automata Theory with Modern Applications | éditeur=Cambridge University Press | année=2006 | pages totales=264 | isbn=978-0-521-84887-9 | isbn2=0521848873}}.
<!-- Boolos Burgess Jeffrey-->
* {{Ouvrage | auteur1=George S. Boolos | auteur2=John P. Burgess | auteur3=Richard C. Jeffrey | titre=Computability and Logic | éditeur=Cambridge University Press | lieu=Cambridge | année=2007 | numéro d'édition=5 | année première édition=1989 | pages totales=366 | isbn=978-0-521-70146-4}}.
<!-- Davis Sigal Weyuker -->
* {{Ouvrage | auteur1=Martin Davis | auteur2=Ron Sigal | auteur3=Elaine J. Weyuker | titre=Computability, Complexity, and Languages | sous-titre=Fundamentals of Theoretical Computer Science | éditeur=Academic Press | lieu=San Diego | année=1994 | numéro d'édition=2 | pages totales=609 | isbn=978-0-12-206382-4 | présentation en ligne=https://books.google.com/books?id=6G_arEqHtysC&printsec=frontcover}}.
<!-- Hopcroft UM -->
* {{Introduction to Automata Theory, Languages, and Computation}}
<!-- Lewis Papadimitriou -->
* {{Ouvrage |auteur1=Harry R. Lewis |auteur2=Christos H. Papadimitriou |titre=Elements of the Theory of Computation |éditeur=Prentice Hall |année=1998 |numéro d'édition=2 |pages totales=361 |isbn=978-0-13-262478-7}}.
<!-- Linz -->
* {{Ouvrage | auteur1=Peter Linz | titre=An Introduction to Formal Languages and Automata | éditeur=Jones & Bartlett Publishers | lieu=Sudbury, MA | année=2011 | numéro d'édition=5 | pages totales=437 | isbn=978-1-4496-1552-9 | présentation en ligne=https://books.google.com/books?id=hsxDiWvVdBcC&printsec=frontcover}}.
<!-- Arora Barak -->
* {{Ouvrage | auteur1=Sanjeev Arora | auteur2=Boaz Barak | titre=Computational Complexity | sous-titre=A Modern Approach | éditeur=Cambridge University Press | année=2009 | pages totales=579 | isbn=978-0-521-42426-4 | présentation en ligne=https://books.google.com/books?id=8Wjqvsoo48MC&printsec=frontcover}}.
<!-- Pippenger -->
* {{Ouvrage | auteur1=Nicholas Pippenger | titre=Theories of Computability | éditeur=Cambridge University Press | lieu=Cambridge | année=2010 | pages totales=264 | isbn=978-0-521-15343-0}}
<!-- Sipser -->
* {{Ouvrage | auteur1=Michael Sipser | titre=Introduction to the theory of computation | éditeur=Cengage Learning | lieu=Boston, MA | année=2013 | numéro d'édition=3 | pages totales=480 | isbn=978-1-133-18779-0 | oclc=761858892 | présentation en ligne=https://books.google.com/books?id=P3f6CAAAQBAJ&printsec=frontcover}}.
==== Articles récents ====
* {{Article |prénom1=Sankardeep |nom1=Chakraborty |prénom2=Roberto |nom2=Grossi |prénom3=Kunihiko |nom3=Sadakane |prénom4=Srinivasa Rao |nom4=Satti 
|titre=Succinct representation for (non)deterministic finite automata 
|périodique=Journal of Computer and System Sciences |volume=131 |date=2023-02-01 
|doi=10.1016/j.jcss.2022.07.002 
|lire en ligne=https://www.sciencedirect.com/science/article/pii/S0022000022000526 |pages=1–12}}
* {{Article |prénom1=Jason |nom1=Bell |prénom2=Daniel |nom2=Smertnig 
|titre=Noncommutative rational Pólya series 
|périodique=Selecta Mathematica |volume=27 |numéro=3 |date=2021-05-19 
|doi=10.1007/s00029-021-00629-2 |arxiv=1906.07271 |numéro article = 34 (34 pages)}}
* {{Article 
|prénom1=Sylvain |nom1=Lombardy 
|prénom2=Jacques |nom2=Sakarovitch 
|titre=The net automaton of a rational expression 
|périodique=LATIN 2022: Theoretical Informatics 
|éditeur=Lecture Notes in Computer Science vol. 13568, Springer 
|date=2022 |isbn=978-3-031-20624-5 
|doi=10.1007/978-3-031-20624-5_23 
|pages=376–392}}

=== Machines abstraites en informatique théorique ===
* {{Article|prénom=Yuri |nom=Gurevich |titre=Sequential Abstract State Machines Capture Sequential Algorithms |journal=[[ACM Transactions on Computational Logic]]| volume= 1| numéro=1 |date=juillet 2000 |pages= 77–111 |url=http://research.microsoft.com/~gurevich/Opera/141.pdf |doi=10.1145/343369.343384}}
* {{article
 |nom1=Goncharov|prénom1=Sergey 
 |auteur2=Stefan Milius
 |auteur3=[[Alexandra Silva]]
 |titre=Toward a Uniform Theory of Effectful State Machines
 |journal=ACM Transactions on Computational Logic
 |volume=21|numéro=3|année=2020|numéro article =23 (63 p.)
 |issn=1529-3785|doi=10.1145/3372880}}.

=== [[Apprentissage automatique]] ===
* {{Ouvrage| auteur1=Trevor Hastie| auteur2=Robert Tibshirani| auteur3=Jerome Friedman| titre=The elements of statistical learning| sous-titre=data mining, inference, and prediction| éditeur=Springer| lieu=New York| année=2009| numéro d'édition=2| pages totales=xxii+745| isbn=978-0-387-84857-0}}
* {{CornuéjolsMiclet}}
* {{MacKay}}
* {{Mitchell}}
* {{Bishop06}}

== Liens externes ==
{{Autres projets|commons = Category:Finite state machine}}
* [https://web.archive.org/web/20130203032845/http://blog.manuvra.com/modeling-a-simple-ai-behavior-using-a-finite-state-machine/ ''Modeling a Simple AI behavior using a Finite State Machine''] Exemple d'emploi dans les jeux vidéo
* [http://www.nist.gov/dads/HTML/finiteStateMachine.html NIST Dictionary of Algorithms and Data Structures] Description of Finite State Machines
* [http://teahlab.com/Moore_Finite_State_Machine_Control_Circuit/ Interactive FSM: Control Circuit], Démonstration de flot logique dans les automates finis.
* [http://ivanzuzak.info/noam/webapps/fsm_simulator/#tab2 FSM simulator], Simulation de DFA, NFA et ε-NFA, y compris engendré par des expressions rationnelles.
{{liens}}
{{Palette|Automates finis et langages réguliers|Informatique théorique}}
{{Portail|Informatique théorique}}

[[Catégorie:Théorie des automates]]
[[Catégorie:Calculabilité]]
[[Catégorie:Méthode formelle]]
[[Catégorie:Automates finis et langages réguliers]]