logo资料库

编译原理 NFA转DFA实验报告.docx

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：docx 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    1.实验目的 输入： 非确定有限（穷）状态自动机。 输出： 确定化的有限（穷）状态自动机 2.实验原理 采用子集对 NFA 转 DFA。 （1） 若 NFA 的全部初态为 S1，S2，…，Sn，则令 DFA 的初态为： S＝[S1，S2，…，Sn]， 其中方括号用来表示若干个状态构成的某一状态。 （2）设 DFA 的状态集 K 中有一状态为[Si，Si+1，…，Sj]，若对某符号 a∈∑， 在 NFA 中有 F（{ Si，Si+1，…，Sj}，a）={ Si ’，Si+1 ]不在 K 中，则将其作为新的状态 则令 F（{ Si，Si+1，…，Sj ’，Si+1 ’，Si+1 ’，…，Sk 个转换函数。若[ Si }为 DFA 的一 ’，…，Sk ’ } }，a）={ Si ’，…，Sk ‘ ’ 加入到 K 中。 （3） 重复第 2 步，直到 K 中不再有新的状态加入为止。 （4）上面得到的所有状态构成 DFA 的状态集 K，转换函数构成 DFA 的 F，DFA 的字母表仍然是 NFA 的字母表∑。 （5） DFA 中凡是含有 NFA 终态的状态都是 DFA 的终态。 还可以采用另一种操作性更强的描述方式。首先给出两个相关定义。 假设 I 是 NFA M 状态集 K 的一个子集（即 I∈K），则定义ε-closure（I） 为： （1） 若 Q∈I，则 Q∈ε-closure（I）； （2） 若 Q∈I，则从 Q 出发经过任意条ε弧而能到达的任何状态 Q’，则 Q’ ∈ε-closure（I）。 状态集ε-closure（I）称为状态 I 的ε闭包。 假设 NFA M＝（K，∑，F，S，Z），若 I∈K，a∈∑，则定义 Ia＝ε-closure （J），其中 J 是所有从ε-closure（I）出发，经过一条 a 弧而到达的状态集。 NFA 确定化的实质是以原有状态集上的子集作为 DFA 上的一个状态，将原状 态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后， 状态数可能增加，而且可能出现一些等价状态，这时就需要简化 3.实验内容 ⑴ 实现计算闭包 closure（I）的算法； ⑵ 实现转换函数 move（q，a）的算法； ⑶ 输出 NFA 转 DFA 的结果。
    DFA 和 NFA 存储使用的数据结构为图中的邻接链表。 typedef struct ArcNode{ int adjvex; char info; struct ArcNode *nextarc; //该弧所指向的顶点的位置 //权 //指向下一条弧的指针 }ArcNode; typedef struct VNode{ char data; ArcNode *firstarc; //顶点信息 //指向第一条依附该顶点的弧的指针 }VNode; 每个链表的第一个数据单元为 N(D)FA 的状态，后边的结点存储内容有指向 的边和边上的权值。 例如课本图 4.3 的 NFA M 表示如下： 4.实验心得 1.一般来说，我们接触到的 N(D)FA 图的边数比较少，所以在选取数据结构 存储时，选择邻接链表，相对于使用二维或三维数组，存储效率得到了提高。 2.在求 e_closure 集合时，因为是任意个空转移，因此使用深度遍历的方法， 先求出一个状态的 e_closure 集，再用循环求出状态集的 e_closure 集。 view plain 1. //nfa2dfa.cpp 2. #include 3. #include 4. using namespace std; 5.
    int adjvex;//该弧所指向的顶点的位置 char info; struct ArcNode *nextarc;//指向下一条弧的指针 //权 //顶点信息 //指向第一条依附该顶点的弧的指针 char data; ArcNode *firstarc; 6. const int Max=20; 7. typedef struct ArcNode{ 8. 9. 10. 11. }ArcNode; 12. typedef struct VNode{ 13. 14. 15. }VNode; 16. 17. class Nfa 18. { 19. public: 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. private: 35. 36. 37. 38. 39. 40. 41. 42. }; 43. Nfa::Nfa() 44. { 45. 46. 47. 48. 49. int K; int T[Max][Max]; VNode AdjList[Max]; VNode Dfa[Max]; bool Visited[Max]; char Alp[Max]; K=Alp[0]=0; char c; string line; ArcNode *p; while(cin>>c&&c!='#') //构造函数,初始化 nfa Nfa(); int FindAdj(char c); void AlpAdd(char c); void InitVisit(); void e_closure(int index); void e_closure(int a[]); void move(int I,char a); void move(int I[],char a); void Nfa::Visit_I(int *Temp); //返回 c 状态的在邻接表中的序号 //向字母表集合中添加表中没有的新元素 c //初始化 Visited 集合 //求单一状态 c 的 e-闭包 //重载的状态集合的 e-闭包 //单一状态 I 的 a 弧转换 //重载的状态集合的 a 弧转换 //Visited 转换为集合 void Insert(int I[],int a); //向状态集合中添加新元素 int TAdd(int I[]); void Resault(int i); void Nfa_Dfa(); //状态矩阵 T 中加入新状态集合 //状态数 //状态子集矩阵 //nfa,邻接表的数据结构存储 //dfa //存 e-闭包结果 //字母表,0 号单元用于存放个数
    50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. { AdjList[K].data=c; AdjList[K].firstarc=new ArcNode; AdjList[K].firstarc->nextarc=NULL; K++; } getline(cin,line); while(getline(cin,line)&&line!="#") { int index=FindAdj(line[0]); if(index!=-1) { p=AdjList[index].firstarc; while(p->nextarc) p=p->nextarc; p->nextarc=new ArcNode; p->nextarc->nextarc=NULL; p->nextarc->adjvex=FindAdj(line[4]); p->nextarc->info=line[2]; AlpAdd(p->nextarc->info); } } cout<<"------------------------------"<nextarc; while(p) { cout<<"f("<info<<")="<adjvex<<" "; p=p->nextarc; } if(inextarc) cout<
    //返回序号 //没有查找到则返回-1 if(c=='*') return; for(int i=1;i<=(int)Alp[0];i++) //集合中已含有 } cout<<"------------------------------"<nextarc; while(p) { if(!Visited[p->adjvex]&&p->info=='*') e_closure(p->adjvex); p=p->nextarc; }
    if(p->info==a) p=p->nextarc; Visited[p->adjvex]=true; } Visited[i]=false; InitVisit(); for(int i=1;i<=I[0];i++) ArcNode *p; p=AdjList[I].firstarc->nextarc; while(p) { 137. 138. } 139. 140. void Nfa::move(int I,char a) 141. { 142. 143. 144. 145. 146. 147. 148. 149. 150. } 151. void Nfa::move(int I[],char a) 152. { 153. 154. 155. 156. } 157. 158. void Nfa::Insert(int I[],int index) 159. { 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. } 174. 175. int Nfa::TAdd(int I[]) 176. {//T[0][0]当前集合的个数 177. 178. 179. 180. //I[0]表示元素个数; int flag=0; for(int i=1;i<=I[0];i++) { } I[0]++;flag++; for(int i=I[0];i>flag;i--) int i=1; for(;i<=T[0][0];i++) { return; else if(index>I[i]) I[i]=I[i-1]; I[flag]=index; if(I[0]==T[i][0]) move(I[i],a); if(index==I[i]) //状态集合中已有 index 状态 flag=i; //标记待插入位置
    int j=1; for(;j<=I[0];j++) if(I[j]!=T[i][j]) { } T[T[0][0]][i]=I[i]; return -1; Temp[++Temp[0]]=i; Temp[0]=0; for(int i=0;i
    cout<nextarc; while(p) { cout<<"D("<<(int)Dfa[j].data<<","<info<<")="<adjvex<<" 225. 226. 227. 228. 229. 230. 231. 232. 233. "; p=p->nextarc; } if(jnextarc) cout<nextarc=NULL; for(int ii=1;ii<=Alp[0];ii++) { for(int jj=0;jj<=T[i][0];jj++) Temp[jj]=T[i][jj]; //将选择的第一个状态的 e-闭包加入 C 矩阵中//并标记 move(Temp,Alp[ii]); Visit_I(Temp); if(Temp[0]) { e_closure(Temp); Visit_I(Temp);
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料