湖南大学-计算理论实验

目录实验A----ADFA的可判定性.........................................................................................21、问题描述......................................................................................................22、算法设计思路..............................................................................................33、实验总结......................................................................................................34、AC代码.........................................................................................................3实验B----CFG是P成员................................................................................................41、问题描述......................................................................................................42、算法设计思路..............................................................................................53、实验总结......................................................................................................54、AC代码.........................................................................................................5实验C----NFA转换为DFA.............................................................................................81、问题描述......................................................................................................82、算法设计思路..............................................................................................93、实验总结......................................................................................................94、AC代码.........................................................................................................9实验D----两个数的互素判定.....................................................................................121、问题描述....................................................................................................122、算法设计思路............................................................................................133、实验总结....................................................................................................134、AC代码.......................................................................................................13实验E----可判定的DFA的空问题.............................................................................141、问题描述....................................................................................................142、算法设计思路............................................................................................153、实验总结....................................................................................................154、AC代码.......................................................................................................15实验A----ADFA的可判定性1、问题描述ProblemdescriptionADFA={B,w|B是DFA，w是串，B接收w}证明：ADFA是可判定的。实验方法:编写一个算法/程序，对于任意给定的输入，可以判定ADFA。Input有多个测试序列，测试结束于测试文件结束；每个测试序列的第一行为几个正整数nmta分别表示有n个状态，从a开始m个小写字母组成的字符集，第一个状态默认为起始状态。t个接受状态和a个测试串,接下来为一个n行m列的矩阵S,其中S[i][j]表示第i行第j列，意义为状态i经过字母j到达状态S[i][j]。接下来有t个数字,表示t个接受状态值，然后是a行，每行一个串表示待测试的串。Output对于每个字符串输出YES表示该DFA接受该串，NO表示不接受。SampleInput33122323333332abSampleOutputYESNO2、算法设计思路A:首先将输入的状态转移矩阵保存在S数组中，其中其中S[i][j]表示第i行第j列，意义为状态i经过字母j到达状态S[i][j]。B:对每一个输入的串W,从after（after表示每次转换后的状态，初始为起始状态）开始，按照每一个字符，得到相应的后继状态，保存在after中。C:最后判断accept[after]的值，即串在DFA上运行之后最终状态是否可接受。3、实验总结总的来说这一题比较容易（有点太水了），只要把输入串的每一个字符按照前面的状态得到后继状态，并不断的走下去，直到串的最后一个字符，就可以得到最后的状态，再根据其是否处在接受态，给出相应的输出4、AC代码#includeiostream#includecstringusingnamespacestd;longn,m,t,a;longs[1000][1000];//存储转移矩阵longaccept[1000];//存储接受状态intmain(){while(cinnmta){memset(s,0,sizeof(s));memset(accept,0,sizeof(accept));for(inti=1;i=n;i++){for(intj=1;j=m;j++)cins[i][j];}for(inti=0;it;i++){longtemp;cintemp;accept[temp]=1;}while(a--){stringtemps;cintemps;intafter=1;for(inti=0;itemps.length();i++){after=s[after][temps[i]-'a'+1];}if(accept[after]==1)coutYESendl;elsecoutNOendl;}}return0;}实验B----CFG是P成员1、问题描述Problemdescription上下文无关文法CFGG是否派生某个串W。采用动态规划（DynamicProgramming）设计一个一个多项式时间的验证算法。Input输入第一行为一个正整数n，接下来n行为一个满足乔姆斯基范式的文法描述。然后一个正整数m，接下来m行为m个小写字母组成的字符串(长度小于100)表示m个待测试的串。Output对于每一个测试串返回yes或者no，表示该串是否能被文法派生出来。SampleInput4S-ABA-AB|aB-BC|bC-CA|CC|c3abacbcSampleOutputyesnono2、算法设计思路A:找出所有A-b型规则B:找出所有A-BC型规则C:考察每一个长为1的子串D:考察L长度的子串E:检查起始变元是否在table[0][n]中3、实验总结（1）刚开始用栈和转移矩阵来进行状态的切换，想要先把CFG转换为一个PDA，在根据PDA接受串的情况来判断（因为题目要求线性时间复杂度），后来发现转换成PDA的时候，每一个转移矩阵里应该是一个状态的集合。（2）原本定义一个setintS来表示转移矩阵，但是觉得这样还不如直接用原来的CFG按照某种规则来进行替换，让他的复杂度为线性的。具体线性替换的顺序在2中详细介绍了4、AC代码#includecstdlib#includeiostream#includefstreamusingnamespacestd;intmain(){intn,m;//n行满足乔姆斯基范式的文法描述,m行待测字符串while(cinn){string*cfg;//CFG文法描述cfg=newstring[n];for(inti=0;in;i++)cincfg[i];//输入CFG文法cinm;//输入待测字符串数量string*str;//待测字符串str=newstring[m];for(inti=0;im;i++)cinstr[i];//输入待测字符串int*lstr;//待测字符串的长度lstr=newint[m];for(inti=0;im;i++)lstr[i]=str[i].length();string***table;//定义表格table=newstring**[m];for(inti=0;im;i++)table[i]=newstring*[lstr[i]];for(inti=0;im;i++)for(intj=0;jlstr[i];j++)table[i][j]=newstring[lstr[i]];//找出所有A-b型规则stringAb[100];intnum