网站建设优化400报价,南昌网络营销网站,南城东莞网站建设,refile自己做的网站目录
1.由正规式到DFA
首先讲如何从正规式到NFA
如何从NFA到DFA
2.DFA的化简
3.DFA和NFA的区别 1.由正规式到DFA
正规式---NFA----DFA
首先讲如何从正规式到NFA
转换规则: 例题1#xff1a;这里圆圈里面的命名是随意的#xff0c;只要能区别开就可以了 如何…目录
1.由正规式到DFA
首先讲如何从正规式到NFA
如何从NFA到DFA
2.DFA的化简
3.DFA和NFA的区别 1.由正规式到DFA
正规式---NFA----DFA
首先讲如何从正规式到NFA
转换规则: 例题1这里圆圈里面的命名是随意的只要能区别开就可以了 如何从NFA到DFA
NFA----状态转换表----状态转换矩阵----DFA
如下例题
以上NFA的转换表如下图所示
这里的I是从x出发的状态Ia表示I集合中的字符经过a的状态的集合
规则若经过的是空串那么就经过空串后到达的字符加入到集合中如果没有经过空串就不到达。
这里的每一列就是列举上一行中出现的集合例如第二列列举的就是上一行中出现的红框的集合 就拿I{123}具体说
由图1经过a的状态有12经过a的状态有33经过a的状态有56Y因为5后面接的就是串所以{12356Y} 以此类推就能得到转换表再将相同的集合表示出来 就可以进一步得到转换矩阵 再根据状态转换矩阵可得图DFA 注这个图怎么判断这个状态是不是一个终态一个圈还是两个圈那么我们只需要看状态转换表
表中含有Y的集合就是终态需要画两个圈 2.DFA的化简 这里终态和非终态的状态分别为终态{3456}非终态{012}
对于非终态{012}
将{012}分别输入a即{0,1,2}a通过状态转换矩阵可知{012}a{13}{13}对于{012}而言不是包含关系所以
将得到1的状态和得到3的状态分开:
{02}--{1}{1}---{3}
再对{02}输入b的状态:
{02}b---{2,4},{2,4}不包含在{02}中所以{0}---{2},{2}----{4} 对于终态{3456}
{3456}a{36},包含关系
{3456}b{45},包含关系
对于非终态有{0}{1}{2}状态对于终态有{3456}状态将他视为状态{3}那么 这里还是根据状态转换矩阵画只是看到{3456}都指向状态{3} 3.DFA和NFA的区别
NFA是不确定的有穷自动机DFA是确定的有穷自动机
DFA与NFA的区别在于NFA的状态转换过程中可以有空串如下图即为NFA
这就导致了一个问题开始之后在给出字符a或b之前我们能够确定当前是处于1状态还是2状态吗很显然我们是无法确定的因此才被称为不确定的有穷自动机因为空串的存在我们无法确定当前的具体状态是什么。
所以NFA的不确定表现我们可以概括为1.多值映射 2.带空转移
所以我们要将NFA转换为DFA
