有穷自动机

开始
求开始状态闭包
标记为False令它为C中唯一成员
C中存在尚未 被标记子集
否
N
是
Y 标记T 结束
对子集T中的每个输 入字母求U=Ia子集
U不在C中?
将U加入C中
图3-1 NFA转换成DFA原理图
运行结果
dfa的最小化利用等价关系找出状态集q上的所有最大等价状态子集即找出q的最小划分然后从各个等价子集中选取一个代表状态消去各等价子集中的非代表状态这样就实现了dfa的最小化的目的
有穷自动机的化简与确定化
组员：王勇 朱蓉 许立龙
1、设计内容及要求
• 可以使用任何语言来完成，例如：C、C++。 • 以文件方式读取自动机。 • 判断读取的自动机是确定的还是不确定的 自动机。 • 若是不确定的自动机，将自动机确定化。 • 将确定化后的自动机最小化。 • 输入测试字符串，输出测试结果
2. DFA的最小化 的最小化 利用等价关系找出状态集Q上的所有最大等价状态子集，即找出Q的最小划分， 然后从各个等价子集中选取一个代表状态，消去各等价子集中的非代表状态， 这样就实现了DFA的最小化的目的。 主要步骤： for v(q,p) ∈F×(Q-F) do 标记可区分状态表中的表项(q,p); /*p和q不可合并*/ for v(q,p) ∈F×F∪(Q-F) ×(Q-F)且q≠p do if E a∈∑，可区分状态表中的表项(δ(q,a), δ(p,a))已被标记 then begin 标记可区分状态表中的表项(q,p); 递归的标记本次被标记的状态对的关联链表上的各 个状态对在可区分状态表中的对应表项。 end else for v a∈∑ do if δ(q,a) ≠δ(p,a)且与(q,p)与(δ(q,a), δ(p,a))不是同一个状态对 then 将(q,p)放在(δ(q,a), δ(p,a))的关联链表上。

ε
ε
2
ε
6 b
ε
f
3.4.5 DFA的最小化（化简）
• 最少状态DFA 对于一个DFA M，存在一个最少状态DFA M’， 使得L(M’)=L(M)。 (a)没有多余状态 (b)没有两个状态是互相等价的 结论： 一个NFA 对应的DFA不惟一 但它对应的最小化DFA不计同构是惟一的
• 多余状态的例子 a
例
正规式 φ
ε
a a|b ab (a|b)(a|b) a* ba* (a|b)*
正规集 φ {ε } {a} L(a|b)=L(a) ∪ L(b)={a,b} L(ab)=L(a)L(b)={ab} {aa,ab,ba,bb} { ε ,a,aa,aaa,…} {b,ba,baa,baaa,…} {所有由a和b组成的字}
• 例 DFA M=({0,1,2,3},{a,b}, f ,0,{3}) 其中 f 为： f (0,a)=1 f (0,b)=2 f (1,a)=3 f (1,b)=2 f (2,a)=1 f (2,b)=3 f (3,b)=3 f (3,a)=3
3.4.1 确定有穷自动机(DFA) • DFA的表示方法 两种：矩阵和图形的方式 矩阵称为状态转换矩阵 图形称为状态转换图
• NFA M所接受字符串的集合称为NFA M所能 识别的语言，记为L(M)。 • NFA的确定化 DFA是NFA的特例
NFA M存在与之等价的DFA M’,L(M)=L(M’) 与某一NFA等价的DFA不惟一 正规式 NFA 正规文法 DFA
3.4.4 NFA 确定化
• 状态集合I的空闭包：ε -closure(I) 它是一个状态集合，包含 ： ♠ I中任何状态q ♠ I中任何状态q经任意条空弧到达的任何状态 • 状态集合I的a弧转换：Ia 定义一个状态集J，J是I中所有状态经一条a 弧到达的状态的全体 Ia＝ε -closure(J)

19
正则运算
定理 正则语言类在连接运算下封闭。 1.13
证明思路 按照定理1.12 证明思路试一下。 输入：M1接受第一段且 M2 接受第二段时，M才接受；
？ M不知道在什么地方将它的输入分开 （什么地方第一段结束，第二段开始)
20
举例
Consider the concatenation: 考虑下列连接 {1,01,11,001,011,…} • {0,000,00000,…} (That is: the bit strings that end with a “1”, followed by an odd number of 0’s.) Problem is: given a string w, how does the automaton know where the L1 part stops and the L2 substring starts? 如何知道L1 何处停止？ L2 何处开始？切分问题。
0,1 1
q4
不确定性表现：
• q11 Y ? Y有两个可能状态: • 导致 q2 自动漂移到 q3
q1,q2
是否接受 “0110” 和 “1”
0110——q1 q1 q2 q3 q4 q4
1——{q1, q2 ,q3}
24
非确定性
例1.14 设 A 是 {0, 1} 上倒数第三个符号为 1 的所有字符串组 成的语言，构造非确定性自动机。
一个字符串，并且 wi 是字母表 的成员。如果存在 Q 中的
状态序列 r0, r1, … , rn，满足下列条件： 1) r0 = q0
2) (ri , wi+1) = ri+1 , i = 0, 1, …, n–1

{ char temp=p[i][j]; //暂时存放一个确定的符号
if(temp>='A'&&temp<='Z')//非终结符号的判断条件
{
bool state=true;
for(int k=0;k<VN;k++)
{
if (temp==K[k]) //避免重复
{state=false;break;}
{ char temp=p[i][j]; //暂时存放一个确定的符号
if(!((temp>='A'&&temp<='Z')||temp==':'||temp=='='||temp=='\0'))
//终结符号的判断条件
{
bool state=true;
for(int k=0;k<VT;k++)
{
if (temp==E[k]) //避免重复
*****大学**学院学生实验报告
学号：年月日
系别
专业
计算机科学与技术
班级
姓名
课程名称
编译原理
课程类型
必修课
学时数
实验名称
从正则文法构造有穷状态自动机及运行
实验目的：
一、从正则文法构造有穷状态自动机（1）、掌握有穷状态自动机的概念、其存储表示及其与正则文法的联系。（2）、输入任意的正则文法，输出相应的有穷状态自动机。
（3）、将文法按五元组形式输出。
（4）、编写若干个函数，其中包括在规则中找出终结符号和非终结符号的函数，字符串输入及识别字符串函数，DFA和NFA的相关判断和输出函数，映射关系函数。