#include<bits/stdc++.h>
using namespace std;
struct GRAM
{
//$代表空
string a;
string b;
string c;
};
int exit(string s,string d)
{
if(d!=""&&d.find(s)>=0&&d.find(s)<=d.length()-1)
return 1;
else
return 0;
}
int main()
{
int num,len;
GRAM gram[100];
GRAM gram1[100];
int time=0,n,n1;
cout<<"请输入图结构（以#结束):"<<endl;
for(len=0;len<100;len++)
{
cin>>gram[len].a;
if(gram[len].a=="#")
break;
else
{
cin>>gram[len].b;
cin>>gram[len].c;
}
}
num=len;
//初始化
GRAM dfa[100];
dfa[0].a=gram[0].a;
//填表
time++;
for(int i=0;i<100;i++)
{
for(int j=0;j<dfa[i].a.length();j++)
{
//添加b
for(int k=0;k<num;k++)
{
if(dfa[i].a[j]==gram[k].a[0])
{
if(gram[k].b!="$")
{
dfa[i].b+=gram[k].b;
}
else
dfa[i].b+="";
}
}
//去除相同的字母
string ustr(dfa[i].b);
sort(ustr.begin(), ustr.end());
ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
dfa[i].b=ustr;
}
for(n=0;n<time;n++)
{
if(dfa[i].b==dfa[n].a)
{
break;
}
}
if(n==time)
{
dfa[time].a=dfa[i].b;
time++;
}
//添加c
for(int j=0;j<dfa[i].a.length();j++)
{
for(int k=0;k<num;k++)
{
if(dfa[i].a[j]==gram[k].a[0])
{
if(gram[k].c!="$")
{
dfa[i].c+=gram[k].c;
}
else
dfa[i].c+="";
}
}
//去除相同的字母
string ustr(dfa[i].c);
sort(ustr.begin(), ustr.end());
ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
dfa[i].c=ustr;
}
for(n1=0;n1<time;n1++)
{
if(dfa[i].c==dfa[n1].a)
{
break;
}
}
if(n1==time)
{
dfa[time].a=dfa[i].c;
time++;
}
}
cout<<"NFA-->DFA:"<<endl;
for(int i=0;i<time-1;i++)
{
cout<<dfa[i].a<<" "<<dfa[i].b<<" "<<dfa[i].c<<endl;
}
cout<<"最后图中的状态为："<<endl;
for(int i=0;i<time-1;i++)
{
cout<<dfa[i].a<<endl;
}
//将DFA以及最小化的结果打印出来
string part[100]; //保存最后图中的状态
string part1[100]; //保存终止状态
for(int i=0;i<time-1;i++)
{
part[i]=dfa[i].a;
}
for(int i=0;i<time-1;i++)
{
cout<<i+1<<" ";
std::stringstream ss;
std::string str;
ss<<i+1;
ss>>str;
gram1[i].a=str;
string flags="Z";
if(exit(flags,part[i])==1)
{
part1[1]+=str;
}
else
{
part1[0]+=str;
}
for(int j=0;j<time-1;j++)
{
if(dfa[i].b==part[j])
{
cout<<j+1<<" ";
std::stringstream ss1;
std::string str1;
ss1<<j+1;
ss1>>str1;
gram1[i].b=str1;
}
}
for(int k=0;k<time-1;k++)
{
if(dfa[i].c==part[k])
{
cout<<k+1<<" ";
std::stringstream ss2;
std::string str2;
ss2<<k+1;
ss2>>str2;
gram1[i].c=str2;
}
}
cout<<endl;
}
int time1=1;
string end=part1[1];//保存终止状态
string start=part1[0]; //保存起始状态
for(int k=0;k<time-1,k+1<time-1;k++)
{
for(int j=0;j<=part1[0].length();j++)
{
if(gram1[k].a[0]==part1[0][j])
{
string s=gram1[k].b+gram1[k].c;
if(exit(s,part1[0])==0)
{
time1++;
part1[time1]=gram1[k].a;
string word=gram1[k].a;
size_t index=part1[0].find(word);
part1[0].erase(index,index);
}
// cout<<part[0]<<endl;
}
}
}
for(int k=0;k<time-1;k++)
{
for(int j=0;j<part1[1].length();j++)
{
if(gram1[k].a[0]==part1[1][j])
{
string s=gram1[k].b+gram1[k].c;
if(exit(s,part1[1])==0)
{
time1++;
part1[time1]=gram1[k].a;
string word=gram1[k].a;
size_t index=part1[1].find(word);
part1[1].erase(index,index);
}
}
}
}
part1[time1+1]=part1[1];
part1[1]=part1[0];
for(int k=0;k<time-1;k++)
{
string s=gram1[k].b+gram1[k].c;
for(int l=0;l<time-1;l++)
{
string s1=gram1[l].b+gram1[l].c;
if(s1==s&&l>k&&gram1[k].a!=end&&gram1[l].a!=end)
{
//cout<<l<<endl;
part1[k+1]+=part1[l+1];
part1[l+1]="";
}
}
}
cout<<"最终状态为："<<endl;
for(int h=1;h<=time1;h++)
{
if(part1[h]!="")
cout<<"{"<<part1[h]<<"}"<<endl;
}
int h1;
for(h1=1;h1<=time1;h1++)
{
if(part1[h1]==part1[time1+1])
{
break;
}
}
if(h1==time1+1)
cout<<"{"<<part1[time1+1]<<"}"<<endl;
cout<<"最小化状态"<<endl;
for(int h=0;h<time-1;h++)
{
for(int k=1;k<=time1+1;k++)
{
if(exit(gram1[h].a,part1[k])==1)
{
cout<<part1[k][0]<<" " ;
break;
}
}
for(int k=1;k<=time1+1;k++)
{
if(exit(gram1[h].b,part1[k])==1)
{
cout<<part1[k][0]<<" " ;
break;
}
}
for(int k=1;k<=time1+1;k++)
{
if(exit(gram1[h].c,part1[k])==1)
{
cout<<part1[k][0]<<" " ;
break;
}
}
cout<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
stru
阅读背景：
编译原理最小化
来源：互联网
分享到：
