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 :

et sont deux langages formels et 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 | modifier le code]

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

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

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

On peut voir l'équation comme la définition récursive d'un langage : un mot de ce langage est soit dans , soit formé d'un mot dans 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 , puis d'un mot final dans .

Exemples[modifier | modifier le code]

  • L'équation , où et sont des lettres, a l'unique solution .
  • L'équation , où est un langage, a pour plus petite solution . Ici est composé du mot vide, et . En fait, tout langage contenant est solution.
  • L'équation , avec et a l'unique solution . En effet, l'équation signifie qu'un mot de la solution ou bien n'est formé que de lettres , ou bien commence par un préfixe formé d'une suite de lettres suivie d'un , et d'un autre mot de la solution.

Preuve[modifier | modifier le code]

1. Le langage est solution. En effet, on a :

.

2. Le langage est la plus petite solution. Soit en effet une autre solution. Alors on a : . En continuant à remplacer par , on obtient pour tout l'équation

,

ce qui montre que contient tous les , donc .

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

.

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

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 un automate fini sur un alphabet . Pour chaque état , soit le langage reconnu à partir de l'état , c'est-à-dire le langage reconnu en prenant pour état initial. On pose enfin . Ce sont les étiquettes de transition de à . On a alors :

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

Exemple[modifier | modifier le code]

Un automate à deux états

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

Le lemme d'Arden donne

.

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

,

et par application du lemme d'Arden,

.

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

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

  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.

Bibliographie[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]