编译原理(三) wu-kan

考虑以下 DFA 的状态迁移表,其中 0,1 为输入符号,A~H 代表状态,其中 A 为初始状态,D 为接受状态,请画出与此 DFA 等价的最小 DFA,并在新的 DFA 状态中标明它对应的原 DFA 状态的子集

 01
ABA
BAC
CDB
DDA
EDF
FGE
GFG
HGD
步骤$F$$S-F$
1${D}$${A,B,C,E,F,G,H}$
2${D}$${C,E},{A,B,F,G,H}$
3${D}$${C,E},{A,G},{B,F},{H}$

由画图工具所限,以下均以椭圆形表示 Start 节点。

flowchart LR
AG--0-->BF
AG--1-->AG
BF--0-->AG
BF--1-->CE
CE--0-->D
CE--1-->BF
D--0-->D
D--1-->AG
H--0-->AG
H--1-->D
AG([AG])

备注:按照教材 DFA 的算法,「死状态」H 会保留下来,但是从实用性的角度 H 去掉也无妨.

考虑所有含有 3 个状态(设为 p,q,r)的 DFA. 设只有 r 是接受状态. 至于哪一个状态是初始状态与本问题无关. 输入符号只有 0 和 1. 这样的 DFA 总共有 729 种不同的状态迁移函数,因为对于每一状态和每一输入符号,可能迁移到 3 个状态中的一个,所以总共有 3^6=729 种可能. 在这 729 个 DFA 中,有多少个 p 和 q 是不可区分的(indistinguishable)?解释你的答案

当 p 和 q 不可区分的时候,r 的迁移实际上与问题无关,因此 r 对输入 0 或者输入 1 各有三种可能的迁移,总共 $3\times 3=9$ 种可能,均符合题意。

下面考虑 p 和 q 的迁移,不妨考虑输入为 0 的情况:

  1. 若 p 迁移到 r,则 q 也要迁移到 r,只有一种情况符合。
  2. 若 p 迁移到 p,则 q 迁移到 p、q 都是符合的。
  3. 若 p 迁移到 q,则 q 迁移到 p、q 都是符合的。

综上,当输入为 0 时 p、q 的迁移有五种情况符合。同理当输入为 1 的时候 p、q 的情况也有五种符合,因此 p、q 的迁移表有 $5\times 5=25$ 种情况符合,因此总共有 $9\times 25=225$ 个 DFA 符合题意。