编译原理实验六DFA最小化

实验六DFA最小化 一要求 输入DFA。 输出最小化的DFA。 二实验目的 1. 熟练掌握DFA及NFA的定义及有关概念。 2. 理解并掌握确定的有穷自动机的最小化等算法。 三实验原理 1. 化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两 个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等 价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删 去，也就获得了状态数最小的DFA。 2. DFA的化简算法 （1）首先将DFAM的状态划分出终止状态集Ki和非终止状态集K2o KKiUK2 由上述定义知，K］和K是不等价的。 （2）对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。 设第i次划分已将状态集划分为k组，艮L KKi①UK①U ... UKk① 对于状态集Kj①（jl,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在数据结构的定义之中，字符与字符串的差别，本次实验室字符 串而不是字符 六实验结果与分析 七源代码 includeiostream includestring using namespace std; define max 100 struct edge string first;//边的初始结点 string condition;〃边上的条件 string last;//边的终点 ； int N;//NFA 的边数 string part[max]; 〃分害 子集 string movestring collection,char ch,edge *b〃状态集合 I 的 a 弧转换 { int i,j; string sn; fori0;icollection.length;i { forj0;jN;j ifb [j ].first [0]collection [i]b [j ]. condition [0]ch ssb[j].last; } } ifsretum ””； else return s; bool isexiststring s,string d〃判断子串是否存在在某一集合 ifdnOd.findsd.findsd.length-lretum 1; else return 0; int divideedge *b,string change//分割子集法进行 DFA 的最小化 int x,m,flag2,flag0,i,j; string ss,partO[max]; flagOflag; forxO;xchange.length;x form0;mflag0;m fori0;ivpart[m] .length。;i ssmovepart[m]. substri, 1,change [x],b; forj0;jflag;j ifisexistss,part[j]partO[j]partO[j]part[m].substri,l; ifss”” partO[flag]partO[flag]part[m].substri,l; break; } } forj0;jflag;j ifpartO[j] partO[j] part[m] part [flag]partO [j]; partO[j]; part[m]; } else partO[j]; } } flagOflag; return flag; } void main int i,j,flag,x; string Condition;//边上的条件 string ss; edge *bnew edge [max]; cout编译原理实验六DFA最小化endl; cout请输入DFA各边信息起点条件空用表示终点并以输入结束endl; fori0;imax;i cinb[i],first; ifb[i].firstHnbreak; else cinb [i].conditionb [i].last; } Ni; coutH请输入该DFA的终态集合nendl; cinpart[l]; coutn请输入该DFA的非终态集合nendl; cinpart[O]; coutHif输入此DFA状态中的边上的条件nendl; cinCondition; flagdivideb,Condition; coutDFA最小化划分的子集如下”vendl; fori0;iflag;i { ifpart[i]coutpart[i]endl; } coutvv”用状态A,B,C等代替子集”; fori0;iflag;i { ifpart[i],,,coutn，part[i],},n； } coutendlvv”则DFA最小化后的各边信息如下endl; char letters [max]; char letter*A; fori0;iflag;i { ifpart[i],,n { letters [i]letter; letter; } } fori0;iflag;i