编译原理实验六DFA最小化
实验六:DFA最小化 一:要求 输入:DFA。 输出:最小化的DFA。 二:实验目的 1. 熟练掌握DFA及NFA的定义及有关概念。 2. 理解并掌握确定的有穷自动机的最小化等算法。 三:实验原理 1. 化简DFA关键在于把它的状态集分成一些两两互不相交的子集,使得任何两 个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等 价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删 去,也就获得了状态数最小的DFA。 2. DFA的化简算法: (1)首先将DFAM的状态划分出终止状态集Ki和非终止状态集K2o K=KiUK2 由上述定义知,K]和K?是不等价的。 (2)对各状态集每次按下面的方法进一步划分,直到不再产生新的划分。 设第i次划分已将状态集划分为k组,艮L K=Ki①UK?①U . UKk① 对于状态集Kj①(j=l,2,.,k)中的各个状态逐个检查,设有两个状态K『、Kj” GKj①,且对手输入符号a,有: F (Kj, a) =Km F (K/, a) =Kn 如果Km和Kn属于同一个状态集合,则将和Kj”放到同一集合中,否则将 和Kj”分为两个集合。 (3)重复第(2)步,直到每一个集合不能再划分为止,此时每个状态集合 中的状态均是等价的。 (4)合并等价状态,即在等价状态集中取任意一个状态作为代表,删去其他 一切等价状态。 (5)若有无关状态,则将其删去。 根据以上方法就将确定有限自动机进行了简化,而且简化后的自动机是原自动机 的状态最少的自动机。 四:数据结构与算法 struct edge{ string first;//边的初始结点 string condition;//边上的条件 string last;//边的终点 }; string move (string collection, char ch, edge *b)//状态集合 I 的 a 弧转换 int divide (edge *b, string change) //分割子集法进行 DFA 的最小化 五:出错分析 1:在数据结构的定义之中,字符与字符串的差别,本次实验室字符 串而不是字符 六:实验结果与分析 七:源代码 #include #include using namespace std; #define max 100 struct edge( string first;//边的初始结点 string condition;〃边上的条件 string last;//边的终点 ); int N;//NFA 的边数 string part[max]; 〃分害 子集 string move(string collection,char ch,edge *b)〃状态集合 I 的 a 弧转换 { int i,j; string s=“n; for(i=0;i