what is the McNaughton-Yamada Algorithm?

Question

I am needing to construct a DFA using the McNaughton-Yamada algorithm for a CS class. The problem is the algorithm is supplemental material and I am not clear on what it is exactly. Is it a method for finding a DFA given a RegEx or is finding the DFA plus minimizing it? I can't seem to find any info on the subject.

I am confused because the minimization routine my instructor showed after we found the DFA in class doesn't seem any different than the 'mark' minimization described in our book.

Thanks for your reply,

Nathan

Answer 1

There is a description of the algorithm (for regular expression to NFA and NFA to DFA) at http://swtch.com/~rsc/regexp/regexp1.html; they show Thompson's version, and claim that the McNaughton-Yamada algorithm is basically the same, but generating a DFA directly from the regular expression.

Answer 2

"...the McNaughton-Yamada analysis algorithm, whereby a regular expression is found describing the words accepted by a finite state machine whose transition table is given. Unmodified the algorithm will produce 4n terms representing an n-state machine. This number could be reduced by eliminating duplicate calculations and rejecting ona high level expressions corresponding to no possible path in the same state diagram. The remaining expressions present a serious simplification problem, since empty expressions and null words are generated liberally by the algorithm."

Source