Construction des automates des termes dérivés et termes dérivés cassés

Construction des automates des termes dérivés et termes dérivés cassés

Dans ce chapitre, nous expliciterons une construction pour l’automate des termes dérivés et pour l’automate des termes dérivés cassés. La première construction d’un automate des termes dérivés est donnée dans [5] comme l’application directe de la définition de l’automate. Dans cette méthode, on construit l’ensemble des termes dérivés en dérivant tous les termes dérivés connus par chaque lettre de l’alphabet jusqu’à ne plus en trouver de nou- veaux. Les transitions sont construites simultanément à chaque étape par la dérivation par rapport à une lettre. Si l’expression de départ est de taille n alors la méthode d’Antimirov a une complexité de O(n). Pour les termes dérivés cassés il est possible d’envisager une méthode similaire, avec une complexité identique.Il existe également une construction de l’automate des termes dérivés qui se base sur des modifications de l’arbre syntaxique de l’expression. Ces modifications font ressortir une représentation des termes dérivés sous forme de chemins dans un graphe. Cette idée de modifier l’arbre syntaxique d’une expression rationnelle en ajoutant des arcs orientés afin de pouvoir obtenir un automate a d’abord été introduite dans [51] où une telle modification de l’arbre, appelée alors ZPC-structure permet de construire l’automate des positions de l’expression.

L’identification des termes dérivés identiques, qui constitue l’étape la plus coûteuse de [18], peut être améliorée. Ainsi dans [17], le marquage des sous- expressions étoilées identiques de l’expression rationnelle permet de réaliser cette identification en complexité O(n). L’identification des sous-expressions est poussée encore plus loin dans [28] où toutes les sous-expressions sont marquées de manière à ce que deux sous-expressions isomorphes partagent la même marque. Cette méthode permet d’améliorer encore la complexité du calcul en O(ln) où l est la longueur littérale de l’expression rationnelle.Dans [1], Allauzen et Mohri proposent un algorithme pour construire l’au- tomate des termes dérivés d’une expression à partir de l’automate de Thomp- son (cf. [47]) de cette expression. Dans [1] c’est en fait à la fois l’automate des positions, l’automate des termes dérivés et l’automate Follow qui sont construits à partir de l’automate de Thompson de l’expression en utilisant uniquement des opérations de minimisation et d’élimination de transitions spontanées. Plus précisément, l’automate des termes dérivés est le résultat de l’élimination des transitions spontanées sur la minimisation de l’automate obtenu par élimination des transitions spontanées créées lors d’une concaté- nation dans la construction de l’automate de Thompson. Cette méthode a la même complexité que l’algorithme de [28] mais permet d’unifier la construc- tion de différents automates à partir d’une expression rationnelle.

Pour le calcul de l’automate des termes dérivés, dans ce chapitre, c’estune méthode très similaire à celle de [28] que nous présentons. Le calcul des termes dérivés est réalisé à partir de chemins dans l’arbre syntaxique de l’expression et nous marquons les états de cet arbre pour identifier les termes dérivés. La méthode que nous allons décrire peut être vue comme une généralisation de l’algorithme de [28] dans le cas où les expressions ne sont pas construites modulo l’associativité du produit. Une autre différence réside dans le fait que, afin de pouvoir adapter notre algorithme au calcul de l’automate des termes dérivés cassés, nous ne séparons pas le calcul destransitions de celui des états de l’automate, c’est-à-dire que nous n’utilisons pas directement le fait que l’automate des termes dérivés est un quotient de l’automate des positions. Ceci est important car l’automate des termes dérivés cassés n’est pas un quotient de l’automate des positions. Dans le cas de l’automate des termes dérivés, cette différence de conception ne change pas les calculs réalisés car dans les deux cas, c’est l’idée de l’algorithme de [51] – pour les transitions de l’automate des positions – qui est utilisé.