automata - 使用配对表方法减少DFA

我正在学习使用配对表方法(系统化还原方法)减少DFA的方法。以下是我们要减少的DFA。

第一步是在表格中布置DFA:

                                    0           1
             q0                  {q0, q3}      {q1}
             q1                    {q2}        {q2}
             q2                  EmptySet      {q2}
          {q0, q1}             {q0, q1, q3}    {q1, q2}
          {q1, q2}                 {q2}        {q2}
        {q0, q1, q2}           {q0, q1, q2}    {q1, q2}

我认为我们不需要包括空集状态。

现在这是我感到困惑的地方，我需要浏览状态列表并根据某些内容对其进行标记。我不确定如何进行。

最佳答案

首先，您拥有的表格与DFA不匹配。

配对表方法使用等效类。首先，我们将状态分为两个状态:最终状态和非最终状态。最初，每个最终状态都可以与任何非最终状态区分开。因此，您应该创建一个如下所示的表，并将(q0,q1)和(q1,q2)标记为q1是最终状态，而q0和q2是非最终状态。
+----+| q0 |+----+----+| q1 | x |+----+----+----+| q2 | | x |+----+----+----+----+ | q0 | q1 | q2 | +----+----+----+
然后，反复使用以下规则进行标记，并在迭代中未进行任何更改时停止:

如果某个字母符号a被标记为，则标记(q_i,q_j)。表格上面的int，和。标记了(q1,q2)后，我们也应该标记(q0,q2)。请注意，我们只有表格的一半。因此，(q0,q2)=(q2,q0)。
+----+| q0 |+----+----+| q1 | x |+----+----+----+| q2 | x | x |+----+----+----+----+ | q0 | q1 | q2 | +----+----+----+

关于automata - 使用配对表方法减少DFA，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32768647/