《湖南大学-计算理论实验》由会员分享，可在线阅读，更多相关《湖南大学-计算理论实验（16页珍藏版）》请在金锄头文库上搜索。
1、目录 实验 A- ADFA 的可判定性.2 1、问题描述.2 2、算法设计思路 .3 3、实验总结.3 4、AC 代码.3 实验 B-CFG 是 P 成员.4 1、问题描述.4 2、算法设计思路 .5 3、实验总结.5 4、AC 代码.5 实验 C-NFA 转换为 DFA .8 1、问题描述.8 2、算法设计思路 .9 3、实验总结.9 4、AC 代码.9 实验 D-两个数的互素判定.12 1、 问题描述.12 2、 算法设计思路.13 3、 实验总结.13 4、 AC 代码.13 实验 E-可判定的 DFA 的空问题.14 1、 问题描述.14 2、 算法设计思路.15 3、 实验总结.15
2、 4、 AC 代码.15实验实验 A- ADFA 的可判定性的可判定性1、问题描述Problem descriptionA ADFADFA=|B|B 是是 DFADFA，w w 是串，是串，B B 接收接收 ww证明：证明：A ADFADFA是可判定的。是可判定的。 实验方法实验方法: :编写一个算法编写一个算法/ /程序，对程序，对于任意给定的输入，可以判定于任意给定的输入，可以判定 A ADFADFA。 Input有多个测试序列，测试结束于测试文件结束；有多个测试序列，测试结束于测试文件结束； 每个测试序列的第一行为几个正整数每个测试序列的第一行为几个正整数 n n m m t t a a
3、 分别表示有分别表示有 n n 个个状态，从状态，从 a a 开始开始 m m 个小写字母组成的字符集，第一个状态默认为起始状态。个小写字母组成的字符集，第一个状态默认为起始状态。t t 个接受状态和个接受状态和 a a 个测试串个测试串, ,接下接下来为一个来为一个 n n 行行 m m 列的矩阵列的矩阵 S, S,其中其中 SijSij表示第表示第 i i 行第行第 j j 列，意义为状态列，意义为状态 i i 经过字母经过字母 j j 到达状态到达状态 SijSij。接下来有。接下来有t t 个数字个数字, ,表示表示 t t 个接受状态值，然后是个接受状态值，然后是 a a 行，每行一
4、个串表示待测试的串。行，每行一个串表示待测试的串。Output对于每个字符串输出对于每个字符串输出 YESYES 表示该表示该 DFADFA 接受该串，接受该串，NONO 表示不接受。表示不接受。Sample Input3 3 1 2 2 3 2 3 3 3 3 3 3 2 a b Sample OutputYES NO2、算法设计思路A:A: 首先将输入的状态转移矩阵保存在 S 数组中，其中其中 Sij表示第 i 行第 j 列，意义为状态 i 经过字母 j 到达状态 Sij。B:B: 对每一个输入的串 W,从 after（after 表示每次转换后的状态，初始为起始状态）开始，按照每一个字符
5、，得到相应的后继状态，保存在 after 中。C:C: 最后判断 acceptafter的值，即串在 DFA 上运行之后最终状态是否可接受。3、实验总结总的来说这一题比较容易（有点太水了） ，只要把输入串的每一个字符按照前面的状态得到后继状态，并不断的走下去，直到串的最后一个字符，就可以得到最后的状态，再根据其是否处在接受态，给出相应的输出4、AC 代码#include #include using namespace std; long n,m,t,a; long s10001000; /存储转移矩阵 long accept1000; /存储接受状态 int main()while(cinn
6、mta)memset(s,0,sizeof(s);memset(accept,0,sizeof(accept);for(int i = 1;isij;for(int i = 0;itemp;accepttemp = 1;while(a-)string temps;cintemps;int after = 1;for(int i = 0;iAB A-AB|a B-BC|b C-CA|CC|c 3 ab ac bc Sample Output yesno no 2、算法设计思路A: 找出所有 A-b 型规则B: 找出所有 A-BC 型规则C: 考察每一个长为 1 的子串D: 考察 L 长度的子串E
7、: 检查起始变元是否在 table0n中3、实验总结（1）刚开始用栈和转移矩阵来进行状态的切换，想要先把 CFG 转换为一个PDA，在根据 PDA 接受串的情况来判断（因为题目要求线性时间复杂度） ，后来发现转换成 PDA 的时候，每一个转移矩阵里应该是一个状态的集合。（2）原本定义一个 set S 来表示转移矩阵，但是觉得这样还不如直接用原来的 CFG 按照某种规则来进行替换，让他的复杂度为线性的。具体线性替换的顺序在 2 中详细介绍了4、AC 代码#include #include #include using namespace std; int main() int n,m;/n 行满
8、足乔姆斯基范式的文法描述, m 行待测字符 串 while(cinn) string *cfg;/CFG 文法描述 cfg=new stringn; for(int i=0;icfgi;/输入 CFG 文法cinm;/输入待测字符串数量 string *str;/待测字符串 str=new stringm; for(int i=0;istri;/输入待测字符串 int *lstr;/待测字符串的长度 lstr=new intm; for(int i=0;ib 型规则 string Ab100; int num=0; for(int i=0;i96 int num2=0; for(int i=0;ik #include #include #include #include0 01 1q0q0q0q1q2q
