Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul. Cette théorie est le fondement de plusieurs branches importantes de l'informatique théorique, comme : La calculabilité, par le modèle des machines de Turing ; Les automates finis, et leurs variantes, qui sont utilisés dans l'analyse des langues naturelles, la traduction des programmes par les compilateurs, divers algorithmes de manipulation de textes comme les algorithmes de recherche de sous-chaîne, ou la vérification automatique du fonctionnement de circuits logiques; La théorie de la complexité des algorithmes, visant à classifier les algorithmes en fonction des ressources temporelles et en mémoire nécessaires à leur exécution ; La vérification de modèle qui sert à établir la conformité de programmes à leurs spécifications. Voir par exemple Coq. Les automates n'ont pas d'existence physique, mais sont un modèle abstrait. thumb|Une façon de voir une machine de Turing. Un alphabet est un ensemble quelconque. Ses éléments sont appelés lettres ou symboles. Les lettres n’ont pas de propriétés particulières. On demande seulement de savoir tester si deux lettres sont égales ou différentes. Parmi les exemples d'alphabets, il y a bien sûr l’alphabet latin, et tous les alphabets des langues naturelles. Il y a aussi l’alphabet binaire, composé des symboles 0 et 1, l’alphabet hexadécimal, l’alphabet des acides aminés, etc. En informatique, on rencontre l’alphabet des lexèmes, c’est-à-dire des unités syntaxiques résultant de l’analyse lexicale d’un programme. Un mot ou une chaîne sur un alphabet est une suite finie d'éléments de . On écrit plutôt L'entier est la longueur du mot. Il existe un seul mot de longueur 0, appelé le mot vide, et noté souvent . Le produit de concaténation de deux mots et est le mot obtenu par juxtaposition des deux mots. Le produit de concaténation est associatif, le mot vide est l'élément neutre pour cette opération, ce qui fait de l'ensemble des mots sur l'alphabet un monoïde.