En informatique théorique, l’utilisation de langages de programmation évolués impose une étape préliminaire sur la reconnaissance de ce langage par la machine. Elle s’effectue grâce à des automates. La théorie des automates développe des automates adaptés aux différents types de langages.
UN AUTOMATE POUR UNE GRAMMAIRE
La théorie des automates est une branche de l’informatique théorique. En théorie des langages, chaque classe de grammaire génère différents types de langages. Il est alors nécessaire de se doter d’un outil qui permette à la machine de reconnaître les langages d’un type de grammaire donné, c’est-à-dire de déterminer si un mot appartient au langage. C’est le rôle des automates. À chaque type de grammaire est alors associé un type d’automate. Les langages réguliers sont reconnus par les automates finis, les langages hors-contexte par des automates à pile et les autres langages par des machines de Turing. Un automate est une procédure effective, c’est-à-dire un algorithme, qui permet de déterminer si un mot donné appartient à un langage. L’automate permet ainsi la compilation d’un programme, la transformation d’un langage source en langage machine. Le rôle de l’automate est donc d’accepter (ou non) les mots du langage qui lui sont proposés et ainsi de reconnaître le langage.
LES AUTOMATES FINIS
Les automates finis sont les plus simples des automates et sont utilisés pour reconnaître des langages réguliers. Ces derniers sont clos par union, intersection, concaténation, complémentaire et par différence ensembliste. Ces conditions très fortes des langages réguliers entraînent que la plupart des langages de programmation ne sont pas réguliers. Un automate fini est défini par un quadruplet dont les éléments sont: un ensemble fini d’états, un sous-ensemble d’états initiaux, un autre d’états finaux et une fonction de transition. L’idée est alors de donner un mot à l’automate, le rôle de ce dernier étant de l’accepter ou de le rejeter. Ainsi, l’automate fini partitionne l’ensemble des mots en deux sous-ensembles, celui des mots acceptés et celui des mots rejetés. Il existe deux types d’automates finis: déterministes et non- déterministes. Dans le premier cas, il ne peut y avoir qu’un état final (plusieurs dans le second) et la fonction de transition devient une simple relation.
LES AUTOMATES À PILE
Les langages réguliers n’étant pas les langages les plus courants, il est nécessaire de construire des automates plus puissants. Dans le cas des grammaires hors-contexte, qui génèrent des langages algébriques, on utilise des automates à pile. Un automate fini ne dispose que d’une mémoire finie, dans la mesure où le nombre de configurations qui peuvent être mémorisées est égal à son nombre d’états. Afin d’étendre les possibilités de mémorisation, on ajoute alors à l’automate fini non-déterministe une pile, c’est-à-dire un dispositif permettant de mémoriser un nombre arbitraire de symboles appartenant à un alphabet fini. Ainsi, la construction d’un automate à pile revient à enrichir la fonction de transition d’un automate fini non-déterministe avec un nouvel alphabet fini qui contient les symboles qui peuvent être empilés et dépilés, des transitions conditionnées par le symbole en haut de la pile et la possibilité d’empiler ou de dépiler un symbole dans la pile lors d’une transition.
LES MACHINES DE TURING
La machine de Turing est le modèle de machine le plus puissant. En effet, tout langage qui ne peut être traité par une machine de Turing ne pourra l’être par aucune autre machine. Elle permet de déterminer si un langage est décidable ou non, la plupart des langages utilisés étant décidables. Si les automates finis ou à pile sont des machines utilisant une mémoire finie, les machines de Turing, elles, utilisent une mémoire plus élaborée, basée sur un ruban « infini » de cases mémoires qu’elles lisent et réécrivent. Une telle machine contient donc une tête de lecture qui se déplace le long du ruban et qui peut réécrire sur une case. Un mot sera accepté (ou refusé) par une machine de Turing si le fonctionnement de la machine à partir de la configuration initiale mène en un nombre fini de transitions à l’état acceptant (ou refusant). On dit alors qu’un langage est décidable s’il existe une machine de Turing qui accepte tous les mots de ce langage et refuse tous les mots qui n’y sont pas.
AUTOMATES CELLULAIRES QUANTIQUES
Appliquer les lois de la mécanique quantique à l’informatique est l’un des grands axes de recherches aujourd’hui. Si la possibilité de construire un ordinateur quantique n’est pas encore avérée, le développement de l’informatique quantique théorique avance très vite. Ainsi, en 1993, un chercheur théorise la fabrication d’un ordinateur quantique sous la forme d’un automate cellulaire quantique. Un automate cellulaire est un ensemble de cellules disposées sur une grille, chaque cellule se trouvant dans un état qui change en fonction de l’état de ses voisins. Ces automates, très utilisés pour modéliser des phénomènes physiques, sont un modèle de calcul au même titre que les machines de Turing. Ce modèle fonctionnerait si l’ordinateur était coupé du reste du monde. Les interactions inévitables avec l’environnement produisent le phénomène de décohérence quantique, entraînant un fonctionnement partiel de l’ordinateur sur un mode classique. Les chercheurs tentent donc de minimiser cet effet.
À RETENIR
En informatique théorique, la théorie des automates est intimement liée à celle des langages formels. Elle a pour objet de développer des méthodes, les automates, capables de reconnaître les langages de programmation. Selon le type de langage à reconnaître, c’est-à-dire accepter ou refuser un mot selon qu’il appartient ou non au langage, on utilisera des automates finis, des automates à pile ou encore des machines de Turing. Le développement théorique de l’informatique quantique s’appuie en partie sur la notion d’automates cellulaires.