《实验E——可判定的DFA的空问题》由会员分享，可在线阅读，更多相关《实验E——可判定的DFA的空问题（8页珍藏版）》请在金锄头文库上搜索。
1、HUNAN UNIVERSITYH A JTTJTrTyU A 乙计算理论导论实验报告d rF血 83 TV j一、实验目的1、理解有穷自动机空问题的可判定性，并利用此算法解决实际问题2、在实际应用中考虑所有可能的情况去求解问题；3、正确处理代码中的各种细节问题。二、实验方法（1）算法思路两种思路：A. DFA接受一个串当且仅当：从起始状态出发，沿着DFA的箭头方向，能够到达一个接受状态。为检查这个条件，设计一个使用标记算法的TM ToT= “对于输入,其中A是一个DFA：1）标记A的起始状态。2）重复下列步骤，直到所有状态都被标记。3）对于一个状态，如果有一个到达它的转移是从某个已经标记过的
2、状态出发的，则将其标 记。4）如果没有接受状态被标记，则接受，否则，拒绝。”B. DFA不接受任意串的三种情况：1）无接受状态；2）接受状态单独存在；3）接受状态和起始状态不在同一圈中。分析两种思路，明显第二种更容易编写程序代码。算法如下：（1）判断接受状态是否存在，不存在直接输出；（2）判断接受状态单独存在的情况，返回布尔变量值；（3）判断接受状态和起始状态不在一个圈内的情况，返回布尔变量值；（4）三种情况均判断结束后，输出结果。2)数据类型题目要求如下：每个测试序列相对应一个DFA,其第一行为2个正整数nm,表示有n个状态，状态集Q=q0,q1?,qn-1 o 默认起始状态为q0,字符集有
3、m个字符。0 n,m三100。随后n 行,每行m个空格隔开的整数气，(0 i n , 0 j m )表示DFA的状态转移函数。气表示第i个状态在输入j (字母表第j个字符)时，变为第8. 个状态。鉴于之前的判断，直接采用静态建立输入矩阵即可。三、问题描述Problem descriptionEdfa=IB是DFA，且L (A) =Q证明：Edfa是可判定的语言。实验方法:编写一个算法/程序， DFADFA对于任意给定的输入(/确定性有限状态自动机DFA)，可以判定E 。DFAInput有多个测试序列，测试结束于测试文件结束；每个测试序列相对应一个DFA，其第一行为2个正整数n，m，表示有n个状
4、态，状态集Q=q0,q,.,qn-1。 默认起始状态为q0，字符集有m个字符。0 n,m 100。随后n行，每行m个空格隔开的整数8. ( 0 i n , 0 j m )表示DFA的状态转移函数。8.表示第i个状态在输入j (字母表第j个字符)时，变为第 8.个状态。每个DFA的最后一行，首先一个整数f,表示接受状态数，然后f个空格隔开的整数fk (0 kijk f),是所有接受状态的编号。其中0 8., fk noij kOutput对于每个输入的DFA，输出”YES”，如果该DFA确实不接受任何串；否则，输出”NO”。Sample Input1 20 0计算理论导论实验报告1 01 20
5、00Sample OutputNOYESJudge Tips样例中2个DFA，第一个是接受所有输入的DFA，第二个是拒绝所有输入的DFA，所以，第一个DFA输出”NO”，而第二个是”YES”。四、程序代码#include#include #include #include #includeusing namespace std;bool a100;bool b100;int print100100;int n, m, f, p, q;/*判断是否是不接受任意串的 DFA*/bool DFS(int k)ak = 1;/接受状态单独存在的情况(2)if(bk)return 1;/接受状态和起始状
6、态不在一个圈内的情况(3)for(int i = 0; i m; i+)if(!aprintki & DFS(printki)return 1;return 0;int main()inti,j;/n 个状态，字符集有 m 个 while(scanf(%d%d, &n, &m)!=EOF)memset(a, 0, sizeof(a);memset(b, 0, sizeof(b); for(i = 0; i n; i+) for(j = 0; j f;/循环输入接受状态for(i = 0; i f; i+)scanf(%d, &p), bp = 1;if(f)if(DFS(0)coutNOend
7、l;elsecoutYESendl;/无接受状态的情况(1)elsecoutYESendl;return 0;五、实验结果六、实验总结1.由于之前的实验在开始添加#includestring，就能直接输入输出采用cin和cout标准输入输出，但是在网站运行时，发现此种输出会出现超时的问题，jsll20L4DB0L0227 13122 GNU C+ Tine Limit Exceeded 1160KB1015ms1072B最终只能又采用 while(scanf(%d%d, &n, &m)!二EOF)和 scanf(%d, &printij)输入。2在分配内存时，根据之前的经验直接采用静态建立很好用的方法。3可判定性的问题求解相对容易，从书本出发求解实际问题，就能更好更深刻的理解内容。
