编译原理6.1：NFA转DFA、DFA化简

NFA转换成DFA

  

 

例子

 

DFA的化简一一状态的等价性

 

对应的，可区别概念： 

 

 

 

 
DFA的化简一一化简算法

 

 

 

 例子（看是否指向终态）：

小结

 

 

补充

 ·子集法进行NFA的确定化，所得DFA的终态如何确定？

 将所有包含原来终态的集合作为新的DFA终态

·无关状态包括哪两种状态？删除无关状态时，与其相关联的弧该怎么处理？

 无关状态包括多余状态和死状态。删除无关状态时直接去掉相关弧

多余状态：对于一个状态K，如果从开始状态S出发，不可能到达该状态K ，则状态K称为多余状态。

 死状态：对于一个状态K，对于任意输入符号，若转到该状态后，不能到达最终状态，则该状态称为死状态。

·在进行DFA简化时，等价状态集中只需保留一个状态作为代表，其余的可以删除。在删除等价状态时，与其相关联的弧应该怎么处理？

 指向等价状态集的入弧都指到代表状态上，等价状态集中的出弧则都由代表状态指出。