实验一 利用子集法构造 DFA一、实验目的 掌握将非确定有限自动机确定化的方法和过程二、实验要求及内容 实验要求：1.输入一个 NFA，输出一个接受同一正规集的 DFA；2.采纳 C++语言，实现该算法；3.编制测试程序；4.调试程序。 实验步骤：1.输入一个 NFA 关系图；2.通过一个转换算法将 NFA 转换为 DFA；3.显示 DFA 关系图。 三、实验环境 计算机、Windows 操作系统、Visual C++ 程序集成环境。四、程序代码#include "stdafx.h"#include
#include#include#include#includeusing namespace std;struct edge{int start,end;char c;}E[100],Ekong[100];//E 保存所有的边，Ekong 保存转换字符为空的边struct State{int H[100];//状态集合int count;//状态集合中的元素个数int flag;//是否是接受状态int mark;//状态编号};int n;//n:边数int nk=0;//空字符转换的边数int first,accept;//开始状态，接受状态char alpha[100];//输入字母表,#代表空串int numof_char=0;//字母表中的字符个数int useof_char[256];//该转换字符是否用过int f[200];//状态属性标志：0 表示始态，1 表示接受态，-1 表示中间态State DFA[100];//DFA 状态集int useof_DFA[100];//标志构造出来的状态是否已存在int numof_Dtran=0;//最后得到的 DFA 中的状态数char Dtran[100][100];//DFA 状态转换表void input(){int i,s,e;char ch;cout<<"请输入转换的有向边数 n："<>n;cout<<"请输入 NFA 的开始状态："<>first;cout<<"请输入 NFA 的接受状态(输入-1 结束)："<>accept;while(accept!=-1){f[accept]=1;cin>>accept;}cout<<"请输入 NFA，起点，终点，转换字符('#'表示空字符)："<>s>>e>>ch;E[i].start=s;E[i].end=e;E[i].c=ch;if(ch!='#'&&!useof_char[ch]){alpha[numof_char++]=ch;useof_char[ch]=1;}if(ch=='#'){Ekong[nk].start=s;Ekong[nk].end=e;Ekong[nk].c=ch;nk++;}}}State move(State T,char s)//c!='#'{State temp;temp.count=0;temp.mark=T.mark;int i,j=0,k=0;for(i=0;i
