Lemme d'Arden

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 :

${\displaystyle X=A\cdot X\cup B}$

où ${\displaystyle A}$ et ${\displaystyle B}$ sont deux langages formels et ${\displaystyle 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é

On peut voir l'équation ${\displaystyle X=A\cdot X\cup B}$ comme la définition récursive d'un langage : un mot de ce langage est soit dans ${\displaystyle B}$, soit formé d'un mot dans ${\displaystyle 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 ${\displaystyle A}$, puis d'un mot final dans ${\displaystyle B}$.

Exemples

• L'équation ${\displaystyle X=aX\cup b}$, où ${\displaystyle a}$ et ${\displaystyle b}$ sont des lettres, a pour unique solution ${\displaystyle a^{*}b=\{b,ab,aab,\ldots ,a^{n}b,\ldots \}}$.

• L'équation ${\displaystyle X=X\cup B}$, où ${\displaystyle B}$ est un langage, a pour plus petite solution ${\displaystyle B}$. Ici ${\displaystyle A}$ est composé du mot vide, et ${\displaystyle A^{*}=A}$. En fait, tout langage contenant ${\displaystyle B}$ est solution.

• L'équation ${\displaystyle X=AX\cup B}$, avec ${\displaystyle A=a^{*}b}$ et ${\displaystyle B=a^{*}}$ a pour unique solution ${\displaystyle (a^{*}b)^{*}a^{*}=\{a,b\}^{*}}$. En effet, l'équation signifie qu'un mot de la solution ou bien n'est formé que de lettres ${\displaystyle a}$, ou bien commence par un préfixe formé d'une suite de lettres ${\displaystyle a}$ suivie d'un ${\displaystyle b}$, et d'un autre mot de la solution.

Démonstration

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

${\displaystyle AL\cup B=A(A^{*}B)\cup B=(AA^{*}\cup \{\varepsilon \})B=A^{*}B=L}$.

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

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

ce qui montre que ${\displaystyle L}$ contient tous les ${\displaystyle A^{n}B}$, donc ${\displaystyle A^{*}B}$.

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

${\displaystyle L=A^{n+1}L\cup A^{n}B\cup A^{n-1}B\cup \cdots \cup AB\cup B}$.

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

Application

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

${\displaystyle L_{q}=\bigcup _{r\in Q}Z_{q,r}\cdot L_{r}\cup F_{q}}$

où

${\displaystyle 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 ${\displaystyle L_{q}}$ des ${\displaystyle n}$ équations de la forme précédente, et d'obtenir une expression explicite des ${\displaystyle L_{q}}$ et notamment des ${\displaystyle L_{i},i\in I}$ qui permettent de déterminer le langage reconnu par l'automate ${\displaystyle {\mathcal {A}}}$.

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

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

${\displaystyle {\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

${\displaystyle L_{2}=1^{*}0\cdot L_{1}}$.

En injectant cette expression de ${\displaystyle L_{2}}$ dans l'expression précédente de ${\displaystyle L_{1}}$ et en factorisant, on obtient

${\displaystyle L_{1}=(1\cup 01^{*}0)\cdot L_{1}\cup \{\varepsilon \}}$,

et par application du lemme d'Arden,

${\displaystyle L_{1}=(1\cup 01^{*}0)^{*}}$.

Notes et références

Référence

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne)
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)

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

Liens externes

• (en) Sur le site de l'EPFL (École polytechnique fédérale de Lausanne)

• Portail de l'informatique théorique