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:
- Reverse the NFA.
- Transform to DFA.
- Reverse DFA.
- 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):
I'm reversing it.
Turning reversed NFA to DFA using the Powerset approach.
- The init state
3
Epsilon-closure is{1, 2, 3}
. - Closure
{1, 2, 3}
transits byA
to{1, 2}
. - Closure
{1, 2}
transits byA
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 state3
. This is clearly a DFA that reads the reversed language which is equal in this case to original oneA*
. There are redundant states, but I assume it does not contradict the Algorithm requirements.- The init state
Reverse it again.
Turning to DFA again.
- The init state
3
Epsilon-closure is{1, 2, 3}
. - Closure
{1, 2, 3}
transits byA
to{1, 2}
. - Closure
{1, 2}
transits byA
to{1, 2}
.
New closure-states and the topology of the final Automata are the same as on step 2.
- The init state
But this DFA is not minimal. Can you explain me, please, where did I make a mistake?
Thanks in advance!
Ilya.