将Epsilon-NFA转换为NFA

Question

我在理解将epsilon-NFA转换为NFA的过程中遇到了问题，所以我想知道是否有人可以帮助我：

​

​

答案是：

​

​

新的NFA中的0有一个A到1,2和2。我认为这是因为在Epsilon NFA中的0导致1和2与A(与Epsilon组合)。那么，为什么1,2没有A步到2，因为在Epsilon NFA中，1有A步到1和2？

Answer 1

无论何时从NFA中删除ε，都应该在转换ε转换的方向时小心。

在您的例子中，ε转换是从节点1到节点2，这是一个accept状态。因此，您需要考虑到状态1的所有传入转换。

此外，随着{1}在ε转换时移动到{2}，因此1也可以减少到{1,2}，并且它将是接受状态。检查this question以了解发生这种情况的原因。

因此，为了删除ε-transition，检查所有进入状态1的转换，用accept状态{ 1，2}替换{1}，并转换它们:-

1. 状态0在读取a时转换为状态1，状态1在读取a时自动转换为状态2

因此，您应该省略从1到2(ε-transition)的路径，并说明读取a时的状态0同时转换为{1}和{2}。因此，只有1个转换将被添加到现有的NFA中

{0} -> {2} (on reading a)    // should be drawn, not given
{0} -> {1} (on reading a)    // this is already given

1. 状态2在读取a时转换为状态1，而状态1在读取a时将自动转换为状态2

因此，您应该省略从1到2(ε-transition)的路径，并说明读取a时的状态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

由于上述原因，请特别注意将状态{1}替换为接受状态{1,2}。

没有更多指向状态1的传入箭头，因此解决了所有依赖关系。新的NFA匹配您给定的NFA作为答案。