如何在理論計算機科學（TOC）中將NFA轉換為DFA？

在非確定性有限自動機中，對於任何當前狀態和輸入符號，都存在多個下一個輸出狀態。

當且僅當存在至少一條從初始狀態開始並以最終狀態結束的轉換路徑時，字串才會被接受。

以下步驟用於將給定的 NFA 轉換為 DFA：

演算法

步驟 01

• 讓我們將“q”作為 DFA 的一組新狀態。它最初被宣告為空。
• 讓我們將 T’ 作為 DFA 的一個新的轉換表。

步驟 02

• 將 NFA 的起始狀態新增到 q’ 中。
• 從起始狀態新增轉換到 T’ 中。
• 如果起始狀態對於某些輸入字母表具有到多個狀態的轉換，則在 DFA 中將這些多個狀態作為單個狀態接受。

步驟 03

如果 T’ 中存在任何新狀態，

• 將新狀態新增到 q’ 中。
• 在轉換表 T’ 中新增狀態的轉換。

步驟 04

• 繼續重複第三步，直到轉換表 T’ 中不再存在新狀態。
• 最後，獲得的轉換表 T’ 是所需 DFA 的完整轉換表。

注意 -

轉換後，DFA 中的狀態數量可能與 NFA 中的狀態數量相同，也可能不同。

DFA 中存在的最大狀態數是 NFA 中狀態數的兩倍。

NFA 和 DFA 中的狀態數 -

1 <= n <= 2m

這裡，

• n = DFA 中的狀態數
• m = NFA 中的狀態數

在生成的 DFA 中，包含 NFA 的最終狀態的所有狀態都被視為最終狀態。

Bhanu Priya

更新於： 2021 年 6 月 12 日

2K+ 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習