一、定义:
不确定的有限自动机(NFA): 一种数学模型
(1) 一个有限的状态集合S
(2) 一个输入符号集合∑(不包含ε)
(3) 一个转换函数move: S X (∑ U {ε}) -> P(S)
(4) 状态s0是唯一的开始状态
(5) 状态集合F是接受状态集合,S包含F
确定的有限自动机(DFA): 是NFA的特殊情况
(1) 任何状态都没有ε转换
(2) 对于任何状态s和任何输入符号a,最多只有一条标记为a的边离开,即转换函数move: S X ∑-> S可以是一个部分函数。
二、表示:
1.NFA:
NFA可以用带标记的有向图表示,节点表示状态,有标记的边代表转换函数。
(a|b)*ab的NFA
(图1)
状态转换表
状态\输入字符
a
b
0 |
{0,1} |
{0} |
1 |
ø |
{2} |
2 |
ø |
ø |
2.DFA:
(a|b)*ab的DFA
(图2)
三、NFA到DFA:子集构造法
步骤
假设有(a|b)*ab的NFA图中
(图3)
第一步:由起始位置配ε可以到达的所有状态集合{0,1,2,4,7}作为DFA的起始状态A;
第二步:确定字母表{a,b}
第三步:可以画出DFA的转换表Dtran的模型,(*表示未确定)
状态\输入字符
a
b
A {0,1,2,4,7} |
* |
* |
第四步:寻找表中未确定项,例如[A,a],为该空确定转移状态,从图(1)可知集合A中的状态匹配输入字符a,可以转移到的状态集合为{1,2,3,4,6,7,8},该集合没有出现过,所以要在DFA的转换表Dtran的模型中加入该状态集。
状态\输入字符
a
b
A {0,1,2,4,7} |
B |
* |
B {1,2,3,4,6,7,8} |
* |
* |
第五步:重复第四步,知道确定DFA的转换表Dtran
状态\输入字符
a
b
A {0,1,2,4,7} |
B |
C |
B {1,2,3,4,6,7,8} |
B |
D |
C {1,2,4,5,6,7} |
B |
C |
D {1,2,4,5,6,7,9} |
B |
C |
第六步:根据DFA转换表就可以画出DFA的状态图。
伪代码
Q 为处理的集合队列
s 起始状态集合
G 为转换表
S = getSet(s, ε);
为S分配一个唯一的标识码,例如(0),对应到G;
将S加入队列Q;
while(Q不为空) {
U = Q.front(), Q.pop();
for (对于字母表中的每个字母) {
New = getSet(U, a);
if (New == ø)
continue;
获得New集合的标识码,如果未出现,则在Q中加入New,并为New分配一个标识码。
G[U,New] = a;
}
}
对于getSet函数来说,给定一个集合U和匹配字符a,获得一个转移集合V,该函数需要注意边为ε的时候,因为NFA的边可以为ε。
分享到:
相关推荐
编译原理课程实验-有限自动机的确定化和最小化: 实验目的:利用状态表和有限自动机的运行原理编写和设计程序,判断输入的自动机是DFA还是NFA,如果是NFA,利用子集法将其确定化,然后利用求同法或求异法将所得的...
是一个CPP文件,添加到工程中就可以运行。
词法分析--有限自动机等价性,编译原理-第二章-词法分析之NFA、DFA之间的转化和DFA的化简笔记对应的课件资源
编译原理,有限自动机,只是课件,需要了解的可以下载来看看,
电子科技大学-有限自动机陈文宇-2020试卷-回忆版
编译原理之有限自动机解析学习课程.pptx
编译原理之有限自动机解析学习教案.pptx
利用状态表和有限自动机的运行原理编写和设计程序,判断输入的自动机是DFA还是NFA,如果是NFA,利用子集法将其确定化,然后利用求同法或求异法将所得的DFA最小化。
编译原理3词法分析与自动机 编译原理3词法分析与自动机 编译原理3词法分析与自动机 编译原理3词法分析与自动机 编译原理3词法分析与自动机
该自动机可以识别用户输入的文法是否是正确文法,如果正确则正常输出。若错误则显示错误,123abc>;
该资源是编译原理中自动机的编写代码,采用 C语言编写。可以运行,实现基础自动机。内附有详细编写的过程论文。可以参考。
编译原理有限自动机运用 设计一个确定的有限自动机,写出状态转换函数,或画出状态图,编制程序,输入一个字符串,程序能判别该字符串是否能被该有限自动机接受,可以考虑输出能否接受的同时,输出状态路径。难度:...
编译原理识别常数的自动机编译原理识别常数的自动机编译原理识别常数的自动机编译原理识别常数的自动机
MATLAB工具箱大全-元胞自动机
一、实验题目:有限自动机的运行(或“利用状态图判断无符号定点实数”等) 二、实验目的: ...利用状态表和有限自动机的运行原理编制程序,使得程序能够识别一个输入串是否为一个有效的无符号定点实数。
大数据-算法-树自动机与模糊树自动机的代数性质
MATLAB源码集锦-元胞自动机代码可直接运行(建议学会基本原理再用)
大数据-算法-基于自动机的XML数据过滤研究.pdf
数学建模-元胞自动机.zip
用c#写得,请用vs2012打开,本代码支持输入任意的DFA矩阵以及任意字符串然后计算该字符串是否属于该矩阵