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^*.
- 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.