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, anddoing powerset construction to get $G_{\min}$.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?
Brzozowski's algorithm for DFA minimization
algorithms;finite automata;runtime analysis