3

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.

Ilya Lakhin
  • 171
  • 6
  • 1
    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. – Pseudonym Apr 12 '23 at 13:55
  • @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? – Ilya Lakhin Apr 12 '23 at 15:21
  • 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. – Pseudonym Apr 13 '23 at 08:44
  • @Pseudonym Also, if I introduce multi-start Automata, how do I merge it back in the end to obtain canonical DFA? – Ilya Lakhin Apr 13 '23 at 12:01
  • 1
    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. – Pseudonym Apr 13 '23 at 14:35

1 Answers1

4

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.

Ilya Lakhin
  • 171
  • 6