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?

Ytterbia

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.

Nerin

Thanks, I was able to find quite relevant material by following references from the article you mentioned. – Ytterbia

The problem isn't just NP-hart, it's PSPACE-hard! – Oestriol

Can you give the title of the presentation so that it can be found by searching? The link returns a zero-page PDF currently. – Starnes

Answer 2

There's an implementation of the Kameda-Weiner algorithm for NFA minimization here: https://github.com/coder0xff/parlex_legacy/blob/132e4a23a599140d22b18ead832626f0c607340f/Automata/NFA.cs#L641

Schorl