NFA minimization without determinization

Question

It is well-known how one gets from an NFA for a regular language to a minimal DFA. However, the DFA might have an exponentially larger number of states.

What I need is a way to reduce an NFA, giving again an NFA but with a smaller number of states. T.i. I don't need the result to be deterministic, but I'd like it to be as small as possible while preserving the recognized language (perhaps not absolutely optimal, but the smaller, the better).

What are the best algorithms for this problem? Or perhaps not "the best" but at least "the easiest to implement with non-abysmal efficiency"? Or does the problem have a well-known name so that I could find good sources of information myself?

Answer 1

I believe the problem is just known as NFA minimisation as well. It's NP-hard in general, I believe.

One fruitful approach may be Bisimulation Minimization [Paige, Tarjan 1987], and subsequent derivatives.

This presentation has some notes on the tractability of the problem as well as references to some approaches with their relative merits spelled out.