Is there a way to test if two NFAs accept the same language?
The decision problem is PSPACE-complete as Shaull noted.

However, it turns out that in practice it is often possible to decide NFA equivalence reasonably quickly.  Mayr and Clemente (based on experimental evidence) claim that the average-case complexity scales quadratically.  Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions.

Just like SAT is NP-complete in a worst-case analysis, yet often turns out surprisingly tractable for real-world instances, it therefore seems likely that NFA equivalence can be decided efficiently for many real-world instances.


Richard Mayr and Lorenzo Clemente, Advanced automata minimization, POPL 2013, doi:10.1145/2429069.2429079 (preprint)