我无法理解将 epsilon-NFA 转换为 NFA 的过程,所以我想知道是否有人可以帮助我:
答案是:
新 NFA 中的 0 有一个 A 通向 1,2 和 2。我认为这是因为 Epsilon NFA 中的 0 通过 A 通向 1 和 2(与 Epsilon 组合)。那么为什么 1,2 没有一个到 2 的 A 步,因为在 Epsilon NFA 中 1 有一个到 1 和 2 的 A 步?
最佳答案
每当您从 NFA 中删除 ε
时,您在转换时都应该小心 ε
转换的方向。
In your case, the ε transition is from node 1 to node 2, which is an accept state. So, you need to consider all the incoming transitions to the state 1.
Also, as {1} moves to {2} upon ε-transition, so 1 can also be reduced to {1,2} and it'll be an accept state. Check this question to know why this happens.
So, for removal of ε-transition, check all the incoming transitions to state 1, replace {1} with accept state {1,2} and convert them :-
- 状态 0 在读取
a
时转换为状态 1,状态 1 在读取ε
时自动转换为状态 2。
因此,您应该省略从 1 到 2(ε-转移)的这条路径,并说读取转移时状态 0 会同时转移到 {1} 和 {2}。因此,只有 1 个转换将被添加到现有 NFA 中,如下所示
{0} -> {2} (on reading a) // should be drawn, not given
{0} -> {1} (on reading a) // this is already given
- 状态 2 在读取
a
时转换为状态 1,状态 1 在读取ε
时自动转换为状态 2。
因此,您应该省略从 1 到 2(ε-转移)的这条路径,并说读取转移时的状态 2 本身会转移到 {1} 和 {2}。因此,只有 1 个转换将被添加到现有 NFA 中,如下所示
{2} -> {2} (on reading a) // a self-loop, should be drawn, not given
{2} -> {1} (on reading a) // this is already given
Please take special care that you replace the state {1} with the accept state {1,2} because of the reason explained above.
不再有指向状态 1 的传入箭头,因此所有依赖关系都已解决。新的 NFA 与您给定的 NFA 作为答案相匹配。
关于state - 将 Epsilon-NFA 转换为 NFA,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31120670/