内容发布更新时间 : 2024/12/23 10:54:31星期一 下面是文章的全部内容请认真阅读。
编译原理实验报告
实验名称 DFA的最小化
实验时间
院系
班级
学号
姓名
1. 试验目的
掌握DFA的最小化
2. 实验原理
所谓自动机的化简问题即是对任何一个确定有限自动机DFA M,构造另一个确定有限自动机DFA M’,有L(M)=L(M’),并且M’的状态个数不多于M的状态个数,而且可以肯定地说,能够找到一个状态个数为最小的M’。
下面首先来介绍一些相关的基本概念。 设Si是自动机M的一个状态,从Si出发能导出的所有符号串集合记为L(Si)。 设有两个状态Si和Sj,若有L(Si)=L(Sj),则称Si和Sj是等价状态。 下图所示的自动机中L(B)=L(C)={1},所有状态B和状态C是等价状态。
0 A B 1 1
C D
1
又例如终态导出的符号串集合中必然包含空串ε,而非终止状态导出的符号串集合中不可能包含空串ε,所以终态和非终止状态是不等价的。
对于等价的概念,我们还可以从另一个角度来给出定义。
给定一个DFA M,如果从某个状态P开始,以字符串w作为输入,DFA M将结束于终态,而从另一状态Q开始,以字符串w作为输入,DFA M将结束于非终止状态,则称字符串w把状态P和状态Q区分开来。
把不可区分开来的两个状态称为等价状态。
设Si是自动机M的一个状态,如果从开始状态不可能达到该状态Si,则称Si为无用状态。
设Si是自动机M的一个状态,如果对任何输入符号a都转到其本身,而不可能达到终止状态,则称Si为死状态。
化简DFA关键在于把它的状态集分成一些两两互不相交的子集,使得任何两个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删去,也就获得了状态数最小的DFA。
下面具体介绍DFA的化简算法: (1) 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。
K=K1∪K2
由上述定义知,K1和K2是不等价的。
(2) 对各状态集每次按下面的方法进一步划分,直到不再产生新的划分。
设第i次划分已将状态集划分为k组,即: K=K1(i)∪K2(i)∪…∪Kk(i)
对于状态集Kj(i)(j=1,2,…,k)中的各个状态逐个检查,设有两个状态Kj’、 Kj’’∈Kj(i),且对于输入符号a,有:
F(Kj',a)=Km F(Kj'',a)=Kn
如果Km和Kn属于同一个状态集合,则将Kj’和Kj’’放到同一集合中,否则将Kj’和Kj’’分为两个集合。 (3) 重复第(2)步,直到每一个集合不能再划分为止,此时每个状态集合
中的状态均是等价的。 (4) 合并等价状态,即在等价状态集中取任意一个状态作为代表,删去其
他一切等价状态。 (5) 若有无关状态,则将其删去。
根据以上方法就将确定有限自动机进行了简化,而且简化后的自动机是原自动机的状态最少的自动机。
3..实验内容
输入: DFA。
输出: 最小化的DFA。
3. 实验心得
通过这次实验,加深了对DFA最小化的方法的理解,学会了实现DFA最小化的方法,化简DFA关键在于把它的状态集分成一
些两两互不相交的子集,使得任何两个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删去,也就获得了状态数最小的DFA。
4. 实验代码与结果
#include
int t=0,x=0,c=0,d=0,z=0,h=0;; string state[5]; #define maxs 100