#include <iostream>
#include <vector>
#include <cstring>
#include "stack"
#include "algorithm"
using namespace std;
int NFAStatusNum,AlphabetNum,StatusEdgeNum,AcceptStatusNum;
char alphabet[1000];
int accept[1000];
int StartStatus;
int isDFAok=1;
int isDFA[1000][1000];
/*
* NFA状态图的邻接表
*/
vector<vector<int>> Dstates;
int Dstatesvisit[1000];
int Dtran[1000][1000];
vector<int> Dtranstart;
vector<int> Dtranend;
int isDtranstart[1000];
int isDtranend[1000];
class Edge{
public:
int to,w,next;
} ;
Edge edge[10000];
int edgetot=0;
int Graph[1000];
void link(int u,int v,int w){
edge[++edgetot].to=v;edge[edgetot].w=w;edge[edgetot].next=Graph[u];Graph[u]=edgetot;
}
void input(){
int u,v,w;
memset(Dtran,-1,sizeof(Dtran));
scanf("%d %d %d %d
",&NFAStatusNum,&AlphabetNum,&StatusEdgeNum,&AcceptStatusNum);
for(int i=1;i<=AlphabetNum;i++){ //读入字母表
scanf("%c",&alphabet[i]);
}
for(int i=1;i<=AcceptStatusNum;i++){
scanf("%d",&accept[i]);
}
//开始状态序号
scanf("%d",&StartStatus);
for(int i=0;i<StatusEdgeNum;i++){
scanf("%d%d%d
",&u,&v,&w);
link(u,v,w);
if(isDFA[u][v]==0){
isDFA[u][v]=1;
}
else{
isDFAok=0;
}
if(w==0){
isDFAok=0;
}
}
//读入测试字符串
}
void e_clouser(vector<int> &T,vector<int> &ans){
int visit[1000];
memset(visit,0,sizeof(visit));
stack<int> Stack;
//T all push in Stack and copy to ans
for (int i=0;i < T.size();++i){
Stack.push(T[i]);
ans.push_back(T[i]);
visit[T[i]]=1;
}
while(Stack.empty()!=1){
int t = Stack.top(); Stack.pop();
for(int p=Graph[t];p!=0;p=edge[p].next){
if(edge[p].w==0){
if(visit[edge[p].to]==0){
visit[edge[p].to]=1;
Stack.push(edge[p].to);
ans.push_back(edge[p].to);
}
}
}
}
sort(ans.begin(),ans.end());
}
void move(vector<int> &T,int a,vector<int> &ans){
int visit[1000];
memset(visit,0,sizeof(visit));
for(int i=0;i<T.size();i++) {
int t=T[i];
for (int p = Graph[t]; p != 0; p = edge[p].next) {
if (edge[p].w == a) {
if (visit[edge[p].to] == 0) {
visit[edge[p].to] = 1;
ans.push_back(edge[p].to);
}
}
}
}
}
bool notin(vector<int> &a,int &U){
for(int i=0;i<Dstates.size();i++){
int ok=1;
if(Dstates[i].size()==a.size()){
for(int j=0;j<a.size();j++){
if(Dstates[i][j]!=a[j]){
ok=0;
break;
}
}
if(ok==1) {
U=i;
return false;
}
}
}
U=Dstates.size();
return true;
}
void nfatodfa(){
vector<int> s,t;
s.push_back(StartStatus);
e_clouser(s,t);
Dstates.push_back(t);
stack<int> Stack;
Stack.push(Dstates.size()-1);
while(Stack.empty()!=1){
int T=Stack.top();Stack.pop();int U;
for(int i=1;i<=AlphabetNum;i++){
vector<int> ans,ans2;
move(Dstates[T],i,ans2);
e_clouser(ans2,ans);
if(notin(ans,U)){
Dstates.push_back(ans);
Stack.push(Dstates.size()-1);
}
Dtran[T][i]=U;
}
}
}
void getDtranStartEnd(){
for(int i=0;i<Dstates.size();i++){
int ok=1;
for(int j=0;j<Dstates[i].size();j++){
if(Dstates[i][j]==StartStatus){
Dtranstart.push_back(i);
isDtranstart[i]=1;
}
if(ok){
for(int k=1;k<=AcceptStatusNum;k++){
if(Dstates[i][j]==accept[k]){
ok=0;
Dtranend.push_back(i);
isDtranend[i]=1;
}
}
}
}
}
}
vector<vector<int>> newDstates;
int newDstatesvisit[1000];
int newDtran[1000][1000];
int set[1000];
vector<int> newDtranstart;
vector<int> newDtranend;
int isnewDtranstart[1000];
int isnewDtranend[1000];
void simple(){
int visit[1000];
memset(visit,0,sizeof(visit));
vector<int> a,b;
//接受结点加入a
for(int i=0;i<Dtranend.size();i++){
a.push_back(Dtranend[i]);
visit[Dtranend[i]]=1;
set[Dtranend[i]]=0;
}
//剩余结点加入b
for(int i=0;i<Dstates.size();i++){
if(visit[i]==0){
b.push_back(i);
set[i]=1;
}
}
newDstates.push_back(a);
newDstates.push_back(b);
while(1){
int ok=0;
for(int i=0;i<newDstates.size();i++){
for (int k = 1; k <= AlphabetNum; k++) {
for(int j=1;j<newDstates[i].size();j++) {
int pp= Dtran[newDstates[i][0]][k];
int u = newDstates[i][j], v = Dtran[u][k];
if (set[v] != set[pp] ) {
//将u剥离
newDstates[i].erase(newDstates[i].begin() + j);
vector<int> temp;
temp.push_back(u);
set[u] = newDstates.size();
newDstates.push_back(temp);
ok = 1;
break;
}
if (ok == 1) break;
}
if(ok==1) break;
}
if(ok==1) break;
}
if(ok==0) break;
}
//isnewDtranstart,isnewDtranend,newDtran
for(int i=0;i<Dstates.size();i++) {
for (int j = 1; j <= AlphabetNum; j++) {
newDtran[set[i]][j]=set[Dtran[i][j]];
}
if(isDtranend[i]==1)
isnewDtranend[set[i]]=1;
if(isDtranstart[i]==1)
isnewDtranstart[set[i]]=1;
}
//isnewDtranstart,isnewDtranend
}
bool dfa(char *S){
int index=0;
int status=0;
for(int i=0;i<newDstates.size();i++){
if(isnewDtranstart[i]==1){
status=i;
}
}
for(int i=0;i<strlen(S);i++) {
//这里我偷懒了,懒得弄个map存映射,直接对这个例子进行操作,就是 S[i]-'a'+1;
int p=S[i]-'a'+1;
status=newDtran[status][p];
}
if(isnewDtranend[status]==1) return true;
else return false;
}
int main() {
freopen("E:\NFATODFA\a.in","r",stdin);
input();
if(isDFAok==0){
printf("This is NFA
");
nfatodfa();
}
else{
printf("This is DNA
");
}
//打印DFA
printf("
Print DFA's Dtran:
");
printf(" DFAstatu a b");
getDtranStartEnd();
for(int i=0;i<Dstates.size();i++){
printf("
");
if(isDtranstart[i]==1)
printf("start ");
else if(isDtranend[i]==1)
printf("end ");
else printf(" ");
printf("%5c ",i+'A');
for(int j=1;j<=AlphabetNum;j++)
printf("%5c ",Dtran[i][j]+'A');
}
printf("
Print simple DFA's Dtran:
");
simple();
printf(" DFAstatu a b");
for(int i=0;i<newDstates.size();i++){
printf("
");
if(isnewDtranstart[i]==1)
printf("start ");
else if(isnewDtranend[i]==1)
printf("end ");
else printf(" ");
printf("%5c ",i+'A');
for(int j=1;j<=AlphabetNum;j++)
printf("%5c ",newDtran[i][j]+'A');
}
printf("
");
char S[1000];
while(scanf("%s
",S)!=EOF){
if(dfa(S)){
printf("%s belongs to the DFA
",S);
}
else
printf("%s don't belong to the DFA
",S);
}
return 0;
}