Minimisation NFA sans déterminisation

Question

Il est bien connu comment on obtient d'un NFA pour un langage régulier à un DFA minimal. Cependant, le DFA peut avoir un nombre exponentiel d'états. Ce dont j'ai besoin est un moyen de réduire un NFA, en donnant à nouveau un NFA mais avec un plus petit nombre d'états de. T.i. Je n'ai pas besoin que le résultat soit déterministe, mais j'aimerais qu'il soit aussi petit que possible tout en préservant le langage reconnu (peut-être pas absolument optimal, mais le plus petit, le mieux).

Quels sont les meilleurs algorithmes pour ce problème? Ou peut-être pas "le meilleur" mais au moins "le plus facile à mettre en œuvre avec une efficacité non abyssale"? Ou le problème a-t-il un nom bien connu pour que je puisse trouver moi-même de bonnes sources d'information?

Answer 1

Je crois que le problème est également connu comme la minimisation NFA. C'est NP-difficile en général, je crois.

Une approche fructueuse peut être la minimisation de la bisimulation [Paige, Tarjan 1987], et les dérivés subséquents.

This presentation a quelques notes sur la facilité de traitement du problème ainsi que des références à certaines approches avec leurs mérites relatifs énoncés.

Answer 2

Il y a une implémentation de l'algorithme Kameda-Weiner pour la minimisation NFA ici: https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs