Termes dérivés cassés

Termes dérivés cassés

Nous avons vu dans le chapitre précédent que les termes dérivés permettent de construire un automate fini plus petit que l’automate standard et qui est même un quotient de celui-ci. Dans ce chapitre nous introduisons une nouvelle variante de la dérivation, la dérivation cassante, qui casse les sommes les plus à gauche d’une concaténation. La motivation pour cette nouvelle variante n’est pas exclusivement la construction d’un automate petit à partir d’une expression, bien que nous montrons que, sous certaines conditions, la borne sur l’ensemble des termes dérivés tient aussi pour les termes dérivés cassés. La motivation vient de [32] – ou plus précisément [33], la version corrigée du précédent –. Il y est montré qu’il est possible en utilisant les termes dérivés cassés, de reconstruire un automate à partir d’une expression calculée par élimination sur celui-ci. Plus précisément, si A est un automate co-déterministe et co-minimal et si E est une expression rationnelle calculée par élimination d’états, quelque soit l’ordre d’élimination choisi, sur A, alors A est le co-quotient minimal de l’automate des termes dérivés cassés de E. Dans ce chapitre nous présentons donc la définition des termes dérivés cassés et de l’automate qu’il représente. Nous présentons également des résultats qui donnent des bornes sur la taille de l’automate des termes dérivés cassés d’une expression donnée. En particulier si une expression est en forme normale, alors son automate des termes dérivés cassés a la même borne de taille que son automate des termes dérivés. L’automate des termes dérivés cassés n’est cependant pas un quotient de l’automate des positions et, pour des expressions qui ne sont pas en forme normale, il est également possible qu’il soit deux fois plus grand que ce dernier. 

Cassage d’une expression

Posons tout d’abord quelques notations sur les ensembles d’expressions rationnelles : soit X un ensemble d’expression rationnelles, (X)p est la partie propre de X – c’est à dire X \ {1} – et δX est un booléen valant 1 si l’expression 1 appartient à X. En particulier il vient : ∀X ⊆ RatE(A) ∂ ∂a Xp = ∂ ∂a X , c(Xp) ∨ δX = c(X) , (3.1) et Xp ∪ δX{1} = X . (3.2) Le cassage d’expressions rationnelles est en fait une opération qui décompose une expression en un ensemble d’expressions dont le facteur le plus à gauche n’est pas une somme : Définition 15 ([2]). L’ensemble B (E) des termes cassés l’expression rationnelle E sur A est l’ensemble d’expressions défini inductivement par : B (0) = {0} , B (1) = {1} , ∀a ∈ A B (a) = {a} , B (F + G) = B (F) ∪ B (G) , (3.3) B (F · G) = (B (F))p · G ∪ δB(F)B (G) , (3.4) B (F ∗ ) = {F ∗ } . (3.5) L’ensemble B (E) peut également être appelé le cassage de E, ou, lorsque l’on parle plus précisément de la fonction B, on dit fonction de cassage. Par définition, le cassage d’une expression est additif : ∀X ⊆ RatE(A) B (X) = [ E∈X B (E) . Il est immédiat de vérifier, par exemple par induction, que cette opération est idempotente : B (B (E)) = B (E) . Il est aussi possible de comparer le langage d’une expression E et le langage des expressions résultant du cassage de E : [ X∈B(E) |X| = |E| . Il apparaît également immédiatement que le cassage d’une expression rationnelle E est un ensemble de concaténations droites de sous-expressions de E. 46 Exemple 16 (Ex. 11 cont.). Nous continuons d’utiliser l’expression E1 = F1 ·(a·F1) avec F1 = (a ∗ +b ∗ ). Le cassage de E1 et de F1 donne les ensembles de termes cassés suivants : B (E1) = {a ∗ · (a · F1), b∗ · (a · F1)} , B (F1) = {a ∗ , b∗ } .

Termes dérivés cassés

Nous définissons maintenant la dérivation cassante par rapport à une lettre (respectivement à un mot) qui va nous permettre de définir les termes dérivés cassés : Définition 16. La dérivation cassante d’une expression rationnelle E sur A par rapport à une lettre a est définie comme le cassage de la dérivation de E par rapport à a : ∂b ∂a E = B  ∂ ∂a E  . La dérivation cassante par rapport à un mot ua, avec u ∈ A+, est définie comme pour les autres dérivations : ∂b ∂ua E = ∂b ∂a  ∂b ∂u E  . Toute expression qui appartient à ∂b ∂u E, pour un mot u quelconque de A+, est appelée vrai terme dérivé cassé de E. Nous notons TBD (E) l’ensemble des vrais termes dérivés cassés de E : TBD (E) = [ u∈A+ ∂b ∂u E . (3.6) L’ensemble BD (E) des termes dérivés cassés de E est l’union de l’ensemble TBD (E) des vrais termes dérivés cassés de E et de l’ensemble B (E) des termes cassés de E : BD (E) = TBD (E) ∪ B (E) . Par induction sur la profondeur de E et en utilisant la définition du cassage de E, on a : ∀a ∈ A ∂ ∂a B (E) = ∂ ∂a E , il en découle directement que : ∀u ∈ A + ∂b ∂u E = B  ∂ ∂u E  . Ce qui implique la propriété fondamentale suivante : 47 Propriété 22. Les termes dérivés cassés (respectivement les vrais termes dérivés cassés) d’une expression rationnelle E sont obtenus en prenant les termes cassés des termes dérivés (resp. des vrais termes dérivés) de E : ∀E ∈ RatE(A) BD (E) = [ K∈D(E) B (K) , TBD (E) = [ K∈TD(E) B (K) . (3.7) En particulier, si une expression E est constante, alors TBD (E) = ∅ . De même, cela montre que l’ensemble des termes dérivés cassés est fini. Exemple 17 (Ex. 11 cont.). L’ensemble des vrais termes dérivés cassés de E1 est : TBD (E1) = B ({a ∗ · (a · F1), b∗ · (a · F1), F1 , a∗ , b∗ }) , = {a ∗ · (a · F1), b∗ · (a · F1), a∗ , b∗ } . L’ensemble des termes dérivés cassés de E1 est donc : BD (E1) = TBD (E1) ∪ B (E1) = {a ∗ · (a · F1), b∗ · (a · F1), a∗ , b∗ } . La Propriété 22 donne une manière de calculer l’ensemble des vrais termes dérivés cassés directement à partir de l’ensemble des vrais termes dérivés. Cela permet donc d’avoir, comme précédemment, une manière de calculer l’ensemble des termes dérivés cassés inductive sans passer par la dérivation cassée : Proposition 23. Soient F et G deux expression rationnelles. Nous avons : TBD (F + G) = TBD (F) ∪ TBD (G) , (3.8) TBD (F · G) = (TBD (F))p · G ∪ TBD (G) ∪ δTBD(F)B (G) , (3.9) TBD (F ∗ ) = (TBD (F)) · F ∗ . (3.10) Démonstration. Cet énoncé est une application directe de (3.7) au calcul inductif de l’ensemble des vrais termes dérivés (Proposition 15, Equations (2.7)–(2.9)). L’équation (3.8) est triviale, développons (3.9) : TBD (F · G) = B (TD (F · G)) = B .