En théorie des automates, le lemme d'Arden est un résultat concernant les langages rationnels.

Il décrit les solutions de l'équation :

X=A⋅X∪B

où A et B sont deux langages formels et X est une inconnue. Le lemme d'Arden s'utilise notamment dans la méthode des équations linéaires gauches qui permet de calculer le langage reconnu par un automate fini donné.

Le lemme est nommé d'après Dean N. Arden qui l'a décrit en 1961[1]. C'est maintenant un résultat que l’on retrouve dans de nombreux manuels ou supports de cours.

Énoncé

modifier

Lemme d'Arden[2] — Soient A et B deux langages formels sur un alphabet Σ. Le langage

L=A∗B

est le plus petit langage (pour l'inclusion ensembliste) qui est solution de l'équation

X=(A⋅X)∪B

De plus, si A ne contient pas le mot vide ε, le langage A∗B est l'unique solution de cette équation.

On peut voir l'équation X=A⋅X∪B comme la définition récursive d'un langage : un mot de ce langage est soit dans B, soit formé d'un mot dans A suivi d'un autre mot du langage, et on peut interpréter la solution comme une définition itérative : un mot est formé d'une suite de mots dans A, puis d'un mot final dans B.

Exemples

modifier
  • L'équation X=aX∪b, où a et b sont des lettres, a pour unique solution a∗b={b,ab,aab,…,anb,…}.
  • L'équation X=X∪B, où B est un langage, a pour plus petite solution B. Ici A est composé du mot vide, et A∗=A. En fait, tout langage contenant B est solution.
  • L'équation X=AX∪B, avec A=a∗b et B=a∗ a pour unique solution (a∗b)∗a∗={a,b}∗. En effet, l'équation signifie qu'un mot de la solution ou bien n'est formé que de lettres a, ou bien commence par un préfixe formé d'une suite de lettres a suivie d'un b, et d'un autre mot de la solution.

Démonstration

modifier

1. Le langage L=A∗⋅B est solution. En effet, on a :

AL∪B=A(A∗B)∪B=(AA∗∪{ε})B=A∗B=L.

2. Le langage A∗⋅B est la plus petite solution. Soit en effet L une autre solution. Alors on a : L=AL∪B=A(AL∪B)∪B=A2L∪AB∪B. En continuant à remplacer L par AL∪B, on obtient pour tout n>0 l'équation

L=An+1L∪AnB∪An−1B∪⋯∪AB∪B,

ce qui montre que L contient tous les AnB, donc A∗B.

3. Si A ne contient pas ε, alors cette solution est la seule. Soit en effet L une autre solution. On sait déjà que L contient A∗B. Par ailleurs, on a pour tout n>0 l'équation

L=An+1L∪AnB∪An−1B∪⋯∪AB∪B.

Soit w un mot de L de longueur n. Il appartient alors au membre droit de l'équation, mais il n'est pas dans An+1L parce que tout mot de ce langage a longueur au moins n+1 (puisque tout mot de A contient au moins une lettre). Donc le mot w appartient à un autre langage de l'union, donc à A∗B. Ceci prouve que L est contenu dans A∗B, donc l'égalité L=A∗B.

Application

modifier

Le lemme d'Arden permet, par la résolution d'un système d'équation par substitution, de déterminer le langage reconnu par un automate fini. On procède comme dans la méthode d'élimination de Gauss : on exprime une variable en fonction des autres, on la remplace par cette expression, on résout le système à une variable de moins, et on explicite la valeur de la variable éliminée.

Soit 𝒜=(Q,ℱ,I,T) un automate fini sur un alphabet Z. Pour chaque état q∈Q, soit Lq le langage reconnu à partir de l'état q, c'est-à-dire le langage reconnu en prenant q pour état initial. On pose enfin Zq,r={a∈Z∣(q,a,r)∈T}. Ce sont les étiquettes de transition de q à r. On a alors :

Lq=⋃r∈QZq,r⋅Lr∪Fq

où

Fq={{ε}q∈F∅q∉F

L'application du lemme d'Arden permet alors d'éliminer une à une les inconnues Lq des n équations de la forme précédente, et d'obtenir une expression explicite des Lq et notamment des Li,i∈I qui permettent de déterminer le langage reconnu par l'automate 𝒜.

Ce même procédé est le fondement de la méthode de Brzozowski et McCluskey, ou de l'algorithme de McNaughton et Yamada.

Exemple

modifier
Un automate à deux états

L'automate ci-contre donne le système d'équations :

L1=1L1∪0L2∪εL2=1L2∪0L1

Le lemme d'Arden donne

L2=1∗0⋅L1.

En injectant cette expression de L2 dans l'expression précédente de L1 et en factorisant, on obtient

L1=(1∪01∗0)⋅L1∪{ε},

et par application du lemme d'Arden,

L1=(1∪01∗0)∗.

Notes et références

modifier

Références

modifier
  1. ↑ (en) Dean N. Arden, « Delayed-logic and finite-state machines », dans 2nd Annual Symposium on Switching Circuit Theory and Logical Design, (FOCS), Detroit, Michigan, USA, IEEE Computer Society, 17-20 octobre 1961 (DOI 10.1109/FOCS.1961.13), p. 133-151.
  2. ↑ Mathématiques: tout-en-un, pour la licence, niveau L2 cours complet avec applications et 760 exercices corrigés, Paris, Dunod, coll. « Série Ramis », , 1321 p. (ISBN 978-2-10-050743-6), p. 379

Bibliographie

modifier
  • Jacques Sakarovitch, Éléments de théorie des automates [« Elements of Automata Theory »], Cambridge University Press, (ISBN 9780521844253)

Liens externes

modifier