# Brzozowski's algorithm for Kleene star NFA

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): 1. I'm reversing it. 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: 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. 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. But this DFA is not minimal. Can you explain me, please, where did I make a mistake?

Ilya.

• 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. Apr 12 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? Apr 12 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. Apr 13 at 8:44
• @Pseudonym Also, if I introduce multi-start Automata, how do I merge it back in the end to obtain canonical DFA? Apr 13 at 12:01
• 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. Apr 13 at 14:35