Hopcroft and Karp's algorithm for Non-deterministic Finite Automata
Filippo Bonchi, Damien Pous · 2011
An algorithm is given for determining if two non-deterministic finite automata are language equivalent. We exploit up-to techniques to improve the standard algorithm by Hopcroft and Karp for deterministic finite automata, so as to avoid computing the whole deterministic automata. Although the proposed algorithm remains exponential in worst case (the problem is PSPACE-complete), experimental results show that it can be much faster than the standard algorithm: only a very small portion of the determinized automata have to be explored in practice.