求救!!!高程第二章中的由NFA转化为DFA的那个算法怎么理解?
大家好:
我今年报了高程,希望能和大家多多交流!!!那个算法怎么去理解呢?书上说的我怎么样都不明白,来帮帮我好吗?有1百分资奖励:)我的QQ:155357455
问题点数：0、回复次数：7Top
1 楼dreamsea（留刘）回复于 2003-08-03 20:19:39 得分 0
参考一下机械工业出版社的《编译原理》Top
2 楼yourongxin（）回复于 2003-08-03 20:29:21 得分 0
编译原理好难啊！晕！Top
3 楼Hiei1234（飞影）回复于 2003-08-04 05:31:00 得分 0
方法是通过推导状态转换矩阵表去除ε-连接
先用推倒产生由ε-连接而出现的状态集为初态，在经过的字符上直至推导到没有新的状态集出现为止。
如有新的状态集出现则把它作为下一次推导的初始状态。
（也就是用一个状态集表示一个状态）（参照高程考纲103页例题）
1．从0状态出发经过ε可达到的状态状态有0->1->2;0->1->4;0->7;(注意：ε+ε=ε）
所以初始状态集为{0,1,2,4,7}。
2．然后用{0,1,2,4,7}推导经过a可达到的状态状态有哪些，初态里在2上有2-a->3和在7上有7-a->8,然后从3出发可到达的状态为6,7,1,2,4;从8状态出发不能到达任何状态所以此状态集为{1,2,3,4,6,7,8}也就是例题中表2.1里的第一个Ia，同理然后再考虑经过b可到达的状态为{1,2,4,5,6,7}此为第一个Ib（注意：a+ε=a；b+ε=b，在考虑a时不考虑b，同理考虑b时也不考虑a）。
3．由于以上Ia和Ib都是新状态所以要把它们作为下一次推导的初态（见P104表2.1的2,3行）。
4．重复以上2,3两步直到没有新的状态集出现为止。
5．把所有不同的状态集看成不同的状态（例如：由于{0,1,2,4,7}是初态而看成是０状态
所有的状态都在表2.1的第一列按从上到下为０,1,2,3,4）然后利用推导时产生的关系将它们连接起来就成为了图2.14的样子。(注意：含有ＮＦＡ中终态那个状态集为ＤＦＡ的终态）
6.如果有必要要将其化简（由于无法贴图，请你自己看考纲105页的消结规则）
Top
4 楼smuwcwt（Lotus/Domino）回复于 2003-08-04 12:21:05 得分 0
书上写得很清楚呀，我看了几遍就懂了，你哪里看不懂写仔细点呀。Top
5 楼zhangjianwxh（头顶地）回复于 2003-08-04 17:54:18 得分 0
好了好了，我来收分了，你去老顽童网站看一看吧！那里关于软件设计的资料好多啊！
http://oldchild.nbc.net.cn
记得去看看哦，不要错过好机会。Top
6 楼koji1314520（蓝色幽灵精）回复于 2003-08-04 18:03:14 得分 0
飞影兄:
十分感谢,接受分吧.其它的哥们不好意思啦,分数有限,下次给啦.希望我们以后能多多交流,谢谢你们啦我的QQ155357455有机会的话我们一起在网上聊好吗?一起去提高,一起去PASS!!!Top
7 楼koji1314520（蓝色幽灵精）回复于 2003-08-04 18:15:52 得分 0
http://expert.csdn.net/Expert/topic/2103/2103907.xml?temp=.1226618
是我说的这个吗?看看吧有高人解释了:)Top
