Knighthana
文章95
标签138
分类7

文章归档

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

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

为什么不合并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都具有相同的转换

1
2
3
4
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