计算理论实验要求在ACM系统提交,头一次用ACM做实验,本机测试对的提交之后却得到错误的结果,相当的郁闷,不过还好,后来在同学的帮助下解决了,顺利AC。
实验题目:
ADFA={<B,w>|B是DFA,w是串,B接收w},证明:ADFA是可判定的。
编写一个算法/程序,对于给定的输入<B,w>,可以判定ADFA。
Input
有多个测试序列,测试结束于测试文件结束; 每个测试序列的第一行为几个正整数n m t a分别表示有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表示不接受。
Sample Input
3 3 1 2
2 3 2
3 3 3
3 3 3
2
a
b
Sample Output
YES
NO
本机测试结果:
代码:
下面的代码没有删减,适合本地测试。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/*第一行为几个正整数n m t a分别表示有n个状态,从a开始m个小写字母组成的字符集,第一个状态默认为起始状态。 t个接受状态和a个测试串,接下来为一个n行m列的矩阵S,其中S[i][j]表示第i行第j列,意义为状态i经过字母j到达状 态S[i][j]。接下来有t个数字,表示t个接受状态值,然后是a行,每行一个串表示待测试的串。 */ #include<iostream> #include<cstdlib> using namespace std; int main() { //cout<<"按照说明格式输入:"<<endl; int n,m,t,a; //n个状态,从a开始m个小写字母组成的字母表,t个接受状态,a个测试串 while(cin>>n>>m>>t>>a) { int **delta; //定义转移函数 delta=new int*[n]; for(int i=0;i<n;i++) delta[i]=new int[m]; //输入转移函数矩阵 for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>delta[i][j]; int *f; //接受状态集 f=new int[t]; //输入接受状态集 for(int i=0;i<t;i++) cin>>f[i]; string *str; //测试字符串 str=new string[a]; //输入测试字符串 for(int i=0;i<a;i++) cin>>str[i]; int *q; //定义状态 q=new int[a]; for(int i=0;i<a;i++) q[i]=0; for(int i=0;i<a;i++) { for(int j=0;j<str[i].length();j++) { //cout<<"状态 "<<q[i]+1<<" 经 "<<str[i][j]<<" 到状态 "<< delta[q[i]][int(str[i][j]-97)]<<endl; q[i]=delta[q[i]][int(str[i][j]-97)]; //DFA运行 q[i]--; } } /* DFA停止状态测试输出 for(int i=0;i<a;i++) cout<<"q["<<i<<"] = "<<q[i]+1<<endl;*/ for(int i=0;i<a;i++) { int flag=0; //接受标志 for(int j=0;j<t;j++) { if(q[i]+1==f[j]) flag=1; } if(flag==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } //释放数组 delete []f; delete []q; delete []str; //释放二维数组 for(int i=0;i<n;i++) delete []delta[i]; delete []delta; } return 0; } |
纠了个结的,pre代码也用不了了。。
在来一层瞅瞅
继续。
你能有多少层。。。
啊啊啊
貌似不错。。~
百度到csdn一篇博文,貌似K2一同学的,大概两个小时前发的,但是已经404了。。借助百度快照,看到了代码。