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 :

$X=A\cdot X\cup 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. C'est maintenant un résultat que l’on retrouve dans de nombreux manuels ou supports de cours.

Énoncé

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

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

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^{2}L\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^{n}B\cup A^{n-1}B\cup \cdots \cup AB\cup B$,

ce qui montre que $L$ contient tous les $A^{n}B$, 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^{n}B\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

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}$

où

$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}}$.

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 :

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

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)