为什么不合并A和E两个状态

2023年04月02日 subject-note

为什么不合并A和E两个状态 / 为什么不合并A,C,E状态 - 编译原理第2版99页

注意到前述DFA D的状态转换表

NFA状态	DFA状态	a	b
{0,1,2,4,7}	A	B	C
{1,2,3,4,6,7,8}	B	B	D
{1,2,4,5,6,7}	C	B	C
{1,2,4,5,6,7,9}	D	B	E
{1,2,4,5,6,7,10}	E	B	C

中，A、C、E都具有相同的转换

Dtran[A,a]=B
Dtran[A,b]=C
Dtran[C,a]=B
Dtran[C,b]=C

1 2	Dtran[E,a]=B Dtran[E,b]=C

但是，为什么只能说A、C具有相同的状态？

因为在P115，“最小化一个DFA的状态数量”一节

最小化DFA状态数量的第一步是，将包含有所有DFA状态的集合分为两个组，分别是接收状态组和非接受状态组

之后根据状态转换表不断分割与合并

DFA D的A、C、E三个状态中，E是接收状态组，A、C是非接受状态组，

这意味着如果输入状态机的串最终于E状态停止，那么就可以接受这个串，如果到达不了E，或串结束状态机时不在状态E，那么这个串就会被拒绝

于是E和AC从一开始就根本不能划分到同一个组中，也就无从谈起合并这三个状态

Knighthana

2023/04/02