Deux expressions, un même langage ?

Premier couple : même langage. $(a^{\ast }{b}^{\ast }{)}^{\ast }$ dénote toutes les concaténations de blocs de la forme $a^i{b}^j$ ; comme un tel bloc peut être réduit à une seule lettre, on obtient tous les mots.

Deuxième couple : même langage. Les deux dénotent les mots alternés commençant et finissant par a : $a$, $aba$, $ababa$, … Elles ne se ressemblent pas, et c'est le point : $(ab{)}^{\ast }a$ groupe par la gauche, $a(ba{)}^{\ast }$ par la droite, et le langage est le même. Deux écritures, un ensemble — la distinction syntaxe / sémantique du chapitre.

Troisième couple : différents. Le plus court témoin est ab, qui est dans $(a|b{)}^{\ast }$ et dans aucune des deux branches de $a^{\ast }|b^{\ast }$.

L'algorithme général. On ne compare pas des expressions, on compare des automates :

• construire un automate pour chaque expression (Berry-Sethi) ;
• les déterminiser et les compléter ;
• former le produit reconnaissant $L_1\setminus L_2$ — acceptant si la première composante l'est et la seconde non ;
• tester si ce langage est vide, par un parcours en largeur depuis l'état initial ;
• recommencer en échangeant les rôles.

Le parcours ne rend pas seulement « oui » ou « non » : il rend le plus court mot de la différence, donc un témoin. C'est ainsi que les témoins ci-dessus ont été obtenus, et confirmés par un calcul indépendant par dérivées sur tous les mots de longueur au plus $10$.

Ce que ce test montre en creux. L'équivalence de deux expressions régulières est décidable — au sens du chapitre chap:decidabilite. Peu de problèmes de ce genre le sont : l'équivalence de deux grammaires non contextuelles, elle, ne l'est pas.