如何求有限自动机DFA与NFA的交集
给出已有的DFA P=(Qp,Σp,δp,Fp)和NFA D=(Qd,Σd,δd,Fd),请问如何能够求出DFA与NFA的交集?
其中,Σ是字母集合,Q是有限状态的集合,F是终止状态集合,δ是状态转移函数。
这是小弟毕业设计的内容,卡在这里好久了,哪位大侠能够给点意见或者提示,非常感谢!
[解决办法]
我想除了一个办法。
你可以先将NFA转化为DFA,记作DFA1,这时候,DFA1的状态集合中与DFA中的Q相同。
然后根据两个DFA,我们可以画出两个图,然后取两个图中的交集。(即:(a,b)线都出现在两个DFA图中)
具体方法是:将两个图映射成两个邻接矩阵,其中矩阵中的值为从某个状态到达另外一个状态的字母。
这时候,我们可以比较两个矩阵,然后去矩阵中相同的值就可以了。
[解决办法]
NFA,不是可以等同转换为DFA么?
那么什么叫他们的交集?
我对这个不了解。顶