Automata Theory 简明教程
DFA Minimization
DFA Minimization using Myphill-Nerode Theorem
Algorithm
Input - DFA
Output - 最小化DFA
Step 1 - 为所有状态对（Qi，Qj）绘制一个表格，不一定直接连接 [所有状态最初都未标记]
Step 2 - 考虑DFA中每个状态对（Qi，Qj），其中Qi ∈ F且Qj ∉ F或反之亦然，并标记它们。[此处的F是结束状态集合]
Step 3 - 重复此步骤，直至无法标记更多状态 -
如果有未标记对（Qi，Qj），如果标记了对于某些输入字母的{δ（Qi，A），δ（Qi，A）}，则标记该对。
Step 4 - 组合所有未标记对（Qi，Qj），并使其成为缩小版DFA中的单个状态。
Example
让我们使用算法2来最小化下面显示的DFA。
Step 1 - 为所有状态对绘制一张表格。
a |
b |
c |
d |
e |
f |
|
a |
||||||
b |
||||||
c |
||||||
d |
||||||
e |
||||||
f |
Step 2 - 我们标记状态对。
a |
b |
c |
d |
e |
f |
|
a |
||||||
b |
||||||
c |
✔ |
✔ |
||||
d |
✔ |
✔ |
||||
e |
✔ |
✔ |
||||
f |
✔ |
✔ |
✔ |
Step 3 - 我们将尝试使用绿色勾号标记状态对。如果我们将1输入到状态“a”和“f”，它将分别进入状态“c”和“f”。（c，f）已经标记，因此我们标记对（a，f）。现在，我们将1输入到状态“b”和“f”；它将分别转到状态“d”和“f”。（d，f）已经标记，因此我们标记对（b，f）。
a |
b |
c |
d |
e |
f |
|
a |
||||||
b |
||||||
c |
✔ |
✔ |
||||
d |
✔ |
✔ |
||||
e |
✔ |
✔ |
||||
f |
✔ |
✔ |
✔ |
✔ |
✔ |
在步骤3之后，我们得到了未标记的属性组合{a，b} {c，d} {c，e} {d，e}。
我们可以将{c，d} {c，e} {d，e}重新组合到{c，d，e}中
因此，我们得到了两个组合状态为 - {a，b}和{c，d，e}
因此，最终的最小化DFA将包含三个状态{f}、{a，b}和{c，d，e}
DFA Minimization using Equivalence Theorem
如果X和Y是DFA中的两个状态，如果它们不可区分，我们可以将这两个状态组合成{X，Y}。如果存在至少一个字符串S，则两个状态是可以区分的，即δ（X，S）和δ（Y，S）中的一个被接受，另一个不被接受。因此，当且仅当所有状态都可区分时，DFA才是最小的。
Algorithm 3
Step 1 - 所有状态 Q 被分为两个分区- final states 和 non-final states ，并由 P0 表示。分区中的所有状态都是0等价。获取计数器 k 并将其初始化为0。
Step 2 - 将k增加1。对于Pk中的每个分区，如果状态在Pk中是k可区分的，则将状态划分为两个分区。此分区X和Y中的两个状态在k-可区分，前提是有一个输入 S ，使得 δ(X, S) 和 δ(Y, S) 在（k-1）-可区分。
Step 3 - 如果Pk ≠ Pk-1，则重复步骤2，否则转到步骤4。
Step 4 − 将第 k 个等价集合组合起来，并将它们设定为化简 DFA 的新状态。
