La notion d'automate a été introduite pour formaliser le concept d'algorithme et celui de calculabilité. Les automates sont définis sur la base de la machine de Turing [Turing 36]. Ce sont des objets mathématiques. Ils font donc abstraction des capacités des hommes ou des machines. Un résultat sera calculable s'il est atteint en un nombre fini de pas, ce nombre pouvant être aussi grand que l'on veut. Les notions de calculabilité, de décidabilité et de problème démontrable ne seront pas abordées dans ce cours. Nous allons nous intéresser à la structure des automates et à leur utilisation dans le cadre de la théorie des langages.
L'objectif de ce chapitre est d'introduire rapidement les automates à travers la présentation des machines de Turing. Puis, nous étudierons plus particulièrement un cas particulier de machine de Turing : les automates finis.
vendredi, 19/09/03 21:38