转换给定的NFA

Question

问题)Σ={a，b}和NFA如下图所示：

1. 使用过程NFA到DFA，将给定的NFA转换为DFA。
2. 使用还原过程，将DFA中的状态最小化。

​

我为nfa和dfa做了一个转换表，但是不知道q2应该去哪里，或者是q0，或者创建一个名为q4的新状态

Answer 1

我们可以使用子集(或powerset)构造从NFA到DFA，方法是将NFA的状态子集考虑为相应DFA的潜在状态。DFA的初始状态为{ q0 }，这意味着在读取任何输入之前只能到达q0。在读取了a从{ q0 }，我们可以到达q2通过消费a，然后再q0通过进行lambda转换。因此，f({q0}，a) = {q0，q2}。在{q0}中读取b时，我们只能去q1；所以f({q0}，b) = {q1}。

我们在DFA中引入了两个新的状态，{q0，q2}和{q1}，我们需要对它们进行转换。片刻的反思将显示{q0、q2}具有与{q0}完全相同的转换。在输入a中，q1可以转到q1、q2或q0 (通过q2)；在输入b上，它可以转到q2或q0 (通过q2)。因此，f({q1}，a) = {q0，q1，q2}和f({q1}，b) = {q0，q2}。

我们已经看到了{q0，q2}，并且知道它的过渡。但是，我们现在需要{q0、q1、q2}的转换。在输入a上，NFA的所有状态都可以从某种状态到达；输入b也是如此。So，f({q0，q1，q2}，a) = {q0，q1，q2}和f({q0，q1，q2}，b) = {q0，q1，q2}。

我们没有在这个迭代中引入任何新的状态，所以在DFA中我们有可能需要的所有状态。我们的DFA是这样的：

q            s    q'
{q0}         a    {q0, q2}
{q0}         b    {q1}
{q0, q2}     a    {q0, q2}
{q0, q2}     b    {q1}
{q1}         a    {q0, q1, q2}
{q1}         b    {q0, q2}
{q0, q1, q2} a    {q0, q1, q2}
{q0, q1, q2} b    {q0, q1, q2}

除了{q1}之外，所有的状态都是接受的，因为它们都包含来自NFA的接受状态q0。现在，在我们最小化这个DFA之前，让我们重新命名以下状态：

qA = {q0}
qB = {q0, q2}
qC = {q1}
qD = {q0, q1, q2}

我们可以迭代地删除不能按以下方式组合的状态对：

   qA,qB    qA,qC    qA,qD    qB,qC    qB,qD    qC,qD
   --------------------------------------------------
1.          xxxxx             xxxxx             xxxxx
Reason: qC cannot be combined with others since it is
        not accepting and the others are

2.                   xxxxx             xxxxxx
Reason: f((qA, qD), b) and f((qB, qD), b) equal (qC, qD)
        which was crossed off during the last iteration.

qA,qB cannot be crossed off, so these states can be
combined in a minimal DFA.

由此产生的最低DFA是：

q            s    q'
qAB          a    qAB
qAB          b    qC
qC           a    qD
qC           b    qAB
qD           a    qD
qD           b    qD