Automata Theory 简明教程

NDFA to DFA Conversion

Problem Statement

设 X = (Qx, ∑, δx, q0, Fx) 是接受语言 L(X) 的 NDFA。我们必须设计一个等效 DFA Y = (Qy, ∑, δy, q0, Fy) ，使得 L(Y) = L(X) 。以下过程将 NDFA 转换为其等效 DFA −

Let X = (Qx, ∑, δx, q0, Fx) be an NDFA which accepts the language L(X). We have to design an equivalent DFA Y = (Qy, ∑, δy, q0, Fy) such that L(Y) = L(X). The following procedure converts the NDFA to its equivalent DFA −

Algorithm

Input − NDFA

Input − An NDFA

Output − 等效 DFA

Output − An equivalent DFA

Step 1 − 根据给定的 NDFA 创建状态表。

Step 1 − Create state table from the given NDFA.

Step 2 − 根据等效 DFA 的可能的输入字母创建一个空白状态表。

Step 2 − Create a blank state table under possible input alphabets for the equivalent DFA.

Step 3 − 标记为 q0 的 DFA 的起始状态（与 NDFA 相同）。

Step 3 − Mark the start state of the DFA by q0 (Same as the NDFA).

Step 4 − 找出对于每个可能的输入字母的状态 {Q0, Q1,… , Qn} 的组合。

Step 4 − Find out the combination of States {Q0, Q1,… , Qn} for each possible input alphabet.

Step 5 − 每次在输入字母列中生成一个新的 DFA 状态时，我们都必须重新应用步骤 4，否则转到步骤 6。

Step 5 − Each time we generate a new DFA state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.

Step 6 − 包含 NDFA 的任何最终状态的状态是等效 DFA 的最终状态。

Step 6 − The states which contain any of the final states of the NDFA are the final states of the equivalent DFA.

Example

我们考虑下图所示的 NDFA。

Let us consider the NDFA shown in the figure below.

δ(q,0)

δ(q,1)

{a,b,c,d,e}

{d,e}

{c}

{e}

∅

{b}

{e}

∅

使用上述算法，我们可以找到其等效 DFA。DFA 的状态表如下所示。

Using the above algorithm, we find its equivalent DFA. The state table of the DFA is shown in below.

δ(q,0)

δ(q,1)

[a]

[a,b,c,d,e]

[d,e]

[a,b,c,d,e]

[b,d,e]

[d,e]

[e]

∅

[b,d,e]

[c,e]

[e]

∅

[c, e]

∅

[b]

[c]

[e]

[c]

∅

[b]

DFA 的状态图如下所示 −

The state diagram of the DFA is as follows −