Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $$S_0$$ and $$S_1$$ are nondistinguishable and should be merged after minimization, but they are not. The process of minimization is like this: I tried to find out why by reading @Hendrik Jan's proof here, Proof of Brzozowski's algorithm for DFA minimization?

However, I find that this case bypasses the proof, because that in the reversed DFA, the initial state $$q_0$$ cannot be reached by $$q_0$$ using any words (but initial state is always considered reachable and cannot be removed). So did I miss anything, or does Brzozowki's algorithm has any specification for this corner case?

(It bypasses the proof like this: in the second series of reversal-determinization, $$S_0 = \{q_1\}$$ and $$S_1 = \{q_0, q_1\}$$, for any $$w$$, $$\delta(q_0, w)$$ in $$S_0$$ iff $$\delta(q_0, w)$$ in $$S1$$, so we say $$S_0 = S_1$$, assuming all states can be reached by $$\delta(q_0, w)$$, but $$\delta(q_0,w)$$ will never be $$q_0$$)

the initial DFA I was working on:

• $S_0$ is not a final state and $S_1$ is. So they cannot be merged. – rici Apr 7 '19 at 0:27
• But if we merge $S_0$ with $S_1$ (and the merged one is also a final state), we get the same DFA with fewer states, does it mean that the original DFA (without $S_0$ and $S_1$ merged) is not a minimal DFA? – Changda Li Apr 9 '19 at 2:37
• The merged DFA accepts $\epsilon$. The original one does not. So they are not equivalent. – rici Apr 9 '19 at 4:23
• Oh, I finally find out my issue. Actually the example I gave above is my "DIY" version trying to make it simpler. And the initial one that I didn't get right is updated in the question. I found out that I used the approach mentioned in Udacity course to do the minimization using Brzozowki's algorithm, which is creating a new state as initial state in the reversed NFA, when there are 2 or more final states. And if two sets are different only on the "created" initial states, I treated them as two different ones, which is not true. I shouldn't add a new state at the begining. – Changda Li Apr 11 '19 at 3:54
• Thanks @rici for helping me out, and your explanation makes things clearer! – Changda Li Apr 11 '19 at 3:56

1 Answer

I have looked into some other corner cases and have a tentative answer: when we are doing the determinization after reversal, there is a corner case where in the DFA before reversal, some states cannot be reached by applying any word to the initial state (two possibilities: the initial state cannot go back to itself or we are adding a state as the new initial state, because when we are doing reversal, there are 2 or more final states). In these cases, two sets are considered the same set if the only differences between them are the "unreachable" states before reversal.

I think we can prove that by reversing the proof process in the link cited in the question.