Le produit d'automates

Les états du produit sont les couples $(p,q)$, et la transition agit sur les deux composantes à la fois :

$$\Delta ((p,q),x)=({\delta }_A(p,x),{\delta }_B(q,x)).$$

Il y a $2\times 3=6$ états, et la même construction sert pour les deux opérations : seule change la condition d'acceptation — les deux composantes acceptantes pour l'intersection, au moins une pour l'union.

Les plus courts mots de l'intersection sont de longueur $3$, aab et aba : deux a pour la parité, et le facteur ab. On l'obtient par un parcours en largeur depuis l'état initial du produit — c'est le test de vacuité, et il rend au passage un témoin, ici aab.

Les tailles mesurées. Le produit a $6$ états ; l'émondage en retire un, et la minimisation n'en retire aucun de plus : $5$ états dans les deux cas. Le couple perdu est $(1,0)$, et il n'est pas accessible : sa première composante dit « un nombre impair de a », donc au moins un a lu, tandis que la seconde dit « aucun a encore lu ». Les deux ne peuvent pas être vraies ensemble — mais le produit, qui fabrique tous les couples, ne le sait pas. Pour l'union, le minimal tombe à $4$. Les deux automates ont été comparés aux prédicats correspondants sur les $4095$ mots de longueur au plus $11$ : accord complet.

C'est le défaut ordinaire du produit : il crée des états qui ne correspondent à aucune situation possible. On émonde donc systématiquement après, et le gain est parfois considérable.

La leçon de coût. Le produit est le seul procédé du chapitre dont la taille se multiplie sans exploser : $|Q_A|\times |Q_B|$. Comparé à la déterminisation, qui peut coûter $2^{|Q|}$, c'est bon marché. C'est pourquoi on préfère toujours intersecter des automates déterministes plutôt que de manipuler des expressions régulières, pour lesquelles l'intersection n'a pas de notation.