难过反义词NFA的确定化
实验⼀ NFA的确定化
⼀、实验⽬的
1.通过本次实验，加深对正则表达式、NFA、DFA及其识别的语⾔的理解;
2.掌握从NFA到DFA的转换，以及⽤⼦集法把NFA转换成DFA理论，编程实现将NFA(不确定有穷⾃动机)转换为DFA(确定有穷⾃动机)。
⼆、实验内容
春天的英语将给定的NFA（五元组）进⾏确定化，输出等价的DFA。要求选择合适的NFA的存储格式，并进⾏正确性检查。
三、实验原理
⼀个确定的有限⾃动机（DFA）M可以定义为⼀个五元组，M＝（K，∑，F，S，Z），其中：
（1） K是⼀个有穷⾮空集，集合中的每个元素称为⼀个状态；
（2） ∑是⼀个有穷字母表，∑中的每个元素称为⼀个输⼊符号；
（3） F是⼀个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表⽰当前
状态为R，如果输⼊字符a，则转到状态Q，状态Q称为状态R的后继状态；
（4） S∈K，是惟⼀的初态；
（5） Z∈K，是⼀个终态集。
⼀个不确定有限⾃动机（NFA）M可以定义为⼀个五元组，M＝（K，∑，F，S，Z），其中：
（1） k是⼀个有穷⾮空集，集合中的每个元素称为⼀个状态；
（2） ∑是⼀个有穷字母表，∑中的每个元素称为⼀个输⼊符号；
（3） F是⼀个从K×∑→K的⼦集的转换函数；
（4） S∈K，是⼀个⾮空的初态集；
（5） Z∈K，是⼀个终态集。
由定义可见，不确定有限⾃动机NFA与确定有限⾃动机DFA的主要区别是：
（1）NFA的初始状态S为⼀个状态集，即允许有多个初始状态；
（2）NFA中允许状态在某输出边上有相同的符号，即对同⼀个输⼊符号可以有多个后继状态。即DFA中的F是单值函数，⽽NFA中的F是多值函数。
因此，可以将确定有限⾃动机DFA看作是不确定有限⾃动机NFA的特例，能被DFA所接受的符号串必能被NFA所接受。对于每⼀个NFA M1总存在⼀个DFA M2，使得L（M1）＝L（M2）。即⼀个不确定有限⾃动机能接受的语⾔总可以找到⼀个等价的确定有限⾃动机来接受该语⾔ 。
四、算法思想
1．根据⼦集构造法对NFA确定化
（1）假定I是M’的状态集的⼦集，定义集合I的ε闭包ε-closure（I）为：
若s∈I，则s∈ε-closure（I）；
若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。
（2）假定I是M’的状态集的⼦集，定义Ia=ε__CLOSURE(J)，其中，J是那些可以从I中某⼀状态结点出发经过⼀条a弧⽽到达的状态结点的全体。
正十六烷（3）构造⼀张共有K+1列的表（K为变换个数）该表的⾸列为ε-closure（X）。检查该⾏上的所有状态⼦集，看它们是否已出现在表的第⼀列，将未曾出现者填⼊后⾯空⾏的第⼀列。重复上述过程，直⾄出现在第I+1列上得所有状态⼦集都已经在第⼀列上出现。
2.DFA的化简
将终态组和⾮终态组的Ik(k=a,b……)求出，若所有集合都是组集合的⼦集，则DFA已最⼩化。
五、具体实现
#include<bits/stdc++.h>
#define MAXS 100
using namespace std;
string NODE;//结点集合
string CHANGE;//终结符集合
int N;//NFA边数
struct edge{
string first;
string change;
string last;
};
struct chan{
string ltab;
string jihe[MAXS];
};
void kong(int a){
int i;
for(i=0;i<a;i++) cout<<" ";
}
//排序
void paixu(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 eclou(char c,string &he,edge b[]){
int k;
for(k=0;k<N;k++){
if(c==b[k].first[0])
if(b[k].change=="*"){
if(he.find(b[k].last)>he.length())
he+=b[k].last;
eclou(b[k].last[0],he,b);
}
}
}
void move(chan &he,int m,edge b[]) {
int i,j,k,l;
k=he.ltab.length();
k=he.ltab.length();
l=he.jihe[m].length();
for(i=0;i<k;i++)
for(j=0;j<N;j++)
if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))
if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())
he.jihe[m]+=b[j].last[0];
for(i=0;i<l;i++)
for(j=0;j<N;j++)
if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))
if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())
he.jihe[m]+=b[j].last[0];
}
//输出
void outputfa(int len,int h,chan *t){
int i,j,m;
cout<<"I"<<" ";
for(i=0;i<len;i++)
cout<<"I"<<CHANGE[i]<<" ";
cout<<endl<<"-------------------------"<<endl;
for(i=0;i<h;i++){
cout<<""<<t[i].ltab;
m=t[i].ltab.length();
for(j=0;j<len;j++){
kong(8-m);
m=t[i].jihe[j].length();
cout<<t[i].jihe[j];
}
cout<<endl;
}
}
int main(){
edge *b=new edge[MAXS];
int i,j,k,m,n,h,x,y,len;
bool flag;
string jh[MAXS],endnode,ednode,sta;
cout<<"请输⼊NFA各边信息（起点条件【空为*】终点），以#结束："<<endl; for(i=0;i<MAXS;i++){
cin>>b[i].first;
if(b[i].first=="#") break;
cin>>b[i].change>>b[i].last;
}
N=i;
for(i=0;i<N;i++){
if(NODE.find(b[i].first)>NODE.length())
NODE+=b[i].first;
if(NODE.find(b[i].last)>NODE.length())
NODE+=b[i].last;
if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!="*"))
CHANGE+=b[i].change;
}
len=CHANGE.length();
cout<<"结点中属于终态的是："<<endl;
cin>>endnode;
for(i=0;i<endnode.length();i++)
if(NODE.find(endnode[i])>NODE.length()){
cout<<"所输终态不在集合中，错误！"<<endl;
return 0;
}
chan *t=new chan[MAXS];
t[0].ltab=b[0].first;
h=1;
eclou(b[0].first[0],t[0].ltab,b);//求e-clou
//cout<<t[0].ltab<<endl;
for(i=0;i<h;i++){
for(i=0;i<h;i++){
for(j=0;j<t[i].ltab.length();j++)
for(m=0;m<len;m++)
eclou(t[i].ltab[j],t[i].jihe[m],b);//求e-clou
for(k=0;k<len;k++){
/
/cout<<t[i].jihe[k]<<"->";
move(t[i],k,b);//求move(I,a)
//cout<<t[i].jihe[k]<<endl;
for(j=0;j<t[i].jihe[k].length();j++)
eclou(t[i].jihe[k][j],t[i].jihe[k],b);
}
for(j=0;j<len;j++){
paixu(t[i].jihe[j]);//对集合排序以便⽐较
for(k=0;k<h;k++){
flag=operator==(t[k].ltab,t[i].jihe[j]);
if(flag) break;
}
if(!flag&&t[i].jihe[j].length()) t[h++].ltab=t[i].jihe[j];
}
}
cout<<endl<<"状态转换矩阵如下："<<endl;
outputfa(len,h,t);//输出状态转换矩阵
//状态重新命名
string *d=new string[h];
cout<<endl<<"重命名："<<endl;
for(i=0;i<h;i++){
sta=t[i].ltab;
t[i].a();
t[i].ltab='A'+i;
房屋买卖委托书
NODE+=t[i].ltab;
cout<<"{"<<sta<<"}="<<t[i].ltab<<endl;
for(j=0;j<endnode.length();j++)
if(sta.find(endnode[j])<sta.length())
d[1]=ednode+=t[i].ltab;// d[1]=ednode+=t[i].ltab;
for(k=0;k<h;k++)
for(m=0;m<len;m++)
if(sta==t[k].jihe[m]) t[k].jihe[m]=t[i].ltab;
}
for(i=0;i<NODE.length();i++)
if(ednode.find(NODE[i])>ednode.length())
d[0]+=NODE[i];
endnode=ednode;
cout<<endl<<"DFA如下："<<endl;
outputfa(len,h,t);
//输出DFA
cout<<"其中终态为："<<endnode<<endl;
m=2;
flag=0;
for(i=0;i<m;i++){
for(k=0;k<len;k++){
y=m;
for(j=0;j<d[i].length();j++){
for(n=0;n<y;n++){
if(d[n].find(t[NODE.find(d[i][j])].jihe[k])<d[n].length()||t[NODE.find(d[i][j])].jihe[k].length()==0) {
if(t[NODE.find(d[i][j])].jihe[k].length()==0)
x=m;
el x=n;
if(!sta.length()){
sta+=x+48;
}
el if(sta[0]!=x+48){
d[m]+=d[i][j];
flag=1;
flag=1;
d[i].era(j,1);
j--;
}
break;
}
仓库可视化管理
}
}
if(flag){
m++;flag=0;
}
长沙古镇牛鞭功效}
}
cout<<endl<<"集合划分：";
for(i=0;i<m;i++)
cout<<"{"<<d[i]<<"}";
cout<<endl;
chan *md=new chan[m];
cout<<endl<<"重命名："<<endl;
for(i=0;i<m;i++){
md[i].ltab='A'+i;
NODE+=md[i].ltab;
cout<<"{"<<d[i]<<"}="<<md[i].ltab<<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].ltab[0]){
for(n=0;n<m;n++){
if(!t[j].jihe[k].length()) break;
el if(d[n].find(t[j].jihe[k])<d[n].length()){
md[i].jihe[k]=md[n].ltab;
break;
}
}
break;
}
}
for(i=0;i<m;i++)
for(j=0;j<endnode.length();j++)
if(d[i].find(endnode[j])<d[i].length()&&ednode.find(md[i].ltab)) ednode+=md[i].ltab;
endnode=ednode;
cout<<endl<<"最⼩化DFA如下："<<endl;
outputfa(len,m,md);
cout<<"其中终态为："<<endnode<<endl;
return 0;
}
