Résolution par le lemme d’Arden

Il est important de noter qu’il existe deux version symétriques du lemme d’Arden :

langage32

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 :

langage33

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 :

langage34

En substituant L1 dans la deuxième équation par sa valeur puis L2 dans la troisième et quatrième équations on obtient :

langage35

On applique le lemme d’Arden droite aux deux dernières équations :

langage36

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 :

langage37

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 :

langage38

En substituant L3 et L4 dans les deux premières équations puis L2 dans la première équation nous obtenons :

langage39

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.

 

Publicités