Théorie des automates

Pour les articles homonymes, voir Théorie et Automate.

En informatique théorique, la théorie des automates est l'étude de machines abstraites définissant un modèle de calcul^{[H 1]}. Cette théorie est le fondement de branches très importantes de l'informatique théorique^{[H 2]}, comme :

Les automates finis, qui sont utilisés dans des classes très importantes de logiciels comme les compilateurs, 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 théorie de la démonstration avec le concept de preuve formelle.

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 calculs. Dans la théorie, ces automates n'ont pas d'existence physique, même si certains auteurs ont proposé la construction de machines de Turing pneumatiques (Marcel-Paul Schützenberger par exemple).

Sommaire

1 Concepts fondamentaux de la théorie des automates
2 Vulgarisation^[1]^, ^[2]^, ^[3] ^,^[4] ^,^[5]
3 Articles connexes
- 3.1 Sources
4 Références

Concepts fondamentaux de la théorie des automates

L'alphabet

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 syntaxique résultant de l’analyse lexicale d'un programme.

Les mots ou chaînes

Un mot ou un chaîne sur un alphabet $A$ est une suite finie

$w=(a_1,\ldots,a_n)$

d'éléments de $A$ . On écrit plutôt

$w=a_1\cdots a_n$

L'entier $n$ 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

$x=a_1\cdots a_n$ et $y=b_1\cdots b_m$

est le mot

$xy=a_1\cdots a_nb_1\cdots b_m$

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 $A$ un monoïde. Ce monoïde est libre, et est noté $A *$ .

Le langage

Un langage formel sur un alphabet $A$ est un ensemble de mots sur $A$ , donc un sous-ensemble de $A *$ . Les opérations ensemblistes (union, intersection, complément) s'étendent bien entendu aux langages. Le produit de concaténation des mots s'étend aux langages de la manière suivante. Si $X$ et $Y$ sont deux langages sur $A$ , leur produit est le langage

$XY=\{xy\mid x\in X, y \in Y\}.$

Une autre opération est l'étoile de Kleene. Pour une partie $X$ de $A *$ , elle est notée $X *$ et est définie par

$X^*=\{x_1x_2\cdots x_n\mid n\ge0,x_i\in X\}.$

Le problème

En théorie des automates, un problème est la question de savoir si un chaine appartient ou non à un langage.

Il s'avère que la notion générale de "problème" peut être exprimée sous forme de "langage" dans la théorie des automates^{[H 3]}. Par exemple, le problème de connaitre la primalité d'un nombre N peut se traduire dans le langage de l'ensemble de toutes les chaines de chiffres binaires qui représentent un nombre premier : le problème du test de primalité consiste alors à savoir si un nombre (une chaine de caractères binaires) appartient à ce langage ou non.

Vulgarisation^[1]^, ^[2]^, ^[3] ^,^[4] ^,^[5]

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.

Références

↑ COHEN D.I.A.: Introduction to Computer Theory. John Wiley & Sons, 1997
↑ HARRISON M.A.: Introduction to Formal Language Theory. Addison-Wesley, 1978
↑ HOPCROFT J.E., ULLMAN J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979
↑ RAYWARD-SMITH V.J.: A First Course in Computability. McGraw-Hill Book Company, London 1986
↑ MARTIN J.C.: Introduction to Languages and the Theory of Computation. Second Edition, McGraw-Hill Int., 1997

Portail de l’informatique

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie des automates de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Theorie des automates — Théorie des automates Pour les articles homonymes, voir Théorie et Automate. 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 … Wikipédia en Français
théorie des automates — automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f … Automatikos terminų žodynas
Theorie des automates finis — Théorie des automates finis Sommaire 1 Langages formels 1.1 Alphabet 1.2 Mot 2 Définitions 2.1 Automate fini … Wikipédia en Français
Théorie des automates finis — Article principal : Automate fini. Cet article décrit la théorie des automates finis, cas particulier de la théorie des automates. Sommaire 1 Langages formels 1.1 Alphabet 1.2 Mot … Wikipédia en Français
Théorie des expressions rationnelles — Langage rationnel Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les… … Wikipédia en Français
Théorie des langages et automates — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… … Wikipédia en Français
Theorie des langages — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… … Wikipédia en Français
Théorie des langages — En informatique, la théorie des langages a pour objectif de décrire les langages formels, vus comme moyen de communication, d un point de vue mathématique. Un langage formel[1] est un ensemble de mots. Un mot est une suite finie de symboles. L… … Wikipédia en Français
Automates cellulaires — Automate cellulaire À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe !) de l… … Wikipédia en Français
Theorie de la complexite — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Théorie des automates

Sommaire