3
$\begingroup$

I have some troubles in understanding of the Brzozowski's algorithm for NFA to minimized DFA transformation. Or maybe I'm doing a mistake in the NFA to DFA transformation steps.

The Algorithm, as described in Wikipedia, is as follows:

  1. Reverse the NFA.
  2. Transform to DFA.
  3. Reverse DFA.
  4. Transform to DFA again.

Let's assume we have the following language: A* (zero or more repetitions of A).

For this language we may have the following NFA (over-complicated for a purpose):

Initial NFA

  1. I'm reversing it.

    Reversed NFA

  2. Turning reversed NFA to DFA using the Powerset approach.

    1. The init state 3 Epsilon-closure is {1, 2, 3}.
    2. Closure {1, 2, 3} transits by A to {1, 2}.
    3. Closure {1, 2} transits by A to {1, 2}.

    So, we have two new states for these two new closures and transitions between them as follows:

    Reversed NFA to DFA

    All states are final as their closures contain state 1. {1, 2, 3} state is a Start state is it contains state 3. This is clearly a DFA that reads the reversed language which is equal in this case to original one A*. There are redundant states, but I assume it does not contradict the Algorithm requirements.

  3. Reverse it again.

    Second Reverse

  4. Turning to DFA again.

    1. The init state 3 Epsilon-closure is {1, 2, 3}.
    2. Closure {1, 2, 3} transits by A to {1, 2}.
    3. Closure {1, 2} transits by A to {1, 2}.

    New closure-states and the topology of the final Automata are the same as on step 2. Final Automata

But this DFA is not minimal. Can you explain me, please, where did I make a mistake?

Thanks in advance!

Ilya.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I think the problem here may be that you introduced a new start for the reversal. If, instead, you allow a set of start states instead of a single start state, you will get the minimal DFA. $\endgroup$
    – Pseudonym ♦
    Apr 12 at 13:55
  • $\begingroup$ @Pseudonym Thank you for your reply. It will fix the issue in this particular case, and probably in some similar cases, but do you think it is the only issue, and introducing of multi-start states will not be just an edge-case hack? $\endgroup$
    – Ilya Lakhin
    Apr 12 at 15:21
  • $\begingroup$ Well I've never seen a proof by Janusz Brzozowski that wasn't correct! But without having a copy of the paper, I can't say for certain what technique he used to reverse the DFA. $\endgroup$
    – Pseudonym ♦
    Apr 13 at 8:44
  • $\begingroup$ @Pseudonym Also, if I introduce multi-start Automata, how do I merge it back in the end to obtain canonical DFA? $\endgroup$
    – Ilya Lakhin
    Apr 13 at 12:01
  • 1
    $\begingroup$ I don't understand that question. The epsilon closure of a set of states is merely the union of the epsilon closures of each state in the set, so the result will be a DFA. $\endgroup$
    – Pseudonym ♦
    Apr 13 at 14:35

1 Answer 1

Reset to default
4
$\begingroup$

I realized this question is a duplicate.

Basically, as @Pseudonym mentioned above, when reverting DFA you should avoid introducing new starting state of the NFA even if there were multiple finish states in DFA. Instead just merge epsilon closures of each reversed NFA start state into a single closure and treat it as a start closure during the Powerset construction.

For those of you who faced this suboptimal issue after reading of the Wikipedia Article's Note:

or add an extra state with ε-transitions to all the initial states, and make only this new state initial.

Please be aware, that this note is simply wrong.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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