如何找到两个NFA的交点 [英] How to find the intersection of two NFA

问题描述

在DFA我们可以做两个自动机的状态的交叉产品，并接受所接受同时在最初的自动机的状态做两件自动机的交集。 联盟同样进行。如何过，虽然我可以在NFA做工会很容易地使用小量的过渡我该怎么做他们的交集？

In DFA we can do the intersection of two automata by doing the cross product of the states of the two automata and accepting those states that are accepting in both the initial automata. Union is performed similarly. How ever although i can do union in NFA easily using epsilon transition how do i do their intersection?

推荐答案

您可以使用跨产品结构上的NFAS就像你的DFA。唯一的变化是你如何处理与小量; -transitions。从该状态 - 过渡到每对状态（Q;具体而言，对于每一个国家（Q <子>我，R <子>Ĵ）在跨产品自动机，您添加和小量<子> K ，R <子>Ĵ），其中有一个与小量;转变点在第一台机器从q <子>我为q <子> K <子/>并且每对状态（Q <子>我，R <子> K ），其中有一个与小量;转变点的第二台机器从研发<子>Ĵ于r <子> K 。

You can use the cross-product construction on NFAs just as you would DFAs. The only changes are how you'd handle ε-transitions. Specifically, for each state (q_i, r_j) in the cross-product automaton, you add an ε-transition from that state to each pair of states (q_k, r_j) where there's an ε-transition in the first machine from q_i to q_k and to each pair of states (q_i, r_k) where there's an ε-transition in the second machine from r_j to r_k.

另外，你也可以转换的NFA到DFA的，然后计算这些的DFA的叉积。

Alternatively, you can always convert the NFAs into DFAs and then compute the cross product of those DFAs.

希望这有助于！

这篇关于如何找到两个NFA的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！