Lemme d'Arden

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 \cdot X \cup B

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 1960[1]. C'est maintenant un résultat que l’on retrouve dans de nombreux manuels ou supports de cours.

Énoncé[modifier | modifier le code]

Lemme d'Arden — Soient A et B deux langages formels. Le langage

L = A^*B

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

X = (A \cdot X )\cup B

De plus, si A ne contient pas le mot vide \varepsilon, le langage A^*B est l'unique solution de cette équation.

On peut voir l'équation X = A \cdot X \cup 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 | modifier le code]

  • L'équation X=aX\cup b, où a et b sont des lettres, a l'unique solution a^*b=\{b,ab,aab,\ldots,a^nb,\ldots\}.
  • L'équation X=X\cup 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\cup B, avec A=a^*b et B=a^* a l'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.

Preuve[modifier | modifier le code]

1. Le langage L=A^* \cdot B est solution. En effet, on a :

AL\cup B = A(A^*B) \cup B = (AA^* \cup\varepsilon)B = A^*B=L.

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

L=A^{n+1}L\cup A^nB\cup A^{n-1}B\cup\cdots\cup AB\cup B,

ce qui montre que L contient tous les A^nB, donc A^*B.

3. Si A ne contient pas \varepsilon, 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=A^{n+1}L\cup A^nB\cup A^{n-1}B\cup\cdots\cup AB\cup 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 A^{n+1}L 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 | modifier le code]

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 \mathcal{A} = (Q, \mathcal{F}, I, T) un automate fini sur un alphabet Z. Pour chaque état q \in Q, soit L_q le langage reconnu à partir de l'état q, c'est-à-dire le langage reconnu en prenant q pour état initial. On pose enfin Z_{q,r} = \{a\in Z \mid (q, a ,r) \in T\}. Ce sont les étiquettes de transition de q à r. On a alors :

L_q =\bigcup_{r \in Q} Z_{q,r}\cdot L_r \cup F_q

F_q = \begin{cases}\{\varepsilon\} & q \in F \\ \varnothing & q \notin F \end{cases}

L'application du lemme d'Arden permet alors d'éliminer une à une les inconnues L_q des n équations de la forme précédente, et d'obtenir une expression explicite des L_q et notamment des L_i, i \in I qui permettent de déterminer le langage reconnu par l'automate \mathcal{A}.

Exemple[modifier | modifier le code]

Un automate à deux états

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

\begin{array}{lcl}L_1&=&1L_1\cup 0L_2\cup \varepsilon\\
L_2&=&1L_2\cup 0L_1\end{array}

Le lemme d'Arden donne

L_2 = 1^*0 \cdot L_1.

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

L_1 = (1\cup 01^*0) \cdot L_1 \cup \{\varepsilon\},

et par application du lemme d'Arden,

L_1 = (1 \cup 01^*0)^*.

Notes et références[modifier | modifier le code]

Référence[modifier | modifier le code]

  1. 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

Bibliographie[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]