Automata Theory 简明教程

DFA Minimization

DFA Minimization using Myphill-Nerode Theorem

Algorithm

Input - DFA

Input − DFA

Output - 最小化DFA

Output − Minimized DFA

Step 1 - 为所有状态对（Qi，Qj）绘制一个表格，不一定直接连接 [所有状态最初都未标记]

Step 1 − Draw a table for all pairs of states (Qi, Qj) not necessarily connected directly [All are unmarked initially]

Step 2 - 考虑DFA中每个状态对（Qi，Qj），其中Qi ∈ F且Qj ∉ F或反之亦然，并标记它们。[此处的F是结束状态集合]

Step 2 − Consider every state pair (Qi, Qj) in the DFA where Qi ∈ F and Qj ∉ F or vice versa and mark them. [Here F is the set of final states]

Step 3 - 重复此步骤，直至无法标记更多状态 -

Step 3 − Repeat this step until we cannot mark anymore states −

如果有未标记对（Qi，Qj），如果标记了对于某些输入字母的{δ（Qi，A），δ（Qi，A）}，则标记该对。

If there is an unmarked pair (Qi, Qj), mark it if the pair {δ (Qi, A), δ (Qi, A)} is marked for some input alphabet.

Step 4 - 组合所有未标记对（Qi，Qj），并使其成为缩小版DFA中的单个状态。

Step 4 − Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

Example

让我们使用算法2来最小化下面显示的DFA。

Let us use Algorithm 2 to minimize the DFA shown below.

dfa minimizing using myphill nerode theorem

Step 1 - 为所有状态对绘制一张表格。

Step 1 − We draw a table for all pair of states.

Step 2 - 我们标记状态对。

Step 2 − We mark the state pairs.

✔

Step 3 - 我们将尝试使用绿色勾号标记状态对。如果我们将1输入到状态“a”和“f”，它将分别进入状态“c”和“f”。（c，f）已经标记，因此我们标记对（a，f）。现在，我们将1输入到状态“b”和“f”；它将分别转到状态“d”和“f”。（d，f）已经标记，因此我们标记对（b，f）。

Step 3 − We will try to mark the state pairs, with green colored check mark, transitively. If we input 1 to state ‘a’ and ‘f’, it will go to state ‘c’ and ‘f’ respectively. (c, f) is already marked, hence we will mark pair (a, f). Now, we input 1 to state ‘b’ and ‘f’; it will go to state ‘d’ and ‘f’ respectively. (d, f) is already marked, hence we will mark pair (b, f).

✔

在步骤3之后，我们得到了未标记的属性组合{a，b} {c，d} {c，e} {d，e}。

After step 3, we have got state combinations {a, b} {c, d} {c, e} {d, e} that are unmarked.

我们可以将{c，d} {c，e} {d，e}重新组合到{c，d，e}中

We can recombine {c, d} {c, e} {d, e} into {c, d, e}

因此，我们得到了两个组合状态为 - {a，b}和{c，d，e}

Hence we got two combined states as − {a, b} and {c, d, e}

因此，最终的最小化DFA将包含三个状态{f}、{a，b}和{c，d，e}

So the final minimized DFA will contain three states {f}, {a, b} and {c, d, e}

DFA Minimization using Equivalence Theorem

如果X和Y是DFA中的两个状态，如果它们不可区分，我们可以将这两个状态组合成{X，Y}。如果存在至少一个字符串S，则两个状态是可以区分的，即δ（X，S）和δ（Y，S）中的一个被接受，另一个不被接受。因此，当且仅当所有状态都可区分时，DFA才是最小的。

If X and Y are two states in a DFA, we can combine these two states into {X, Y} if they are not distinguishable. Two states are distinguishable, if there is at least one string S, such that one of δ (X, S) and δ (Y, S) is accepting and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable.

Algorithm 3

Step 1 - 所有状态 Q 被分为两个分区- final states 和 non-final states ，并由 P0 表示。分区中的所有状态都是0等价。获取计数器 k 并将其初始化为0。

Step 1 − All the states Q are divided in two partitions − final states and non-final states and are denoted by P0. All the states in a partition are 0th equivalent. Take a counter k and initialize it with 0.

Step 2 - 将k增加1。对于Pk中的每个分区，如果状态在Pk中是k可区分的，则将状态划分为两个分区。此分区X和Y中的两个状态在k-可区分，前提是有一个输入 S ，使得 δ(X, S) 和 δ(Y, S) 在（k-1）-可区分。

Step 2 − Increment k by 1. For each partition in Pk, divide the states in Pk into two partitions if they are k-distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input S such that δ(X, S) and δ(Y, S) are (k-1)-distinguishable.

Step 3 - 如果Pk ≠ Pk-1，则重复步骤2，否则转到步骤4。

Step 3 − If Pk ≠ Pk-1, repeat Step 2, otherwise go to Step 4.

Step 4 − 将第 k 个等价集合组合起来，并将它们设定为化简 DFA 的新状态。

Step 4 − Combine kth equivalent sets and make them the new states of the reduced DFA.

Example

让我们思考下列 DFA −

Let us consider the following DFA −

δ(q,0)

δ(q,1)

让我们对上述 DFA 应用上述算法 −

Let us apply the above algorithm to the above DFA −

P0 = {(c,d,e), (a,b,f)}
P1 = {(c,d,e), (a,b),(f)}
P2 = {(c,d,e), (a,b),(f)}

因此，P1 = P2。

Hence, P1 = P2.

在化简后的 DFA 中有三个状态。化简后的 DFA 如下所示 −

There are three states in the reduced DFA. The reduced DFA is as follows −

δ(q,0)

δ(q,1)

(a, b)

(c,d,e)

(f)