AUTOMATES 

RAPPELS DE COURS

HISTORIQUE

Alan Turing a décrit à 1936 un modèle de « machine idéale » auquel il a laissé son nom. D’autres modèles furent proposés, qui sont tous équivalents à la machine de Turing. Church a démontré dans sa thèse que ces modèles sont les plus généraux possibles. Ces travaux amenèrent à distinguer entre les fonctions qui sont calculables en théorie de celles qui ne le seraient même pas. (Toute fonction calculable peut être calculée par la machine de Turing en temps (nombre d’opérations) fini). Un modèle plus simple mais fort utile est celui d’un automate fini. Un automate fini est une machine abstraite constituée d’états et de transitions. Cette machine est destinée à traiter des mots fournis 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 distincts : il ne dispose donc que d’une mémoire bornée, indépendamment de la taille de la donnée sur laquelle on effectue les calculs. Un automate fini forme un graphe orienté étiqueté, dont les états sont les sommets et les transitions les arcs étiquetés. Les automates finis fournissent un outil de construction d’algorithmes particulièrement simple. Il existe plusieurs types de machines à états finis. Les « accepteurs » produisent en sortie une réponse « oui » ou « non », c’est-à-dire qu’ils acceptent (oui) ou rejettent (non) l’entrée. Les systèmes de reconnaissance classent l’entrée par catégorie. Les capteurs produisent un certain résultat en fonction de l’entrée. Les automates finis peuvent caractériser des langages (c’est-à-dire des ensembles de mots) finis (le cas standard), des langages de mots infinis (automates de Rabin, automates de Büchi), ou encore divers types d’arbres (automates d’arbres). Les machines à états finis se rencontrent également dans les circuits digitaux, où l’entrée, l’état et le résultat sont des vecteurs de bits de taille fixe (machines de Moore et machines de Mealy). Dans les machines de Mealy, les actions (sorties) sont liées aux transitions, tandis que dans les machines de Moore, les actions sont liées aux états. 169 Chapitre 5 • Automates 

QUELQUES DÉFINITIONS

Pour définir un automate fini, on a besoin des éléments suivants : • Un alphabet A qui est un ensemble fini d’objets qu’on appelle « lettres » ou « caractères » mais qui peuvent, selon le cas, être de n’importe quel genre (instructions machine, état civil d’une personne, type d’objet géométrique etc.) • Des mots sont des séquences ordonnées de caractères de l’alphabet. Dans nos applications, on aura affaire qu’à des mots de longueur finie, mais il n’est pas interdit d’utiliser des mots de longueur infinie (automates de Rabin, automates de Büchi). La longueur d’un mot est le nombre de lettres le constituant. Exemple : w = abacda – mot de longueur six sur l’alphabet latin (ou bien sur l’alphabet {a, b, c, d}). • Un mot vide est noté par ´ ou par 1. C’est le seul mot de longueur nulle. • On note A ∗ l’ensemble de tous les mots sur l’alphabet A, y compris le mot vide. • Un automate fini sur l’alphabet A est donné par un quadruplet (Q, I, T , E) où : ® Q est un ensemble fini d’états de l’automate ; ® I ⊂ Q est un ensemble d’états initiaux ; ® T ⊂ Qest un ensemble d’états terminaux ; ® E ⊂ Q ×