NFA到DFA的轉換

問題陳述

設X = (Q_x, ∑, δ_x, q₀, F_x)為一個接受語言L(X)的NFA。我們必須設計一個等價的DFAY = (Q_y, ∑, δ_y, q₀, F_y)，使得L(Y) = L(X)。以下過程將NFA轉換為其等價的DFA -

演算法

輸入 - 一個NFA

輸出 - 一個等價的DFA

步驟1 - 從給定的NFA建立狀態表。

步驟2 - 為等價的DFA在可能的輸入字母表下建立一個空白狀態表。

步驟3 - 將DFA的起始狀態標記為q0（與NFA相同）。

步驟4 - 找出每個可能的輸入字母表的狀態組合{Q₀, Q₁,... , Q_n}。

步驟5 - 每次我們在輸入字母表列下生成一個新的DFA狀態時，都必須再次應用步驟4，否則轉到步驟6。

步驟6 - 包含NFA的任何最終狀態的狀態是等價DFA的最終狀態。

示例

讓我們考慮下圖所示的NFA。

使用上述演算法，我們找到其等價的DFA。DFA的狀態表如下所示。

DFA的狀態圖如下所示 -