Voir la source de Automate fini

== 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>.