Les Xor-automates, une forme normale compacte pour les langages réguliers

La seule forme normale connue pour un langage régulier L est son automate deterministe minimal MDA(L). Nous montrons qu’un langage régulier est aussi caractérisé par une dimension finie dim(L), qui est toujours plus petite (voire exponentiellement plus petite) que le nombre d’états |MDA(L)| de l’automate minimal. Cette dimension est le nombre minimal d’états des xor- automates non-deterministes (NXA) qui acceptent le langage. Les NXAs combinent les avantages des automates déterministes (l’existence de forme normale, compatibilité avec la négation, algorithmes de minimisation, notion d’équivalence d’états et d’accessibilité) et les avantages des automates non déterministes (représentation compacte, ou matricielle, compatibilité avec le miroir). Nous donnons un algorithme de minimisation qui produit en temps cubique le xor-automate minimal de L: MXA(L) à partir de n’importe quel NXA reconnaissant L. Le MXA est une forme normale du langage L=L’<=>MXA(L)=MXA(L’). La manière dont notre algorithme fonctionne permet d’établir un lien entre l’algorithme de Brzozowski (qui minimise un automate deterministe en utilisant le langage miroir) et les autres algorithmes basés sur l’équivalence d’états (quotient de Nerode, ou autres).