Lemme d'Arden

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En théorie des automates, le lemme d'Arden s'applique aux langages rationnels.

Il permet de résoudre des équations du type :

X = A \cdot X \cup B

où A et B sont deux langages rationnels et X l'inconnue recherchée. Si A ne contient pas le mot vide ε, le langage A^* \cdot B est solution de cette équation.

En effet,

A^* \cdot B = A \cdot A^* \cdot B \cup B = (A \cdot A^* \cup \{\epsilon\}) \cdot B

Par définition,

A^* = \bigcup_{n \ge 0} A^n

d'où :

A \cdot A^* \cup \{\epsilon\} = A \cdot \bigcup_{n \ge 0} A^n \cup \{\epsilon\} = A^*

car

A \subset \bigcup_{n \ge 0} A^n

et

\{\epsilon\} \subset \bigcup_{n \ge 0} A^n

Le lemme d'Arden s'utilise notamment dans la méthode des équations linéaires gauches qui permet de calculer le langage rationnel correspondant à un automate fini donné.