Adi*_*iar 4 algorithm intersection finite-automata dfa nfa
在DFA中,我们可以通过执行两个自动机状态的交叉乘积并接受在初始自动机中接受的那些状态来完成两个自动机的交集.联盟的表现同样如此.虽然我可以轻松地使用epsilon过渡在NFA中进行联合,但我如何做他们的交集呢？
您可以像使用DFA一样在NFA上使用跨产品构造.唯一的变化是你如何处理ε-过渡.具体而言,对于每个状态(Q 我,R Ĵ在跨产品自动机),就从该状态添加ε -过渡到每对状态(Q ķ,R Ĵ),其中有一个在所述第一机器的ε -过渡从q i到q k以及每对状态(q i,r k),其中在第二机器中从r j到r k存在ε-转变.
或者,您始终可以将NFA转换为DFA,然后计算这些DFA的交叉乘积.
希望这可以帮助!