首页 > 代码库 > 利用子集构造法实现NFA到DFA的转换
利用子集构造法实现NFA到DFA的转换
-
概述
NFA非有穷自动机，即当前状态识别某个转换条件后到达的后继状态不唯一，这种自动机不便机械实现，而DFA是确定有限状态的自动机，它的状态转换的条件是确定的，且状态数目往往少于NFA，所以DFA能够比较方便的机械实现且识别能力方面也和NFA相当。本次实验采用子集构造法来实现不带空弧的由NFA到DFA的转换。
子集构造法的算法如下：
设NFA为M=(K,Σ,f,S0,Z)，则构造相应的DFA M′=(Q,Σ,f′,I0,F)
①取I0=S0；
②对于状态集Q中任一尚未标记的状态qi={Si1,Si2,…,Sim},Sik∈K，做：
(1) 标记qi；
(2) 对于每个a∈Σ，置
T=f({Si1,Si2,…,Sim},a)
qj=εCLOSURE(T)
(3) 若qj不在Q中，则将qj作为一个未加标记的状态添加到Q中，且把状态转移f′(qi,a)=qj添加到M′。
③重复进行步骤②，直到Q中不再含有未标记的状态为止。对于由此构造的Q，我们把那些至少含有一个Z中的元素的qi作为M′的终态。
对于如图所示的NFA其在文件中保存的信息如下
转成DFA之后的形式为
重命名为
-
程序整体思路
首先将文件中所给的NFA输入读入程序，在读入过程中将其以图的邻接表的形式保存，其中将状态转移条件记为该边的权值，每种状态记为图的结点，该状态识别状态转移条件(权值)之后到达的状态为该结点的邻接点。
对于上面的例子，将其读入程序中后该图在程序中的逻辑存储结构（图的邻接表）如图所示，其中邻接点中第一个数字表示权值，第二个数字表示所连的结点。
将图读入程序中后，再使用子集构造算法来完成由NFA到DFA的转化。
对于每种状态，其数据结构定义为
1 typedef struct state 2 { 3 set<int> Set; 4 char name; 5 }state;
其中set里存放该状态识别某个条件后所能到达的状态集合的下标，name里存该状态重命名后的名字。
这些状态保存在状态数组States[max]中，状态数组States[max]数据结构定义为
1 state States[max];
子集构造法的过程就是不断向状态数组States[ ]中，添加识别某个条件后，新的未出现的状态的过程。
程序中函数说明
void creatph(algraph &g,FILE *fpr)：将文件内容读入程序，并将其转换为图的邻接表子函数。
int change(algraph g,char p)：将图中结点转化为对应下标子函数。
state move(state s,int n,algraph g)：求当前状态集合的转移集合，即求s状态识别字母n之后的状态集合。
int equalSet(state m,state n)：比较两个状态的set集合内容是否相等，不相等返回0，相等返回1。
void inStates(state &s)：判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组。
void changeToD(algraph g,FILE *fpw)：由NFA转到DFA的主控程序子函数。
程序输入如下图所示
程序输出如下图所示
-
代码清单
1 #include<stdio.h> 2 #include<malloc.h> 3 #include <iostream> 4 #include <fstream> 5 #include <cstring> 6 #include<set> 7 8 using namespace std; 9 10 #define max 50//定义结点最大数量 11 typedef char vertype;//定义结点值域为字符类型 12 char buf[1024];//定义读文件内容时，程序缓冲数组 13 int num;//记录有穷字母表元素的个数 14 int length;//记录States数组的长度 15 16 typedef struct arcnode//图的边信息 17 { 18 int adjvex; 19 int weight;//边所对应的权值 20 struct arcnode *next; 21 }arcnode; 22 23 typedef struct vnode//图的结点类型定义 24 { 25 vertype data; 26 arcnode *next; 27 }vnode,adjlist[max]; 28 29 typedef struct//图的定义 30 { 31 adjlist a; 32 int vexnum,arcnum; 33 }algraph; 34 35 typedef struct state//状态的定义 36 { 37 set<int> Set; 38 char name; 39 }state; 40 41 state States[max]; 42 43 int change(algraph g,char p)//将图中结点转化为对应下标 44 { 45 int i; 46 for(i=0;i<g.vexnum;i++) 47 { 48 if(p==g.a[i].data) 49 return i; 50 } 51 return -1; 52 } 53 54 void creatph(algraph &g,FILE *fpr) 55 { 56 int line = 0; 57 while(!feof(fpr)) 58 { 59 fgets(buf,1024,fpr); 60 if(strlen(buf)>1)//获取文件中图的结点个数 61 { 62 int i = 0; 63 while(buf[i]==‘ ‘) 64 { 65 i++; 66 } 67 68 g.a[line].data=http://www.mamicode.com/buf[i]; 69 g.a[line].next=NULL; 70 line++; 71 } 72 } 73 g.vexnum=line; 74 75 rewind(fpr);//将文件指针返回到开头位置 76 line = 0; 77 arcnode *s; 78 79 while(!feof(fpr))//再次扫描文件将边的信息添上，构造图 80 { 81 int weight=0;//边所对应的权值,每一行权值都从0开始 82 fgets(buf,1024,fpr); 83 if(strlen(buf)>1) 84 { 85 for(int i=0;i<strlen(buf)-1;i++) 86 { 87 if(buf[i]==‘{‘) 88 { 89 weight++; 90 if(num<weight) 91 num=weight; 92 93 i++; 94 if(buf[i]==‘N‘) 95 i=i+4; 96 97 while(buf[i]!=‘}‘) 98 { 99 if(buf[i]!=‘,‘) 100 { 101 //cout<<buf[i];//////////////////////////////// 102 int x = change(g,buf[i]); 103 104 s=(arcnode *)malloc(sizeof(arcnode)); 105 s->adjvex=x; 106 s->weight=weight; 107 s->next=g.a[line].next; 108 g.a[line].next=s; 109 //cout<<line;//////////////////////////////// 110 } 111 i++; 112 } 113 } 114 } 115 line++; 116 } 117 } 118 119 } 120 121 state move(state s,int n,algraph g)//求当前状态集合的转移集合，即求s状态识别字母n之后的状态集合 122 { 123 state temp; 124 arcnode *m; 125 set<int>::iterator itr;//迭代器 126 for(itr = s.Set.begin();itr!=s.Set.end();itr++)//遍历当前s状态中集合元素 127 { 128 int i = *itr; 129 m = g.a[i].next; 130 while(m) 131 { 132 if(m->weight==n) 133 { 134 temp.Set.insert(m->adjvex);//cout<<m->adjvex<<" "; 135 // temp.name=s.name+1;//cout<<temp.name<<endl; 136 } 137 m=m->next; 138 } 139 } 140 return temp; 141 } 142 143 int equalSet(state m,state n)//比较两个状态的set集合内容是否相等 144 { 145 int flag = 1; 146 if(m.Set.size()!=n.Set.size()) 147 { 148 flag = 0; 149 return flag; 150 } 151 152 set<int>::iterator itrm; 153 set<int>::iterator itrn; 154 for(itrm = m.Set.begin(),itrn = n.Set.begin();itrm!=m.Set.end();itrm++,itrn++) 155 { 156 int m = *itrm; 157 int n = *itrn; 158 159 if(m!=n) 160 { 161 flag = 0; 162 break; 163 } 164 } 165 return flag; 166 } 167 168 void inStates(state &s)//判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组 169 { 170 int flag = 0; 171 if(length==0) 172 { 173 States[0]=s; 174 States[0].name=‘A‘; 175 length++; 176 } 177 else 178 { 179 for(int i=0;i<length;i++) 180 { 181 //cout<<equalSet(States[i],s); 182 if(equalSet(States[i],s)==1)//若存在，进行改名 183 { 184 s.name=States[i].name; 185 flag = 1; 186 break; 187 } 188 } 189 190 if(flag == 0)//若不存在，改名后加入States数组 191 { 192 s.name=States[length-1].name+1; 193 States[length]=s; 194 length++; 195 } 196 } 197 } 198 199 void changeToD(algraph g,FILE *fpw) 200 { 201 state s,temp; 202 s.Set.insert(0); 203 s.name=‘A‘; 204 205 inStates(s); 206 207 for(int i=0;i<length;i++) 208 { 209 cout<<"{"; 210 fprintf(fpw,"{"); 211 212 set<int>::iterator itr;//迭代器 213 for(itr = States[i].Set.begin();itr!=States[i].Set.end();itr++)//遍历当前s状态中集合元素 214 { 215 int i = *itr; 216 cout<<g.a[i].data<<","; 217 fprintf(fpw,"%c,",g.a[i].data); 218 } 219 220 cout<<"}"; 221 fprintf(fpw,"}"); 222 223 cout<<States[i].name; 224 fprintf(fpw,"%c",States[i].name); 225 226 for(int j=1;j<=num;j++) 227 { 228 temp = move(States[i],j,g); 229 inStates(temp); 230 //查看temp状态的set集合 231 /* 232 set<int>::iterator itr;//迭代器 233 for(itr = temp.Set.begin();itr!=temp.Set.end();itr++)//遍历当前s状态中集合元素 234 { 235 int i = *itr; 236 cout<<i<<" "; 237 }*/ 238 cout<<temp.name; 239 fprintf(fpw,"%c",temp.name); 240 } 241 cout<<endl; 242 fprintf(fpw,"\n"); 243 } 244 } 245 246 247 int main() 248 { 249 algraph g; 250 251 FILE *fpr = fopen("F:\\test.txt","r"); 252 FILE *fpw = fopen("F:\\testOutput.txt","w"); 253 254 255 /* FILE *fpr = fopen("test.txt","r"); 256 FILE *fpw = fopen("output.txt","w");*/ 257 258 creatph(g,fpr); 259 260 //create测试 261 /* 262 for(int i=0;i<g.vexnum;i++) 263 { 264 cout<<g.a[i].data<<endl;////////////////// 265 266 } 267 */ 268 269 changeToD(g,fpw); 270 //move测试 271 /* 272 state s; 273 s.Set.insert(0); 274 s.Set.insert(2); 275 s.Set.insert(3); 276 s.mark=1; 277 s.name=‘B‘; 278 279 move(s,2,g); 280 */ 281 return 0; 282 }
利用子集构造法实现NFA到DFA的转换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。