I found the paper "On the State Minimization of Nondeterministic Finite Automata" which, I assume, contains the Kameda-Weiner algorithm that I've been searching for. It's behind a paywall though. I'm just a hobbyist. Can someone explain it, or point me to another source?


I've implemented it here: https://github.com/coder0xff/parlex_legacy/blob/132e4a23a599140d22b18ead832626f0c607340f/Automata/NFA.cs#L641

I've never gotten around to describing it, but to be brief, it's very involved. The only way to gain a useful understanding of the algorithm is to read the paper start to finish.

| cite | improve this answer | |
  • $\begingroup$ Apologies. It's in C#. $\endgroup$ – Brent Sep 25 '13 at 22:15
  • $\begingroup$ what/where is Nfa.Minimize? is there any descr anywhere? $\endgroup$ – vzn Sep 25 '13 at 22:56
  • $\begingroup$ The name is Minimized. It's in the linked file near the bottom. As for a description, a paper is required to explain it. It has no documentation as it is a component of a larger project, but in short, create an NFA and add states. Also add some of the state's to the StartState and AcceptState members. Add entries to the transitionfunction member and you have an nfa. Call Minimized on it and it'll return a new NFA. $\endgroup$ – Brent Sep 26 '13 at 2:12
  • $\begingroup$ It's a bit slow for anything more than a few states, since it is np-hard after all, but I plan on adding some optimizations in the near future. Note that currently this is state minimization, and the number of transitions may not be minimal, but it's fairly easy and I'll be extended it to do so as well. $\endgroup$ – Brent Sep 26 '13 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.