Termes dérivés

Termes dérivés

Dérivation des expressions

Dans cette section nous rappelons la définition des expressions dérivées d’une expression rationnelle et de l’automate qui en découle. 2.1.1 Expression dérivée d’une expression Définition 8 ([11]). Soient E une expression rationnelle sur A et a une lettre de A. L’expression dérivée 1 de E par rapport à a, notée [a] -1(E), est l’expression rationnelle définie inductivement par : [a] -1(0) = [a] -1(1) = [a] -1(b) = 0 ∀b ∈ A, b 6= a , [a] -1(a) = 1 , [a] -1(F + G) = [a] -1(F) + [a] -1(G) , [a] -1(F · G) = ([a] -1(F)) · F + c(F)[a] -1(G) , [a] -1(F * ) = ([a] -1(F)) · F ∗ , où il faut comprendre que c(F)[a] -1(G) vaut [a] -1(G) si le terme constant de F est non nul et 0 sinon. Nous avons choisi de noter [a] -1(E) l’expression dérivée par rapport à a de l’expression rationnelle E afin de n’avoir aucune ambiguïté avec les autres opérations de dérivation que nous définissons par la suite. 1. Appelée en anglais derivative dans [11]. 31 Exemple 7. Posons K1 = (b · a ∗ )·((a + b) ∗ ). Pour simplifier l’écriture, nous posons K ′ 1 = (a + b) ∗ et donc K1 = (b · a ∗ ) · K ′ 1 . Les expressions dérivées par rapport à a et b de K1 sont : [a] -1(K1) = [a] -1(b · a * ) · K ′ 1 + c(b · a ∗ )[a] -1(K1’) = [a] -1(b · a * ) · K ′ 1 = ([a] -1(b) · a ∗ ) · K ′ 1 + c(b)[a] -1(a* ) = (0 · a ∗ ) · K ′ 1 = 0 [b] -1(K1) = ([b] -1(b) · a ∗ ) · K ′ 1 = a ∗ · K ′ 1 Si l’on dérive ce dernier résultat par a on obtient : [a] -1(a* · K’1) = [a] -1(a* ) · K ′ 1 + c(a ∗ )[a] -1(K1’) = a ∗ · K ′ 1 + K ′ 1 La notation choisie est justifiée par la propriété suivante : Propriété 10. Si E est une expression rationnelle sur A qui dénote le langage L et que a est une lettre de A, alors le langage dénoté par la dérivée [a] -1(E) de E par rapport à a dénote le langage a −1L. Finalement nous pouvons étendre la dérivation aux mots : Définition 9 ([11]). Soient E une expression rationnelle sur A, u un mot non vide de A∗ et a une lettre de A. L’expression dérivée de E par rapport à ua, notée [ua] -1(E), est l’expression rationnelle définie inductivement par : [ua] -1(E) = [a] -1([u] -1(E)) . L’ensemble des expressions dérivées d’une expression E est l’ensemble des expressions dérivées de cette expression E par rapport à n’importe quel mot u non vide de A∗ . Exemple 8 (Ex. 7 cont.). Comme nous l’avons déjà calculé : [ba] -1(K1) = [a] -1(a* · K1’) = a ∗ · K ′ 1 + K ′ 1 . et nous avons : [bb] -1(K1) = [b] -1(a* · K1’) = K ′ 1 , [baa] -1(K1) = [a] -1(a* · K1 + K1’) = a ∗ · K ′ 1 + K ′ 1 + K ′ 1 . 32 Propriété 11. Si E est une expression rationnelle sur A qui dénote le langage L et que u est un mot non vide de A∗ , alors le langage dénoté par l’expression dérivée [u] -1(E) de E par rapport à u dénote le langage u −1L. 

Nombre d’expressions dérivées

La définition donnée peut produire un nombre infini d’expressions dérivées pour une expression rationnelle E donnée, comme le montre l’exemple de l’expression K1 puisque la dérivation par rapport au mot ban donne : [ban ] -1(K1) = a ∗ · K ′ 1 + K ′ 1 + · · · + K ′ 1 , avec une somme de n fois K ′ 1 . Cependant si les calculs sur les expressions rationnelles sont réalisés modulo l’associativité de la somme, la commutativité de la somme et l’idempotence de la somme, alors nous avons le théorème suivant : Théorème 12 ([11]). L’ensemble des expressions dérivées d’une expression rationnelle est fini modulo les identités As, C et I et il est calculable. Exemple 9 (Ex. 7 cont.). Modulo AsCI, les expressions dérivées de K1 sont : 0, K1, a ∗ · K1, K1 et a ∗ · K1 + K1. 2.1.3 Automates des expressions dérivées Le théorème précédent permet de calculer un ensemble fini d’expressions dérivées. Cela permet donc de définir l’automate fini suivant dont les états sont les expressions dérivées modulo AsCI d’une expression : Définition 10. L’automate BE des expressions dérivées d’une expression rationnelle E est l’automate déterministe tel que : (i) l’ensemble des états est l’ensemble des expressions dérivées modulo AsCI de E ; (ii) l’état initial est l’expression E ; (iii) les états finaux sont les états dont le terme constant est non nul ; (iv) si F est une expression dérivée de E alors (F, a, [a] -1(F)) est une transition de BE. De la Propriété 11 découle directement : Proposition 13 ([11]). Si E est une expression rationnelle dénotant L, alors BE reconnaît L. Exemple 10 (Ex. 7 cont.). L’automate des expressions dérivées de K1 est montré sur la Figure 2.1.

Termes dérivés d’une expression

L’automate des expressions dérivées d’une expression E reconnaît le langage L dénoté par E, cependant sa taille peut être exponentielle en la taille de l’expression et présuppose également des calculs modulo AsCI très coûteux. Nous décrivons dans cette section une modification de l’opération de dérivation vue dans la section précédente, due à Antimirov dans [5] et qui permet de construire un automate – qui peut ne pas être déterministe – qui ne soit pas plus gros que l’automate standard de cette expression. L’idée pour atteindre ce but est de remplacer la dérivée d’une expression par un ensemble d’expressions dont chaque élément est un terme de la somme que définit l’expression dérivée. Cela permet, d’une certaine manière, de réaliser ‘à la volée‘ l’opération de modulo AsCI là où elle est nécessaire. 

Définition et propriétés

Nous allons maintenant définir les termes dérivés d’une expression rationnelle. Ces termes dérivés ont été définis en [5] sous le nom de partial derivatives. Nous n’utilisons pas cette terminologie mais celle de [43, I.5.2] pour les raisons évoquées dans cette dernière référence : les ‘derivatives‘ de [11] sont déjà partielles dans le sens où elles sont définies par rapport à une lettre. La terminologie ‘terme dérivé‘ est utilisée car les termes dérivés sont les termes de la somme définie par l’expression dérivée. Définition 11 ([5]).