确定化与最小化
确定化
用画表法
第一步:第一列写出所有的状态,第一行写出所有的弧名
状态应该不是所有节点的排列组合,要不先把所有单个节点的状态写出来,然后单个节点推出来新的状态之后再把这个新状态写到第一列
第二步:给左边第一列的所有状态编号,0、1、2、……,然后把表中的所有状态用编号代替
第三步:根据这个编号得出的新表画出确定化的图
什么是终态终态:原图上的终态,和包含所有节点的状态
举个例子
最小化
记住一句话,分组后的元素,经过a弧到达的状态在同一组中,经过b弧到达的状态也在同一组中(这两个组不一定相同)
根据上一个得出的确定化图写
第一步:分组,把非终态分成一组,把终态分成一组
对两个组分别用相同的方法进行处理,所以光以非终态组为例说明
第二步:写出每一个元素通过a弧的状态
第三步:看是否在同一组中,是的话直接看通过b弧的状态,不是的话,把不同的状态按相同的组进行分类
第四步:看分了之后的组通过b弧的状态,这些状态在同一个组中的话,那么这些状态就可以合并
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 TongZhuo's Blog!
评论