Théorie des automates - Définition

Introduction

La théorie des automates, intimement liée à l'étude des langages formels, est une branche de l'informatique théorique qui étudie la puissance de calcul de divers modèles d'automates finis.

Vulgarisation

Un automate est une machine prenant en entrée des propositions quelconques comme, par exemple, « (1 + 3) / ( 5 - 1) = 1 » et retournant vrai ou faux, en fonction de ce que l’on attend de la machine ; une évaluation syntaxique ou sémantique. Dans le cas d’une évaluation syntaxique, on désire que la machine évalue si la proposition est correctement formée ou non. Par exemple, « (1 + 3) / ( 5 - 1) = 2 » est correctement formée alors que « ++1 + 3) / )5 - 1) = 2 » ne l’est pas. Dans le cas d’une évaluation sémantique, on désire que la machine évalue la valeur de vérité de la proposition, par exemple : « (1 + 3) / ( 5 - 1) = 2 » est fausse alors que « (1 + 3) / ( 5 - 1) = 1 » est vraie.

L’étude des automates concerne donc l’étude de la syntaxe des langages formels et des langues naturelles ainsi que de la calculabilité, soit l’étude des limites de calcul qu’une machine particulière peut réaliser. L’étude de la syntaxe et celle de la sémantique sont équivalentes ; les limites de reconnaissance syntaxique d’un automate sont équivalentes à sa puissance de calcul et vice-versa. En effet, que l’on utilise un automate pour réaliser de la syntaxe ou de la sémantique est inconnu de la machine, cette distinction est purement artificielle.

En 1937, Alan Turing démontra qu’une sorte particulière d’automate, la machine de Turing, pouvait calculer ce que tout autre automate pouvait calculer et qu’il était impossible de faire mieux. Cette machine était aussi puissante, au niveau du calcul, que tout mathématicien. Il démontra également qu’il existe une sorte particulière de machine de Turing, la machine de Turing universelle, qui peut reproduire le comportement de n’importe quelle autre machine de Turing ; l’ordinateur était né.

La machine de Turing n'est pas l'achèvement de la théorie des automates, mais son commencement. La théorie des automates fut développée pour comprendre comment émergeait la prodigieuse capacité de calcul des machines de Turing. Il fallut attendre 1956 pour que le premier théorème autre que ceux de Turing apparaisse, il s'agit du théorème de Kleene, démontrant l'équivalence entre les graphes de transition, les automates finis et les grammaires régulières. Le théorème de Kleene réalisa pour la première fois l'adéquation d'un automate, considéré comme un accepteur de langage, et d'une grammaire formelle considérée comme un générateur de langage.

Stephen Cole Kleene a étudié une version simplifiée de la machine de Turing pour mieux la comprendre, il a dépouillé la machine de Turing de sa mémoire (son ruban) et trouvé un moyen de décrire ce que fait cette machine simplifiée, soit quel langage elle génère. La méthode de Kleene fut par la suite la principale méthode employée pour l'avancement de la recherche.

Au cours des années suivantes, les chercheurs débordèrent d'imagination pour créer différentes variations de la machine de Turing ; machine à une pile, à deux piles et plus, machine à queues, machine de Post, machines à registres, etc. Ils s'aperçurent rapidement que malgré leurs efforts, la variation n'était qu'une illusion et que tout automate s'inscrivait dans une des quatre catégories qu'ils avaient découvertes. La puissance de calcul des automates pouvait être organisée en une hiérarchie à quatre niveaux, les automates d'une hiérarchie supérieure pouvant calculer tout ce que peut calculer un automate de niveau inférieur.

Ce fait avait pourtant déjà été mentionné par le linguiste Noam Chomsky qui étudiait les grammaires formelles, il avait découvert en 1956 qu'il existait seulement quatre types de grammaires, les grammaires supérieures comprenant l'expressivité des grammaires inférieures. La stricte équivalence de ces quatre grammaires avec les quatre types d'automates fait de Noam Chomsky un des pères fondateurs de l'informatique théorique.