使用Pair Table方法減少DFA

我正在學習如何使用Pair Table方法（系統縮減方法）來減少DFA的使用次數。這裏是我們希望減少的DFA。使用Pair Table方法減少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}

我們並不需要包括空集的狀態，我想。

現在，這裏是我困惑的地方，我需要通過狀態列表並標記它們。我不知道如何繼續。

來源

2015-09-24 Talen Kylon

首先，您擁有的表格與DFA不匹配。

對錶方法使用等價類。首先我們將州劃分爲兩個：最終狀態和非最終狀態。最初，每個最終狀態都可以與任何非最終狀態區分開來。所以你應該創建一個如下所示的表格，並且標記爲(q0,q1)和(q1,q2)，因爲q1是最終的，但q0和q2是非最終狀態。

+----+ | q0 | +----+----+ | q1 | x | +----+----+----+ | q2 | | x | +----+----+----+----+ | q0 | q1 | q2 | +----+----+----+

然後反覆，你繼續使用下面的規則標記和當在迭代沒有什麼改變，止損：

馬克(q_i,q_j)如果由於某些字母符號，標記。 Int上表中，和。由於(q1,q2)被標記，我們也應該標記(q0,q2)。請注意，我們只有一半的表格。因此，(q0,q2)=(q2,q0)。

+----+ | q0 | +----+----+ | q1 | x | +----+----+----+ | q2 | x | x | +----+----+----+----+ | q0 | q1 | q2 | +----+----+----+

來源

2016-10-28 17:56:15

使用Pair Table方法減少DFA

回答

相關問題