Automate fini

Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit aussi parfois machine à états finis au lieu de machine avec un nombre fini d'états), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé comme ici, soit marqué d'une flèche sortante.

→