5. Systèmes d'équations rationnelles

Nous définissons maintenant des "équations" entre expressions rationnelles et montrons comment résoudre des systèmes d'équations de ce type.

Les définitions rationnelles permettent de proposer des expressions rationnelles plus lisibles. Cependant, il est parfois nécessaire d'obtenir une expression rationnelle ne comportant que des symboles du vocabulaire. Il faut donc alors essayer de trouver (ou retrouver) cette expression. La simple substitution n'est pas toujours suffisante, surtout en cas de récursivité. La solution consiste à passer par la résolution d'un système d'équations rationnelles. La transformation s'effectue en utilisant directement les définitions rationnelles. L'opérateur → devient =, l'opérateur | devient +, parfois ε devient 1 et les identificateurs deviennent des variables. La résolution du système ainsi obtenu donne l'expression rationnelle du langage. Nous allons donc décrire ces systèmes d'équations ainsi que la méthode de résolution.


Système d'expressions rationnelles

Les systèmes d'équations rationnelles sont des ensembles d'équations dont les coefficients sont des expressions rationnelles.

Par exemple, le système suivant est un système d'équations rationnelles :

X=a1X+a2Y+a3

Y=b1X+b2Y+b3

avec ai, bi (i=1,2,3) des expressions rationnelles.

Alors une solution est :

X=(a1|a2b2*b1)*(a3|a2b2*b3)

Y=(b2|b1a1*a2)(b3|b1a1*a3)

Remarque : les solutions ne sont pas uniques, mais, en général, on s'intéresse à la plus petite des solutions (le plus petit point fixe).


Système d'expressions rationnelles en forme standard

Un ensemble d'équations rationnelles d'indéterminés D={X1, ..., Xn} est en forme standard si ∀ Xi ∈ D, il y a une équation de la forme Xi=ai0 + ai1X1 + ... + ainXn avec aij des expressions rationnelles sur A telles que A ∩ D = ∅.

Remarques : il est possible d'avoir aij=∅ quand il n'y a pas de terme correspondant à Xj dans l'équation de Xi. ∅ joue le rôle de 0 et ε celui de 1 (l'équation pour Xi comporte alors Xj sans coefficient à droite). Souvent, on utilise même 1 plutôt que ε dans ces équations.

Pour résoudre un tel système, il suffit, par analogie avec les systèmes linéaires, de procéder par élimination de variables. Pour cela, il est nécessaire de passer par le lemme d'Arden.


Lemme d'Arden

Soient K et L deux langages sur A* (K ⊆ A* et L ⊆ A*), ε ∉ K, alors :

  1. K*L est l'unique solution de l'équation X = KX + L.
  2. LK* est l'unique solution de l'équation X = XK + L.

Si ε ∈ K, alors A* est solution et K*L la plus petite solution.

Démonstration :

Les deux cas se traitent de manière similaire. Pour démontrer Arden (par exemple le cas 1) il suffit d'abord de montrer que X=K*L est une solution de X=KX+L. Ensuite, il faut montrer que cette solution est la seule possible. Pour cela, il faut procéder par l'absurde en proposant une autre solution P à l'équation.

Démonstration plus formelle.

De ce lemme, il est possible de démontrer un certain nombre d'identités rationnelles très utiles pour démontrer des équivalences d'expressions rationnelles ou pour simplifier des expressions.

En particulier, il assez aisé de démontrer les identités suivantes :

Pour démontrer e1 par exemple, il suffit de démontrer que (a+b)* = a*(ba*)*. (a+b)*, selon le lemme d'Arden, est l'unique solution de l'équation X = (a+b)X+1. Si (a+b)* = a*(ba*)*, alors a*(ba*)* est aussi solution de cette équation :

(a+b)(a*(ba*)*)+1 = a+(ba*)* + ba*(ba*)*+1
  a+(ba*)* + (ba*)++1
  a+(ba*)* + (ba*)*
  (a+ + 1)(ba*)*
(a+b)(a*(ba*)*)+1 = a*(ba*)*

Donc est bien solution de l'équation : CQFD

Revenons maintenant à l'algorithme de résolution d'un système d'équations rationnelles. Soit un système de n équations rationnelles notées X1, ..., Xn. Cette méthode se déroule en trois phases :

  1. Ecrire, quand c'est possible, les équations du système sous la forme Xi = xiXi + Yi où xi est une expression rationnelle sur A et Yi est une expression rationnelle de la forme y0 + y1X1 + ... + yi-1Xi-1 +yi+1Xi+1 + ... + ynXn avec yi des expressions rationnelles sur A.
  2. Pour toutes les équations Xi de X1 à Xn-1, sachant que selon le lemme d'Arden, l'unique solution pour Xi = xiXi+Yi est xi*Yi, remplacer dans toutes les équations Xi+1... Xn la variable Xi par xi*Yi
  3. Pour toutes les équations Xi de Xn à X1, calculer la valeur de Xi en appliquant le Lemme d'Arden et remplacer Xi par cette valeur dans toutes les équations de Xi-1 à X1.

Il faut penser à simplifier continuellement vos expressions rationnelles pour avoir un résultat le plus simple possible. De plus, en fonction des simplifications choisies et de l'ordre adopté, les résultats ne sont pas toujours identiques (du point de vue des expressions obtenues) mais toujours équivalents.

Par exemple, Soit D={X1, X2, X3} avec A={0,1} et le système S :
X1 = 0X2 + 1X1 + ε
X2 = 0X3 + 1X2
X3 = 0X1 + 1X3

étape 1 X1 = 1X1 + (0X2 + ε)
X2 = 1X2 + (0X3)
X3 = 1X3 + (0X1)
étape 2 X1 = 1X1 + (0X2 + ε)
X2 = 1X2 + (0X3)
X3 = 1X3 + (01*(01*0X3 + ε))
étape 3 X3= (1+01+0)X3 + 01*=(1+01*01*0)*01*
X2 = 1*(0X3) = 1*0(1+01*01*0)*01*
X1 = 1*(0X2 + ε) = 1*01*0(1+01*01*0)*01*+1*

Nous verrons dans un prochain chapitre que ces systèmes sont utiles pour obtenir la description par une expression de langages décrits par un automate d'état fini.

Exercices et tests :

Exercice 5.1. a et b sont deux expressions rationnelles. Montrer que :

  1. a(a+ba)* = (a+ab)*a Aide
  2. (a+b)+ = a+ + a* (ba*)+ Aide

Solution

Exercice 5.2. Démonter que a(ba)*b = (ab)+. Aide

Solution

Exercice 5.3. Résoudre les systèmes suivants :

  1. L1 = aL2 + bL3
    L2 = bL2 + 1
    L3 = bL3 + aL2
  2. L1 = bL2 + bL3
    L2 = aL2 + aL4 + 1
    L3 = cL4
    L4 = cL4 + 1
  3. L1 = (a+b) L2
    L2 = (a+b) L2 + cL3
    L3 = cL4
    L4 = cL3 + (a+b)L5 + 1
    L5 = (a+b)L5 + 1

Solution

mercredi, 26/11/03 8:43