#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=1001;
/*
NFA五元组
M={K,A,f,S,Z};
K::状态集合
A::字母表
F::转换函数
S::开始状态
Z::结束状态
*/
/*状态集合K中的结点*/
string node;
/*字母表A中的符号*/
string cas;
//NFA边数
int N;
/*转换函数f*/
struct f
{
string u,w,v;
//起点，条件，终点
};
struct change
{
string ta;
string arr[maxn];
};
void none(int a)
{
int i;
for(i=0; i<a; i++)
{
cout<<' ';
}
}
void Sort(string &a)
{
int i,j;
char b;
for(j=0; j<a.length(); j++)
for(i=0; i<a.length(); i++)
if(node.find(a[i])>node.find(a[i+1]))
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
}
}
void eclouse(char c,string &he,f b[])
{
int k;
for(k=0; k<N; k++)
{
if(c==b[k].u[0])
if(b[k].w=="*")
{
if(he.find(b[k].v)>he.length())
he+=b[k].v;
eclouse(b[k].v[0],he,b);
}
}
}
void movex(change &he,int m,f b[])
{
int i,j,k,l;
k=he.ta.length();
l=he.arr[m].length();
for(i=0; i<k; i++)
for(j=0; j<N; j++)
if((cas[m]==b[j].w[0])&&(he.ta[i]==b[j].u[0]))
if(he.arr[m].find(b[j].v[0])>he.arr[m].length())
he.arr[m]+=b[j].v[0];
for(i=0; i<l; i++)
for(j=0; j<N; j++)
if((cas[m]==b[j].w[0])&&(he.arr[m][i]==b[j].u[0]))
if(he.arr[m].find(b[j].v[0])>he.arr[m].length())
he.arr[m]+=b[j].v[0];
}
void output(int len,int h,change *t)
{
int i,j,m;
cout<<" I ";
for(i=0; i<len; i++)
cout<<" I"<<cas[i]<<" ";
cout<<endl<<"*********************"<<endl;
for(i=0; i<h; i++)
{
cout<<' '<<t[i].ta;
m=t[i].ta.length();
for(j=0; j<len; j++)
{
none(8-m);
m=t[i].arr[j].length();
cout<<t[i].arr[j];
}
cout<<endl;
}
}
int main()
{
freopen("sample.in","r",stdin);
f *b=new f[maxn];
int i,j,k,m,n,h,x,y,len;
bool flag;
string jh[maxn],z,z1,sta;
/*NFA输入信息*/
/*NFA转换函数个数*/
cout<<"input the num of the function of the NFA::\n";
cin>>N;
/*转换函数*/
cout<<"input the "<<N<<" functions of the NFA::[the none set is *]\n";
for(i=0; i<N; i++)
{
cin>>b[i].u;
cin>>b[i].w>>b[i].v;
}
/*统计字母表A的大小*/
for(i=0; i<N; i++)
{
if(node.find(b[i].u)>node.length())
node+=b[i].u;
if(node.find(b[i].v)>node.length())
node+=b[i].v;
if((cas.find(b[i].w)>cas.length())&&(b[i].w!="*"))
cas+=b[i].w;
}
len=cas.length();
/*输入结束状态Z*/
cout<<"input the end state of the NFA:\n";
bool fl=true;
while(fl)
{
cin>>z;
fl=false;
for(i=0; i<z.length(); i++)
{
if(node.find(z[i])>node.length())
{
cout<<"Sorry!!the Z state not in the K states\n";
fl=true;
break;
}
}
}
//子集算法
change *t=new change[maxn];
t[0].ta=b[0].u;
h=1;
eclouse(b[0].u[0],t[0].ta,b);
for(i=0; i<h; i++)
{
for(j=0; j<t[i].ta.length(); j++)
for(m=0; m<len; m++)
eclouse(t[i].ta[j],t[i].arr[m],b);
for(k=0; k<len; k++)
{
movex(t[i],k,b);
for(j=0; j<t[i].arr[k].length(); j++)
eclouse(t[i].arr[k][j],t[i].arr[k],b);
}
for(j=0; j<len; j++)
{
Sort(t[i].arr[j]);
for(k=0; k<h; k++)
{
flag=operator==(t[k].ta,t[i].arr[j]);
if(flag)
break;
}
if(!flag&&t[i].arr[j].length())
t[h++].ta=t[i].arr[j];
}
}
cout<<endl<<"the change state of Matrix:::"<<endl;
output(len,h,t);
//状态重新命名
string *d=new string[h];
node.erase();
cout<<endl<<"rename:::"<<endl;
for(i=0; i<h; i++)
{
sta=t[i].ta;
t[i].ta.erase();
t[i].ta='A'+i;
node+=t[i].ta;
cout<<"{"<<sta<<"}="<<t[i].ta<<endl;
for(j=0; j<z.length(); j++)
if(sta.find(z[j])<sta.length())
d[1]=z1+=t[i].ta;
for(k=0; k<h; k++)
for(m=0; m<len; m++)
if(sta==t[k].arr[m])
t[k].arr[m]=t[i].ta;
}
for(i=0; i<node.length(); i++)
if(z1.find(node[i])>z1.length())
d[0]+=node[i];
/*DFA::*/
z=z1;
cout<<endl<<"DFA::"<<endl;
output(len,h,t); //输出DFA
cout<<endl<<"the end state ::"<<z<<endl;
//DFA最小化
m=2;
sta.erase();
flag=0;
for(int i=0; i<m; i++)
{
y=m;
for(int j=0; j<d[i].length(); j++)
{
for(int n=0; n<y; n++)
{
if(d[n].find(t[node.find(d[i][j])].arr[k])<d[n].length()||t[node.find(d[i][j])].arr[k].length()==0)
{
if(t[node.find(d[i][j])].arr[k].length()==0)
x=m;
else
x=n;
if(!sta.length())
{
sta+=x+48;
}
else if(sta[0]!=x+48)
{
d[m]+=d[i][j];
flag=1;
d[i].erase(j,1);
j--;
}
break;
}
}
}
if(flag)
{
m++;
flag=0;
}
sta.erase();
}
/*划分子集*/
cout<<endl<<"divide the set ::";
for(i=0; i<m; i++)
cout<<"{"<<d[i]<<"} ";
cout<<endl;
//状态重新命名
change *md=new change[m];
node.erase();
cout<<endl<<"rename ::"<<endl;
for(i=0; i<m; i++)
{
md[i].ta='A'+i;
node+=md[i].ta;
cout<<"{"<<d[i]<<"}="<<md[i].ta<<endl;
}
for(i=0; i<m; i++)
for(k=0; k<len; k++)
for(j=0; j<h; j++)
{
if(d[i][0]==t[j].ta[0])
{
for(n=0; n<m; n++)
{
if(!t[j].arr[k].length())
break;
else if(d[n].find(t[j].arr[k])<d[n].length())
{
md[i].arr[k]=md[n].ta;
break;
}
}
break;
}
}
z1.erase();
for(i=0; i<m; i++)
for(j=0; j<z.length(); j++)
if(d[i].find(z[j])<d[i].length()&&z1.find(md[i].ta))
z1+=md[i].ta;
z=z1;
cout<<endl<<"the min of the DFA"<<endl;
output(len,m,md);
cout<<endl<<"the end state ::"<<z<<endl;
return 0;
}
#include <iostream>
#include <string>
#include
阅读背景：
NFA(子集算法,DFA最小化)代码实现
来源：互联网
分享到：
