Résolution par le lemme d’Arden

Difficulté
Difficile 80%

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.

lemme d'Arden

Version de droite

Prenons l’automate suivant :

lemme d'Arden

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 :

lemme d'Arden

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

lemme d'Arden

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

lemme d'Arden

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 :

lemme d'Arden

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 :

lemme d'Arden

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

lemme d'Arden

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.

Partager
fr_FRFR
%d blogueurs aiment cette page :