湖南大学-计算理论实验

更新时间:2023-09-15 06:18:01 阅读量: 资格考试认证 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

目录

实验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 4、 AC代码 ....................................................................................................... 15

实验A---- ADFA的可判定性

1、

Problem description ADFA={< B,w >|B是DFA,w是串,B接收w}证明:ADFA是可判定的。 实验方法:编写一个算法/程序,对于任意给定的输入,可以判定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

2、 算法设计思路

A:首先将输入的状态转移矩阵保存在S数组中,其中其中S[i][j]表示第i行第j列,意义为状态i经过字母j到达状态S[i][j]。

B:对每一个输入的串W,从after(after表示每次转换后的状态,初始为起始状态)开始,按照每一个字符,得到相应的后继状态,保存在after中。

C:最后判断accept[after]的值,即串在DFA上运行之后最终状态是否可接受。

3、 实验总结

总的来说这一题比较容易(有点太水了),只要把输入串的每一个字符按照前面的状态得到后继状态,并不断的走下去,直到串的最后一个字符,就可以得到最后的状态,再根据其是否处在接受态,给出相应的输出

4、 AC代码

#include #include using namespace std; long n,m,t,a;

long s[1000][1000]; //存储转移矩阵 long accept[1000]; //存储接受状态 int main(){

while(cin>>n>>m>>t>>a){ memset(s,0,sizeof(s));

memset(accept,0,sizeof(accept)); for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++) cin>>s[i][j]; }

for(int i = 0;i>temp;

accept[temp] = 1; }

while(a--){

string temps; cin>>temps;

int after = 1;

for(int i = 0;i

if(accept[after]==1)

cout<<\ else

cout<<\ }} return 0; }

实验B----CFG是P成员

1、 问题描述

Problem description 上下文无关文法CFG G是否派生某个串W。采用动态规划(Dynamic Programming)设计一个一个多项式时间的验证算法。 Input 输入第一行为一个正整数n,接下来n行为一个满足乔姆斯基范式的文法描述。然后一个正整数m,接下来m行为m个小写字母组成的字符串(长度小于100) 表示m个待测试的串。 Output 对于每一个测试串返回\或者\,表示该串是否能被文法派生出来。 Sample Input 4 S->AB A->AB|a B->BC|b C->CA|CC|c 3 ab ac bc Sample Output yes no no

2、 算法设计思路

A: 找出所有A->b型规则 B: 找出所有A->BC型规则 C: 考察每一个长为1的子串 D: 考察L长度的子串

E: 检查起始变元是否在table[0][n]中

3、 实验总结

(1)刚开始用栈和转移矩阵来进行状态的切换,想要先把CFG转换为一个PDA,在根据PDA接受串的情况来判断(因为题目要求线性时间复杂度),后来发现转换成PDA的时候,每一个转移矩阵里应该是一个状态的集合。 (2)原本定义一个set S来表示转移矩阵,但是觉得这样还不如直接用原来的CFG按照某种规则来进行替换,让他的复杂度为线性的。具体线性替换的顺序在2中详细介绍了

4、 AC代码

#include #include #include using namespace std; int main() {

int n,m; 串 while(cin>>n) { string *cfg; cfg=new string[n]; for(int i=0;i>cfg[i]; cin>>m; string *str;

//n行满足乔姆斯基范式的文法描述, m行待测字符

//CFG文法描述

//输入CFG文法

//输入待测字符串数量 //待测字符串

本文来源:https://www.bwwdw.com/article/znvh.html

Top