Problema con la implementación del algoritmo de Brzozowski

He estado tratando de implementar el algoritmo de Brzozowski, pero acabo de descubrir que crea autómatas subóptimos para una determinada clase de entradas, con un estado más de lo que realmente se necesita en el resultado. Puedo mostrarlo en un autómata 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        

Aquí rev es la parte de inversión de bordes, donde ya había eliminado las transiciones en épsilon, y det es la determinación a través de la construcción de conjuntos de potencia, creando nuevos estados tan pronto como los descubre, de forma recursiva.

El problema aquí es este: una vez que agrego el estado adicional para compensar los tres estados de inicio diferentes después de la inversión del primer borde y la construcción del conjunto de potencia, nada vuelve a ese estado y, por lo tanto, no puedo deshacerme de él más tarde por ser equivalente al estado de inicio original.

¿Hay algo mal con la forma en que lo estoy haciendo? ¿Me estoy perdiendo de algo?

Esta es una excelente pregunta!

El paso de reversión en el Algoritmo de Brzozowski no introduce un nuevo estado de inicio virtual que conduce a los antiguos estados de aceptación a través de las transiciones . En cambio, permite múltiples estados de inicio, lo que no es un gran problema, si construye el autómata del producto de todos modos justo después de la reversión.$\varepsilon$

Conceptualmente, es lo más fácil considerar la reversión y la determinación como un solo paso. Si su DEA es , entonces defina como la DEA revertida siguiente manera:$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\}$ .

(Es posible que desee ignorar los estados que no son accesibles).

El teorema de Brzozowski establece que es una DEA mínima que acepta .$(M^R)^R$$L(M)$

Para leer más, sugiero Elementos de la teoría de autómatas de Sakarovitch, páginas 116-117.