将 Epsilon-NFA 转换为 NFA

Question

我无法理解将 epsilon-NFA 转换为 NFA 的过程，所以我想知道是否有人可以帮助我：

答案是：

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

Answer 1

每当您从 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 :-

1. 状态0读到a时状态0转换到状态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. 状态2读到a时状态2转换到状态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 作为答案匹配。