构造由正规式构造NFAa(ab)*的DFA

格式:DOC ? 页数:2页 ? 上传日期: 08:25:24 ? 浏览次数:24 ? ? 1200积分 ? ? 用稻壳阅读器打开

全文阅读已结束如果下载本文需要使用

该用户还上传了这些文档

步骤:1、根据三个转换原则(如圖一)转换为NFA

步骤:2、通过子集构造法将NFA转化为DFA

不再出现新的标记了结束,此时初态为I[0]

步骤:3、通过“分割法”进行最小化

DFA的化简:寻找一個状态数比原DFA M少的DMA M’,使得L(M)=L(M’)且这个M’是唯一的

M’ 满足两个条件:1、无死状态(不能到达终态或无法到达的状态)2、两两不是等价状态

思路:1、先删除死状态2、将M的状态集合分成一些不相交的子集,使任何不同两个子集都是可区别的而同一子集中的任何两个状态都是等價的。最后在每个子集中选出一个代表同时消去其他等价状态。

我要回帖

更多关于 由正规式构造NFA 的文章

 

随机推荐