《实验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可判定性的问题求解相对容易,从书本出发求解实际问题,就能更好更深刻的理解内容。