Lemme d’Arden
Il est important de noter qu’il existe deux version symétriques du lemme d’Arden. Suivant la version qu’on utilise la méthode pour générer les équations est légèrement différente.
Version de droite
Prenons l’automate suivant :
La construction des équations se fait comme suit : le langage reconnu par un état est égale au langage suivi du symbole de transition de ses prédécesseurs. Par exemple, le langage L2 accepté par l’état 2 est égale à : L2 = L1a. Un mot w ∈ Li si et seulement si il
existe un calcul de l’automate sur w partant de l’état initial et arrivant dans l’état i (attention la version n’est pas la même sur une version gauche).
Nous avons le système d’équation suivant :
En substituant L1 dans la deuxième équation par sa valeur puis L2 dans la troisième et quatrième équations on obtient :
On applique le lemme d’Arden droite aux deux dernières équations :
Le langage reconnu par l’automate est l’ensemble des langages reconnus par ses états terminaux, ce qui donne dans cet exemple : ab(a+b)* + (b+aa)a*
Version de gauche
Prenons l’automate suivant :
La construction des équations se fait comme suit : le langage reconnu par un état est égale au langage précédé du symbole de transition de ses successeurs. Par exemple, le langage L2 accepté par l’état 2 est égale à : L2 = aL1+aL3+ε (car c’est un état terminal). Un mot w ∈ Li si et seulement si il
existe un calcul de l’automate sur w partant de l’état i et arrivant dans un état final (attention si on utilisait l’autre version du lemme la définition serait différente).
Nous avons le système d’équations suivant :
En substituant L3 et L4 dans les deux premières équations puis L2 dans la première équation nous obtenons :
Enfin en appliquant le lemme d’Arden (version de gauche) à la première équation on
obtient : L1 = (a + bba + bbab)∗ (bb + ε). Nous avons ici le langage reconnu à partir de l’état initial, donc de l’automate.
