Nat*_*ann 2 algorithm computer-science finite-automata dfa
我需要使用McNaughton-Yamada算法为CS类构建DFA.问题是算法是补充材料,我不清楚它究竟是什么.这是一种在给定RegEx的情况下查找DFA还是找到DFA并将其最小化的方法？我似乎无法找到有关该主题的任何信息.
我很困惑,因为我们的教师在课堂上发现DFA后所显示的最小化程序似乎与我们书中描述的"标记"最小化没有任何不同.
感谢您的回复,
弥敦道
在http://swtch.com/~rsc/regexp/regexp1.html上有对该算法的描述(用于正则表达式为NFA,NFA为DFA); 他们展示了Thompson的版本,声称McNaughton-Yamada算法基本相同,但直接从正则表达式生成DFA.