Problème avec l'implémentation de l'algorithme de Brzozowski

J'ai essayé d'implémenter l'algorithme de Brzozowski mais je viens de découvrir qu'il crée des automates sous-optimaux pour une certaine classe d'entrées, ayant un état de plus que ce qui est vraiment nécessaire dans le résultat. Je peux le montrer sur un automate trivial:

   a b           a   b           a b            a     b            a b
>0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2
 1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2
*2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3
                              *3 4 -        3   -     2         *3 1 3
                              *4 4 1        4  3,4    -          
                              *5 5 5        5   5    1,5         
                                           >6 3,4,5 1,2,5        

Ici, rev est la partie d'inversion de bord, où j'avais déjà supprimé les transitions sur epsilon, et det est la détermination par la construction du jeu de puissance, créant de nouveaux états dès qu'il les découvre, récursivement.

Le problème ici est le suivant: une fois que j'ai ajouté l'état supplémentaire pour compenser les trois états de départ différents après l'inversion du premier bord et la construction du jeu de puissance, rien ne revient jamais à cet état et donc je ne peux pas m'en débarrasser plus tard pour être équivalent à l'état de départ d'origine.

Y a-t-il quelque chose qui ne va pas dans ma façon de procéder? Suis-je en train de manquer quelque chose?

Ceci est une excellente question!

L'étape de retour dans l'algorithme de Brzozowski n'introduit pas un nouvel état de départ virtuel qui mène aux anciens états d'acceptation via -transitions. Au lieu de cela, il autorise plusieurs états de départ, ce qui n'est pas un gros problème, si vous construisez quand même l'automate produit juste après la réversion.$\varepsilon$

Sur le plan conceptuel, il est le plus facile de considérer le retour et la détermination comme une seule étape. Si votre DEA est , définissez-le comme le DEA inversé comme suit:$M=(Q,\Sigma,\delta,q_0,F)$$M^R=(Q^R,\Sigma,\delta^R,q_0^R,F^R)$

• $Q^R=\mathcal{P}(Q)$ ,
• $q_0^R=F$ ,
• $F^R=\{ P\subseteq Q \mid q_0\in P\}$ ,
• $\delta^R(P,a):=\{ p\in Q \mid \delta(p,a)\in P\}$ .

(Vous voudrez peut-être ignorer les états qui ne sont pas accessibles.)

Le théorème de Brzozowski déclare que est un DEA minimal acceptant .$(M^R)^R$$L(M)$

Pour une lecture plus approfondie, je suggère Elements of Automata Theory de Sakarovitch pages 116-117.