实验E----可判定的DFA的空问题 |
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
Total submit users: 138, Accepted users: 130 |
Problem 13122 : No special judgement |
Problem description |
EDFA={< B >|B是DFA,且L(A)=Ф} 证明:EDFA是可判定的语言。 实验方法:编写一个算法/程序,对于任意给定的输入(/确定性有限状态自动机DFA),可以判定EDFA。 |
Input |
有多个测试序列,测试结束于测试文件结束; |
Output |
对于每个输入的DFA,输出”YES”,如果该DFA确实不接受任何串;否则,输出”NO”。 |
Sample Input |
1 2 |
Sample Output |
NO |
Judge Tips |
样例中2个DFA,第一个是接受所有输入的DFA,第二个是拒绝所有输入的DFA,所以,第一个DFA输出”NO”,而第二个是”YES”。 |
1、算法设计思路
A: <DFA B>是否接受w的问题。ADFA是可判定的。ANFA是可判定的。ARES是可判定的。EDFA是可判定的。EQDFA是可判定的。P100。核心思想:图灵机跟踪DFA的状态和当前位置,状态和位置的变化由转移函数决定。
B: DFA不接受任意串存在以下几种情况:没有接受状态、接受状态独立、接受状态和起始状态不在同一个团中;基于以上三种情况编写代码
2、实验总结
不要去根据DFA可能接受某一个串去判断一个DFA大的可判定性,而是从相反的方向来考虑问题:即判断DFA是否拒绝所有的串。DFA拒绝所有的串只可能存在以上三种情况。
3、AC代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
bool vis[110];
bool ac[110];
int num[110][110];
int n, m, f, p, cnt;
bool dfs(int k)
{
vis[k] = 1;
if(ac[k])
{
return 1;
}
for(int i = 0; i < m; i++)
if(!vis[num[k][i]] && dfs(num[k][i]))
{
return 1;
}
return 0;
}
int main()
{
while(scanf("%d%d", &n, &m)!=EOF)
{
memset(vis, 0, sizeof(vis));
memset(ac, 0, sizeof(ac));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d", &num[i][j]);
scanf("%d", &f);
for(int i = 0; i < f; i++)
{
scanf("%d", &p), ac[p] = 1;
}
if(f)
if(dfs(0))
printf("NO\n");
else
printf("YES\n");
else
printf("YES\n");
}
return 0;
}