2
$\begingroup$

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: enter image description here 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: enter image description here 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: enter image description here

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ $S_0$ is not a final state and $S_1$ is. So they cannot be merged. $\endgroup$
    – rici
    Apr 7 '19 at 0:27
  • $\begingroup$ 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? $\endgroup$
    – Changda Li
    Apr 9 '19 at 2:37
  • 1
    $\begingroup$ The merged DFA accepts $\epsilon$. The original one does not. So they are not equivalent. $\endgroup$
    – rici
    Apr 9 '19 at 4:23
  • $\begingroup$ 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. $\endgroup$
    – Changda Li
    Apr 11 '19 at 3:54
  • $\begingroup$ Thanks @rici for helping me out, and your explanation makes things clearer! $\endgroup$
    – Changda Li
    Apr 11 '19 at 3:56
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.