用户工具

站点工具


01-基础学习:课程:编译原理:实验:实验一:dfa的可判定性

DFA的可判定性

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

实验代码

adfa.cpp
/*第一行为几个正整数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行,每行一个串表示待测试的串。
*/
#include<iostream>
#include<cstdlib>
using namespace std;
 
int main()
{
	//cout<<"按照说明格式输入:"<<endl;
	int n,m,t,a;		//n个状态,从a开始m个小写字母组成的字母表,t个接受状态,a个测试串
	while(cin>>n>>m>>t>>a)
	{
		int **delta;	//定义转移函数
		delta=new int*[n];
		for(int i=0;i<n;i++)
			delta[i]=new int[m];
 
		//输入转移函数矩阵
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				cin>>delta[i][j];
 
		int *f;			//接受状态集
		f=new int[t];
		//输入接受状态集
		for(int i=0;i<t;i++)
			cin>>f[i];
 
		string *str;		//测试字符串
		str=new string[a];
		//输入测试字符串
		for(int i=0;i<a;i++)
			cin>>str[i];
		int *q;			//定义状态
		q=new int[a];
		for(int i=0;i<a;i++)
			q[i]=0;		
 
		for(int i=0;i<a;i++)
		{
			for(int j=0;j<str[i].length();j++)
			{
				//cout<<"状态 "<<q[i]+1<<" 经 "<<str[i][j]<<" 到状态 "<< delta[q[i]][int(str[i][j]-97)]<<endl;
				q[i]=delta[q[i]][int(str[i][j]-97)];		//DFA运行
				q[i]--;
			}
		}
		/* DFA停止状态测试输出
		for(int i=0;i<a;i++)
			cout<<"q["<<i<<"] = "<<q[i]+1<<endl;*/
 
		for(int i=0;i<a;i++)
		{
			int flag=0;		//接受标志
			for(int j=0;j<t;j++)
			{
				if(q[i]+1==f[j])
					flag=1;
			}
			if(flag==1)
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;
		}
 
		//释放数组
		delete []f;
		delete []q;
		delete []str;
		//释放二维数组
		for(int i=0;i<n;i++)
			delete []delta[i];
		delete []delta;
	}
	return 0;
}
01-基础学习/课程/编译原理/实验/实验一/dfa的可判定性.txt · 最后更改: 2020/04/07 06:34 由 annhe