将Epsilon-NFA转换为NFA [英] Converting Epsilon-NFA to NFA

问题描述

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

I'm having trouble understanding the process of converting an epsilon-NFA to a NFA, so I wondered if anybody could help me with it:

答案是:

新NFA中的0的A分别为1,2和2.我认为这是因为Epsilon NFA中的0导致1和2带有A(与Epsilon结合使用).那么为什么1,2为何没有A步到2，因为在Epsilon NFA中1却有A步到1和2?

The 0 in the new NFA has an A going to 1,2 and to 2. I figured this is because the 0 in the Epsilon NFA leads to 1 and 2 with an A (combined with an Epsilon). So why doesn't the 1,2 have an A-step going to 2, because in the Epsilon NFA the 1 has an A-step to 1 and 2?

推荐答案

每当从NFA中删除ε时，在转换时都应注意ε过渡的方向.

Whenever you remove an ε from the NFA, you should be careful at the time of conversion for the direction of ε transition.

在您的情况下，ε过渡是从节点1到节点2，这是一个 接受状态.因此，您需要考虑所有传入的过渡到 状态1.

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.

此外，由于ε转换时{1}移至{2}，因此1也可以减小为{1,2}，并且它将是接受状态.查看此问题，以了解为什么会发生这种情况

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.

因此，要删除ε-transition，请检查进入状态1的所有传入转换，将{1}替换为接受状态{1,2}并进行转换:-

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时将转换为状态1，并且状态1在读取ε时将自动转换为状态2.

1. State 0 transits to state 1 when it reads a, and state 1 will automatically transit to state 2 as it reads ε.

因此，您应该忽略从1到2(ε跃迁)的路径，并说在读取到{1}和{2}的跃迁时状态0.因此，只会以

So, you should omit this path from 1 to 2(of ε-transition), and say that state 0 on reading a transits to both {1} and {2}. So, only 1 transition will be added to the exisitng NFA as

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

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

1. State 2 transits to state 1 when it reads a, and state 1 will automatically transit to state 2 as it reads ε.

因此，您应该忽略从1到2(ε跃迁)的路径，并说在读取跃迁到{1}和{2}本身时的状态2.因此，仅会向

So, you should omit this path from 1 to 2(of ε-transition), and say that state 2 on reading a transits to both {1} and {2}, itself. So, only 1 transition will be added to the exisitng NFA as

{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}.

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相匹配.

There are no more incoming arrows directed to state 1 and hence all the dependencies are resolved. The new NFA matches your given NFA as the answer.

这篇关于将Epsilon-NFA转换为NFA的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！