舉例說明如何將NFA轉換為DFA。

問題

將以下非確定性有限自動機 (NFA) 轉換為確定性有限自動機 (DFA)。

解決方案

狀態轉換圖如下：

NFA 的狀態轉換表如下：

DFA 表不能有多個狀態。因此，將 q0q1 作為一個單一狀態。

讓我們透過將兩個狀態視為一個狀態來將給定的 NFA 轉換為 DFA。

DFA 的狀態轉換表如下：

在上表中，q2 是最終狀態。無論哪裡出現 q2，都將其視為最終狀態。

注意：

• 轉換後，最終 DFA 中的狀態數量可能與 NFA 中的狀態數量相同，也可能不同。
• DFA 中狀態的最大數量可能是 2 的 (NFA 中狀態數量) 次冪。
• NFA 和 DFA 中狀態數量之間的關係為：1<=n<=2^m

  其中 n = DFA 中的狀態數量

  m = NFA 中的狀態數量

• 最終 DFA 中包含 NFA 最終狀態的所有狀態都被視為最終狀態。

Bhanu Priya

更新於：2021年6月12日

3K+ 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習