计算机理论导引实验————ADFA的可判定性.doc

《计算机理论导引实验————ADFA的可判定性.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUNANUNIVERSITY计算理论导引实验报告题目：ADFA的可判定性学生姓名：安佳玮学生学号：20090810101专业班级：计算机科学与技术1班上课老师：吴昊实验日期：2011-12-22目录一、实验目的2二、实验方法2三、实验代码2四、测试数据以及运行结果6一、实验目的•ADFA={

2、B是DFA，w是串，B接收w}•证明：ADFA是可判定的。二、试验方法编写一个算法/程序，对于给定的输入，可以判定ADFA三、实验代码#includeclassDFA{public:intnum_Q;//状态的个数in

3、t*acc_Q;//接受状态集合intstart_Q;//起始状态intnum_E;//字母表的个数int**next_Q;//转移函数boolGo(int*w);//接受输入时的运行结果DFA();//构造函数~DFA();//析构函数};DFA::DFA(){intnum_acc;//接受状态的总个数cout<<"状态总个数：";cin>>num_Q;cout<<"字母表总个数：";cin>>num_E;cout<<"起始状态编号（从0开始）：";cin>>start_Q;cout<<"接受状态的总个数：";cin>>num_acc;//给接受状态

4、数组动态分配空间acc_Q=newint[num_acc+1];cout<<"接受状态编号(以空格隔开)：";for(inti=0;i>acc_Q[i];}//标记结尾acc_Q[num_acc]=-1;//转移函数数组分配空间next_Q=newint*[num_Q];for(i=0;i

5、<>next_Q[j][k];}}}//析构函数DFA::~DFA(){if(acc_Q)deleteacc_Q;if(next_Q)deletenext_Q;}//在输入w下运行自动机boolDFA::Go(int*w){boolresult;//运行结果int*p=w;//动态之争intnow_Q;//当前状态now_Q=start_Q;//在输入下依次寻找下一个状态while(*p!=-1){cout<<"当前状态"<

6、;now_Q=next_Q[now_Q][*p];cout<>len_

7、w;w=newint[len_w+1];cout<<"输入串中字母的编号依次分别为（以空格隔开）：";for(inti=0;i>w[i];}w[len_w]=-1;cout<<"正在运行中..."<>c;if(c=='N')return0;}deletew;}改程序在VC+

8、+下可以通过编译，并且运行结果正确四、测试数据以及运行结果以教材上面的一个自动机为例。该自动机识别含有001作为字串的所有字符串，而拒绝其它的串。运行结果如下所示：HUNANUNIVERSITY计算理论导引实验报告题目：CFG是P成员学生姓名：安佳玮学生学号：20090810101专业班级：计算机科学与技术1班上课老师：吴昊实验日期：2011-12-22目录一、实验目的2二、实验方法2三、实验代码2四、测试数据以及运行结果10一、实验目的上下文无关文法CFGG是否派生某个串W。采用动态规划（DynamicProgramming）设计一个多项式时间的验证

9、算法二、试验方法编写一个算法/程序，对于给定的输入，可以在多项式时间内判定ACFG。