ADFA的可判定性

对于这个问题，我们需要知道DFA是什么，以及它的运行原理是怎样的。

DFA及其原理

有穷自动机例子：

那么M1识别正则语言A={w|w至少含有一个1并且在最后的1后面有偶数个0}

那么DFA是什么呢？对，DFA是确定型的有穷自动机，意思就是当机器处于给定的状态并读入下一个输入符号时，可以知道机器的下一个状态是什么。

然后我们可以把上题的描述转换成一个DFA，M1=（Q，，，，F），其中

①Q={1，2，3}。

②={a，b，c}。

③描述为

④1是起始状态。

⑤F={2}。

有穷自动机：

我们把问题搞清楚了，那么久可以开始写代码了。

代码如下：

#include<iostream>
#include<malloc.h>
#include<string.h>
using namespace std;
class DFA{
private:
int num_Q;//状态个数
int acc_Q[100];//接受状态集合
int t;//接受状态个数 
int start_Q;//起始状态
int num_E;//字母表个数
int next_E[100][100];//转移函数
public:
void Init(int n,int m,int t,int accept[],int s[100][100]){//初始化DFA 
num_Q=n;
num_E=m;
for(int i=0;i<t;i++)
acc_Q[i]=accept[i];
start_Q=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
next_E[i][j]=s[i][j];
}
}
this->t=t;
}
bool go(char* w){//接受字符串的运行结果
bool result=false;//运行结果 
int q=start_Q;//当前状态
for(int i=0;i<strlen(w);i++){
q=next_E[q-1][w[i]-'a'];
}
for(int i=0;i<t;i++){
if(q==acc_Q[i])
result=true;
}
return result;
}
};
int main(){
int n,m,t,a,s[100][100],accept[100];
char test[100][100],ch;
while(cin>>n>>m>>t>>a){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
}
}
for(int i=0;i<t;i++){
cin>>accept[i];
}
for(int i=0;i<a;i++){
cin>>test[i];
}
//验证
DFA dfa;
dfa.Init(n,accept,s);
for(int i=0;i<a;i++){
if(dfa.go(test[i]))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
} 

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!