Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
should be noted this was cross-posted to Stack Overflow:… – Jan Dvorak Aug 4 '13 at 5:17
I've purchased the paper and intend to describe the algorithm once I've thoroughly studied it. – Brent Aug 4 '13 at 16:46
Good idea. Don't forget to update the cross-post as well. – Jan Dvorak Aug 4 '13 at 17:13

I've implemented it here: See Nfa.Minimized

share|cite|improve this answer
plz at least state the language. – vzn Sep 25 '13 at 15:21
Apologies. It's in C#. – Brent Sep 25 '13 at 22:15
what/where is Nfa.Minimize? is there any descr anywhere? – vzn Sep 25 '13 at 22:56
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. – Brent Sep 26 '13 at 2:12
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. – Brent Sep 26 '13 at 2:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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