what is the McNaughton-Yamada Algorithm?

algorithm computer-science finite-automata dfa
Nathan Schwermann picture Nathan Schwermann · Mar 10, 2011 · Viewed 7.6k times · Source

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

Jeremiah Willcock picture Jeremiah Willcock · Mar 10, 2011

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.

Related questions

What is a plain English explanation of "Big O" notation?

I'd prefer as little formal definition as possible and simple mathematics.

Read More
How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

Read More
What exactly does big Ө notation represent?

I'm really confused about the differences between big O, big Omega, and big Theta notation. I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent? I have …

Read More