De l'automate à l'expression

Le langage est celui des mots ayant un nombre pair de a.

L'élimination. On retire l'état $1$. Les chemins de $0$ vers $0$ qui passaient par $1$ se résument en une seule transition portant $E_{01}{E}_{11}^{\ast }{E}_{10}$, soit $a{b}^{\ast }a$. Il reste la boucle $b$ sur $0$, déjà présente. En additionnant les deux :

$$(b|a{b}^{\ast }a{)}^{\ast }.$$

Pourquoi $(b|aa{)}^{\ast }$ est fausse. Elle oublie que l'on peut lire des b entre les deux a — c'est exactement ce que dénote l'étoile $E_{11}^{\ast }$ dans la formule d'élimination, et c'est la partie qu'on oublie. Le plus court témoin est aba : il a deux a, donc il est dans le langage, et il n'est pas dénoté par $(b|aa{)}^{\ast }$.

Vérification. Les deux expressions ont été évaluées par dérivées sur les $8191$ mots de longueur au plus $12$ : $(b|a{b}^{\ast }a{)}^{\ast }$ coïncide exactement avec « nombre pair de a », et $(b|aa{)}^{\ast }$ diverge dès aba.

La règle à retenir. Dans $E_{pq}{E}_{qq}^{\ast }{E}_{qr}$, l'étoile centrale n'est jamais décorative : elle recueille tout ce que l'état éliminé pouvait faire sur lui-même. L'oublier est la faute unique de cet algorithme.