what is the McNaughton-Yamada Algorithm?

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 Reg开发者_如何学运维Ex 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

---

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.

---

"...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

---

Their algorithm isn't usually brought up separate from Thompson's work. Thompson's original went from a regular expression to a simulated NFA in memory. The Thompson-McNaughton-Yamada algorithm is an extension that turns the regex into an actual NFA stored in memory, as opposed to a transient simulation.

Converting the NFA to a DFA (determinization) is not part of McNaughton or Yamada's extension. Rather, it's done via the subset construction (aka powerset construction) algorithm.

You can see Thompson-McNaughton-Yamada algorithm and subset construction algorithm in action on arbitrary regular expressions by using the Compiler Construction Toolkit's regular expression to NFA and DFA tool.