Contributions à l’étude de la dérivation des expressions rationnelles et à l’étude des systèmes de numération abstraits

Les travaux présentés dans ce mémoire s’inscrivent dans la théorie des automates et des langages formels. Dans cette théorie, un alphabet est un ensemble fini de lettres et les mots sont toutes les concaténations successives différentes de lettres de l’alphabet. Les langages sont des ensembles, finis ou infinis de mots. La théorie des automates permet de manipuler ces mots et ces langages.

Ce mémoire peut se diviser en deux parties et donne également deux visions différentes de la manière dont la théorie des automates permet de manipuler les langages. Dans une première partie les automates sont vus comme un moyen de représenter les langages rationnels. La problématique abordée est alors celle de naviguer entre deux modèles, les automates finis et les expressions rationnelles, représentant le même langage. Dans la deuxième partie, nous traitons de problèmes de la théorie des automates issus de la considération des systèmes de numération. Ces systèmes permettent de représenter des ensembles dénombrables par un langage infini. Il s’agit alors d’utiliser les automates, dans leur généralité, afin de manipuler des entiers et en particulier d’être capable de ‘compter‘ sur un langage représentant les entiers.

D’un coté donc, les automates, dans leur forme la plus simple, sont des machines finies à travers lesquelles des mots peuvent être lus. Si la lecture d’un de ces mots permet d’atteindre un état d’acceptation de la machine, alors on dit que ce mot est reconnu par l’automate. Les automates, finis, peuvent ainsi permettre de reconnaître les mots de langages qui peuvent être infinis. De tels langages sont appelés des langages reconnaissables. Pour chaque langage reconnaissable, il est possible de construire différents automates qui reconnaissent ce langage. En particulier, il est possible d’avoir des automates dits déterministes, c’est-à-dire pour lequel la lecture d’un mot se fait de manière linéaire : il suffit de suivre les lettres consécutives du mot sur un graphe sans autre choix.

De l’autre coté, il est possible de créer des langages en appliquant des successions d’opérations sur les langages. Ces opérations sont l’union de deux langages, le concaténation membres à membres de deux langages et l’étoile d’un langage, c’est-à-dire l’union pour tout entier n des concaténations n fois de ce langage. Ces opérations sont appelées opérations rationnelles. Si l’on prend l’ensemble le plus petit fermé pour ces opérations rationnelles et contenant les langages composés uniquement des lettres de l’alphabet, on obtient une classe de langages appelés langages rationnels. Comme ces langages sont obtenus par une succession d’opérations à partir d’atomes, il est possible des les représenter de manière finie par une formule bien parenthésée représentant ces opérations. Une telle formule est appelée expression rationnelle .

Le théorème fondamental de la théorie des automates, énoncé par Kleene, stipule qu’un langage sur un alphabet est rationnel si, et seulement si, il est reconnaissable par un automate fini sur le même alphabet. Autrement dit, les langages rationnels et les langages reconnaissables sont les mêmes. Cela signifie que les automates finis et les expressions rationnelles représentent les mêmes objets : les langages rationnels. Dès lors le problème du passage d’un modèle à un autre est un problème qui a fait l’objet de beaucoup d’intérêt.

Dans un premier sens, les algorithmes les plus classiques pour calculer une expression rationnelle à partir d’un automate fini – en conservant le langage qu’ils représentent – sont les algorithmes de ‘McNaughton et Yamada‘ [34] et d’élimination d’états (cf.[49] et [50] par exemple). Ces deux algorithmes, bien que différents, produisent des résultats similaires. En particulier les deux algorithmes dépendent d’un ordre sur les états et un choix d’ordre différent peut produire des expressions très différentes dans la forme et dans la taille. Un même automate peut donc produire différentes expressions rationnelles. Une autre méthode pour produire des expressions rationnelles est la résolution de systèmes d’équations en utilisant le lemme d’Arden (cf. [43, p107–108]).

