读书人

有没有把多个DFA合并成一个DFA的算法?

发布时间: 2012-02-10 21:27:42 作者: rapoo

有没有把多个DFA合并成一个DFA的算法?
算法可以把多个DFA直接合并成一个DFA,或者把多个DFA合并成一个NFA,然后再将这个NFA转化成DFA。谢谢!

[解决办法]
应该可以,
先把起点 S合并成一个 状态,

1。对任意一个新状态,让后对接受串q,进行的动作,把所有接受字符q的状态合并,
2。产生到1个新状态
3。goto 1。直到不能在合并。

对所有包含终结符的新状态,都标示为终结态。

这样就变成了1个DFA,还可以变成最小DFA。



[解决办法]
把多个DFA合并成一个NFA,然后再将这个NFA转化成DFA。
----------------------------------------

lz不是已经说出算法来了吗

读书人网 >软件架构设计

热点推荐