计算理论实验—ADFA的可判定性

计算理论实验要求在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

 

本机测试结果:

adfa可判定性实验

 

代码:

下面的代码没有删减,适合本地测试。

7 thoughts on “计算理论实验—ADFA的可判定性

  1. 百度到csdn一篇博文,貌似K2一同学的,大概两个小时前发的,但是已经404了。。借助百度快照,看到了代码。

回复 原来昵称可以改呀比论坛ID好 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注