Dans le deuxième sens, il existe beaucoup plus d’algorithmes pour obtenir un automate fini à partir d’une expression rationnelle. Ces algorithmes peuvent même fournir des automates différents les uns des autres. On peut en particulier évoquer l’automate de Thompson qui est un automate construit à partir de l’expression avec des successions de constructions ‘de base‘ qui correspondent aux opérations rationnelles de l’expression. Cependant cet automate n’en est pas un au sens classique du terme car il possède des transitions spontanées c’est-à-dire étiquetées par le mot vide et non une lettre de l’alphabet. Dans les algorithmes notables, l’algorithme le plus répandu est celui de Glushkov [26] qui construit un automate, dit des positions dont la taille est celle de l’expression, c’est-à-dire qu’il y a – en plus de l’état qui ne sert que d’état initial – autant d’états que d’occurrences de lettres dans l’expression rationnelle. Cela fait que cet automate semble très proche dans les informations qu’il contient de l’expression rationnelle elle-même. L’automate des positions a également cela de particulier qu’il est possible de le calculer de plusieurs manières, a priori différentes. En effet, si la méthode de [26] construit l’automate des positions en calculant les ensembles de lettres qui peuvent suivre une lettre donnée – à partir de l’expression rationnelle –, il existe un algorithme qui le construit avec une construction un peu comme pour l’automate de Thompson : des constructions de base permettent de réaliser la somme et la concaténation de deux automates standards ainsi que l’étoile standard d’un automate standard – c’est à dire avec un unique état initial qui n’est pas accessible à partir du reste de l’automate –, pour construire l’automate des positions d’une expression, il suffit de construire inductivement cet automate (cf. [43, p156–157]).

Bien que l’automate des positions soit un automate intéressant pour les raisons que nous venons d’exposer, d’autres constructions d’automates à partir d’expressions rationnelles ont été considérées, dans le but de construire un automate le plus petit possible. En particulier on peut citer l’automate follow de Ilie et Yu [27] qui se trouve être un quotient de l’automate des positions.

Les problématiques de passer d’un modèle à l’autre et réciproquement étant bien étudiées, il apparaît intéressant de regarder la réversibilité de ces opérations. Une première voie, développée dans [13], s’intéresse à la récupération d’une expression rationnelle ’petite’ à partir de l’automate des positions d’une expression rationnelle. Une autre problématique envisagée dans [32] la possibilité de retrouver un automate fini à partir d’une expression rationnelle calculée sur cet automate. Une solution à cette problématique, donnée dans [32], utilise l’automate des termes dérivés cassés d’une expression .

Pour définir l’automate des termes dérivés cassés, il faut tout d’abord revenir à la définition d’une dérivation pour les expressions rationnelles. Cette dérivation a été introduite par Brzozowski dans [11]. Il s’agit d’une transposition syntaxique de la notion de quotient d’un langage aux expressions rationnelles : la dérivation d’une expression par rapport à une lettre est une expression qui dénote le quotient par rapport à cette lettre du langage dénoté par l’expression de départ. Il se trouve que cette dérivation permet, modulo des identités sur les expressions rationnelles – l’associativité, la commutativité et l’idempotence de la somme –, de construire un automate fini reconnaissant le langage de l’expression. Cet automate est déterministe et sa taille est exponentielle en la taille de l’expression.

Il apparaît donc que cette dérivation ne fournit pas un automate ‘petit‘, en plus de devoir réaliser des opérations contraignantes comme de repérer les expressions égales par commutativité de l’addition. C’est pour résoudre ce problème qu’Antimirov propose dans [5] une variante de la dérivation : cette nouvelle dérivation d’une expression rationnelle n’est plus une expression rationnelle mais un ensemble d’expressions rationnelles. Cette modification des dérivées, que nous appelons termes dérivés d’une expression, permet de construire un automate qui est un quotient de l’automate des positions [18], donc plus petit.

Les termes dérivés cassés sont une variante des termes dérivés. Cette variante consiste en l’éclatement des termes dérivés qui commencent par une somme – c’est-à-dire, si l’expression est une concaténation, si le terme le plus à gauche commence par une somme–. Cette variante permet entre autre d’avoir des automates plus généraux que les automates des termes dérivés qui sont toujours standard. Plus important encore, il est montré dans [32] que si l’on prend un automate – co-déterministe et co-mimimal –, que l’on calcule une expression rationnelle par élimination d’états et que l’on construit le co-quotient minimal de l’automate des termes dérivés cassés de cette expression alors on obtient l’automate de départ. Et ce, quel que soit l’ordre d’élimination des états choisis.