湖南大学-计算理论实验

发布时间 : 2024/5/22 3:26:57 星期三 文章湖南大学-计算理论实验更新完毕开始阅读

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文法

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

str=new string[m]; for(int i=0;i>str[i]; //输入待测字符串 int *lstr; //待测字符串的长度 lstr=new int[m]; for(int i=0;ib型规则 string Ab[100]; int num=0;

for(int i=0;i96 && cfg[i][k]<123) { Ab[num]+=cfg[i][0]; Ab[num]+=cfg[i][k]; num++; } } }

//找出所有A->BC型规则 string ABC[100]; int num2=0;

for(int i=0;i

} } //考察每一个长为1的子串 for(int i=0;ik

&&

{ cout<<\ } else { cout<<\ } } delete []cfg; delete []str; for(int i=0;i

return 0; }

实验C----NFA转换为DFA

1、 问题描述

Problem description 有限状态自动机（FSM \或者FSA \）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。 Input 输入第一行只有一个正整数t，表示有t个测试数据（意味着t个NFA）t≤10; 对于每组测试数据（每个NFA），首先是3个正整数n,Q0,f，分别表示状态数、起始状态集合和接受状态集合的特征串对应的整数。n≤10;Q0,f < 2n; 接下来两行是NFA的转移函数矩阵，第一行是每个状态在输入为0的状态转移情况，用特征串对应的整数表示；第二行是每个状态在输入为1的状态转移情况。 Output 对于每个NFA，输出四行表示与之等价的DFA。输出格式如下： 第一行3个空格隔开的整数a b c，分别表示DFA的状态数，接受状态数，起始状态的编号（从0开始对状态编号）。要求 a < 65536。b，c ≤ a 第二行b个空格分隔的整数，表示每个接收状态的编号,每个编号的值一定在[0,a)之间。 第三行、第四行每行a个空格分隔的整数，表示DFA的转移函数矩阵，第三行第i个值ui表示状态转移函数的一项δ（qi，0）→ui，