I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter. My problem is that I cannot access any actual reference on the algorithm. Their original paper is behind a paywall at IEEE that my university does not have access to.

The algorithm went something like this: 1. For each symbol in the expression, given them a subscript from left to right increasing by one for each instance of that symbol. For example, the expression, aa* would receive a_1 a_2^*.

  1. We proceed to construct a diagram based on the possible lengths of words.

If done appropriately, this produces a DFA. I think the labeling in (1) is to help label the states.

Feel free to come up with your own example if you decide to give an answer. I won't provide any problem here because there is no guarantee that it isn't actually my homework exercise.

  • $\begingroup$ According to this answer and this paper, the McNaughton–Yamada algorithm produces an NFA rather than a DFA. If you want a DFA, you can determinize your NFA. $\endgroup$ – Yuval Filmus Mar 24 at 11:20
  • $\begingroup$ In addition, if course materials aren't enough to do the homework, then (unless it's an advanced class) there is something profoundly wrong going on. $\endgroup$ – Yuval Filmus Mar 24 at 11:21
  • $\begingroup$ See this (French but detailed) Wikipedia entry. $\endgroup$ – J.-E. Pin Oct 16 at 13:20

Your Answer

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

Browse other questions tagged or ask your own question.