在 DFA 中,我们可以通过对两个自动机的状态进行叉积并接受在两个初始自动机中都接受的那些状态来进行两个自动机的交集。
联合执行类似。尽管我可以使用 epsilon 转换轻松地在 NFA 中进行联合,但我如何进行它们的交集?

最佳答案

您可以像使用 DFA 一样在 NFA 上使用跨产品构造。唯一的变化是您如何处理 ε 转换。具体来说,对于叉积自动机中的每个状态 (qi, rj),您添加从该状态到每对状态 (qk, rj) 的 ε-转换,其中第一台机器中存在从 qi 到 qk 的ε-转换以及每对状态 (qi, rk) 在第二台机器中存在从 rj 到 rk 的 ε 转换。

或者,您始终可以将 NFA 转换为 DFA,然后计算这些 DFA 的叉积。

希望这可以帮助!

关于algorithm - 如何找到两个NFA的交集,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21662041/

10-13 00:05