Minimalizacja NFA bez determinacji

Question

Dobrze wiadomo, w jaki sposób uzyskuje się od NFA zwykłego języka do minimalnego DFA. Jednak DFA może mieć wykładniczo większą liczbę stanów.

Potrzebuję sposobu na zredukowanie NFA, ponownie dając NFA, ale z mniejszą liczbą stanów 10. T.i. Nie potrzebuję tego, by wynik był deterministyczny, ale chciałbym, aby był tak mały, jak to możliwe, zachowując uznany język (być może nie jest absolutnie optymalny, ale mniejszy, tym lepszy).

Jakie są najlepsze algorytmy dla tego problemu? A może nie "najlepszy", ale przynajmniej "najłatwiejszy do wdrożenia z nie-fatalną wydajnością"? Czy problem ma znaną nazwę, aby samemu znaleźć dobre źródła informacji?

Answer 1

Wierzę, że problem ten jest znany również jako minimalizacja NFA. Uważam, że generalnie jest NP-trudny.

Jednym z owocnych podejść może być Minimizacja Bisimulation [Paige, Tarjan 1987], a następnie pochodne.

This presentation ma kilka uwag na temat łatwości obsługi problemu, jak również odniesień do niektórych podejść z ich względnymi zaletami.

Answer 2

Jest to implementacja algorytmu Kameda-Weiner dla NFA minimalizacji tutaj: https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs