为什么不合并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 | Dtran[A,a]=B |
1 | Dtran[E,a]=B |
但是,为什么只能说A、C具有相同的状态?
因为在P115,“最小化一个DFA的状态数量”一节
最小化DFA状态数量的第一步是,将包含有所有DFA状态的集合分为两个组,分别是接收状态组和非接受状态组
之后根据状态转换表不断分割与合并
DFA D的A、C、E三个状态中,E是接收状态组,A、C是非接受状态组,
这意味着如果输入状态机的串最终于E状态停止,那么就可以接受这个串,如果到达不了E,或串结束状态机时不在状态E,那么这个串就会被拒绝
于是E和AC从一开始就根本不能划分到同一个组中,也就无从谈起合并这三个状态
Knighthana
2023/04/02