我无法理解将 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 步?
我无法理解将 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 步?
每当您ε
从 NFA 中删除一个时,您应该在转换时小心转换方向ε
。
在您的情况下,ε 转换是从节点 1 到节点 2,这是一个接受状态。因此,您需要考虑到状态 1 的所有传入转换。
此外,当 {1} 在 ε 转换时移动到 {2},所以 1 也可以减少到 {1,2} 并且它将是一个接受状态。检查此问题以了解为什么会发生这种情况。
因此,为了移除 ε-transition,检查所有进入状态 1 的转换,将 {1} 替换为接受状态 {1,2} 并转换它们:-
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
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 作为答案。