DFA最小化下载_Word模板_7

is_062617

暂无简介

DFA最小化学号：专业：姓名：实验日期：2012.5.25 教师签字：成绩：实验名称：试验五：有穷确定自动机的最小化实验目的： 1. 掌握DFA的结构。 2. 掌握DFA最小化的方法。 3. 编程实现。实验原理：已知DFA，,构造,M-′.=，使得L(M’)=L(M),且M’中不含有等价状态。步骤如下: i. 做初始划分（K-Z，Z）； ii. 设在划分的某一步π=（,𝐼-1.,,𝐼-2.,…,,𝐼-𝑡....

学号：专业：姓名：实验日期：2012.5.25 教师签字：成绩：实验名称：试验五：有穷确定自动机的最小化实验目的： 1. 掌握DFA的结构。 2. 掌握DFA最小化的方法。 3. 编程实现。实验原理：已知DFA，,构造,M-′.=，使得L(M’)=L(M),且M’中不含有等价状态。步骤如下: i. 做初始划分（K-Z，Z）； ii. 设在划分的某一步π=（,𝐼-1.,,𝐼-2.,…,,𝐼-𝑡.），对于每个Ii，计算Iia=｛qi1,qi2,..,qip｝. 若qi1,qi2,..,qip分属于m个不同的子集，则将Ii分成m个子集，构成 iii. 若，则令π=,π-new.，并重复ii； iv. 对每个，任取一代表元，删去其余元素，将DFA上有入度的线，终点改为代表元；实验代码： “Grammar.cpp” #include #include using namespace std; struct subset { int id; vector set; }; class Grammar { public: Grammar(ifstream &in); ~Grammar(void); int k;//状态个数 int tc;//终结符个数 char t[26];//终结符 int m;//边数 int DFA[32][128]; int belong[32];//某个状态属于哪个子集 bool terminal[32];//终结符表 int terminalCount;//终结符个数 bool Mterminal[32];//最小化后的终结符表 int MDFA[32][128];//最小化的DFA表 int MDFAstart;// 最小化的DFA的初态 subset DFAsubset[32];//划分的子集 int subsetcount;//子集的个数 void erase(); vector spilt(subset I); void min(); bool insameset(int e,subset &v); }; Grammar::Grammar(ifstream &in) { int i,u,v; char a; memset(terminal,false,sizeof(terminal)); memset(Mterminal,false,sizeof(Mterminal)); for(u=0;u<32;u++) for(v=0;v<128;v++) { DFA[u][v]=-1; MDFA[u][v]=-1; } this->subsetcount=0; in>>this->k;//状态个数 in>>this->tc;//终结符个数 for(i=0;i>t[i]; in>>this->terminalCount;//终态个数 for(i=0;iterminalCount;i++)//标志终态 { in>>u; terminal[u]=true; } in>>this->m;//边数 for(i=0;i>u>>a>>v; DFA[u][a]=v; } this->min(); } void Grammar::min() { subset start,end; int i,id=0; start.id=id++; end.id=id++; for(i=1;i<=this->k;i++) { if(terminal[i]) { end.set.push_back(i); belong[i]=end.id; } else { start.set.push_back(i); belong[i]=start.id; } } DFAsubset[subsetcount++]=start; DFAsubset[subsetcount++]=end; while(true) { bool flag=false; for(i=0;i vs=spilt(DFAsubset[i]); if(vs.size()>1) { flag=true; vs[0].id=DFAsubset[i].id; DFAsubset[i]=vs[0]; for(unsigned int j=1;j Grammar::spilt(subset I) { subset sub; vector U; sub.set.push_back(I.set[0]); U.push_back(sub); for(unsigned int i=1;i

本文档为【DFA最小化】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

历史搜索

清空历史搜索

DFA最小化

热门搜索

历史搜索