Brzozowski\'s DFA minimization algorithm builds a minimal DFA for DFA G by: reve

Question

Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA G by:

reversing all the edges in G, making the initial state an accept state, and the accept states initial, to get an NFA N? for the reverse language,
using powerset construction to get G? for the reverse language,
reversing the edges (and initial-accept swap) in G? to get an NFA N for the original language, and
doing powerset construction to get Gmin.

Of course, since some DFA's have an exponential large reverse DFA, this algorithm runs in exponential time in worst case in terms of the size of the input, so lets keep track of the size of the reverse DFA.

If N is the size of the input DFA, n is the size of the minimal DFA, and m the size of the minimal reverse DFA, then what is the run time of Brzozowski's algorithm in terms of N,n, and m?

In particular, under what relationship between n and m does Brzozowski's algorithm outperform Hopcroft's or Moore's algorithms?

I have heard that on typical examples in practice/application, Brzozowski's algorithm outperforms the others. Informally, what are these typical examples like?

Explanation / Answer

Here's partial answer regarding your third question. In fact, perhaps Brzozowski's algorithm really doesn't outperform all the other algorithms so clearly in DFA minimization.

In [1], the authors investigate the practical performance of DFA/NFA minimization algorithms. The algorithms are Hopcroft's, Brzozowski's, and two variants of Watson's. They conclude that there's no clear winner, but Hopcroft's algorithm performs better for DFAs with small alphabets. For NFAs, Brzozowski is clearly the fastest one.

The paper itself is quite short and clearly written. There's also additional discussion and references that might be helpful.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.