基于C语言实现的NFA确定化和DFA最小化.zip

# NFA 确定化和 DFA 最小化 ## 一、实验任务 1. 存储 NFA 与 DFA； 2. 编程实现子集构造法将 NFA 转换成 DFA。 3. 先完善 DFA，再最小化 DFA。 ## 二、实验内容 确定 NFA 与 DFA 的存储格式。要求为 3 个以上测试 NFA 准备好相应有限自动机的存储文件。 用 C 或 Java 语言编写将 NFA 转换成 DFA 的子集构造法的程序。 准备 3 个以上测试 DFA 文件。（提示：其中一定要有没有最小化的 DFA） DFA 手动完善。（状态转换映射要是满映射） 用 C 或 Java 语言编写用等价划分法最小化 DFA 的程序。 其实这部分内容要求没这么简单的，还有验证是否转换成功，怎么验证呢？只要你求出原来的和改后的某个子集（如长度小于某个 N），再证实两个语言集合完全相同。不过当初我忘了这个了，后来验收的时候才发现没写，所以这部分我也不会加进来了。￣ω￣= ## 三、存储格式  ``` 3 // 字符集中的字符个数 (以下两行也可合并成一行) / * o // 以空格分隔的字符集。O代表任意非/和*的字符 5 // 状态个数 (以下两行也可合并成一行) 1 2 3 4 5 // 状态编号。若约定总是用从1开始的连续数字表示，则此行可省略 1 // 开始状态的编号。若约定为1，则此行可省 1 // 结束状态个数。若约定为1，则此行可省略 5 // 结束状态的编号 2 -1 -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态 -1 3 -1 -1 4 3 5 4 3 -1 -1 -1 ``` 这部分不会照搬的，到后面输入会修改。不过大致还是这样的格式。 ## 四、程序设计 实现思路 想想还是写一点点吧，否则感觉缺点什么。 nfa 和 dfa 来看的大致都知道了，转换的话只要是用子集构造法。至于子集构造法怎么样的，大家自己查吧，我要说的就是注意空字符的到达处理，循环需要注意。 而 dfa 最小化是最简单的吧，我反正就是先分为先分为是接受状态的集合和不是接受状态的集合，然后把转换状态相同的分为一个状态就可以了。当然，要修改状态的转换。 **文件说明：** ``` 1. intArr.h intArr.cpp 数组类，用于实现数字集合的并，删除，查找 2. NFA_To_DFA.h NFA_To_DFA.cpp dfa转nfa的类 3. minimalDFA.h minimalDFA.cpp 最小化dfa的类 4. main.cpp 主函数 ``` - **类设计说明** 1）intArr 类 ``` class intarr { public: intarr(); intarr(intarr &arr1); //复制构造函数 int inline getSize(){return size;} //获取集合大小 void cleanArr(); //清空集合元素 void operator &= (int num); //重载&=，并入单个元素 void operator &= (intarr &arr1); //重载&=，并入一个集合 void getSort(); //对集合元素从小到大排序 int &operator[](int i); //重载[]，可以向数组一样获得元素 bool operator == (intarr &arr1); //重载==，判断两个集合是否相等 bool getNum(int num); //判断一个数字是否在集合中 void delNum(int num); //删除一个数字 int getNumber(); //获得创建对象的个数 private: int *arr=NULL; //数组指针 int size; //数组大小 static int number; //创建对象的个数 }; ``` 2） NFA_To_DFA 类 dfa 中的 dfa 集合 ``` struct state { int stateNum; //这个状态的编号 int *nextNum; //根据输入字符将会指向哪些状态 intarr nfaArr; //NFA状态集 bool isMake = false; //是否标记 static int maxNum; //最大状态标号 }; ``` 共享的一个 dfa 状态，作为一个中间状态用于创建新的 dfa 状态 ``` struct sstate { intarr nfaArr; //NFA状态集 int stateNum = 0; }; ``` nfa 转 dfa 的类 ``` class nfa_to_dfa { public: nfa_to_dfa(std::string fn); //默认构造函数 void getIntArr(int num, std::string s); void closure_s(); //空字符匹配 void closure_T(int num, int charNum); //字符集匹配 void inStates(); //是否在当前DFA状态中了 void read(); //读取NFA数据 void convert(); //开始转换 void output(); ~nfa_to_dfa() {} //析构函数 private: std::string charracters; //nfa字符集 int charrLength = 0; //字符集的长度 int statesNumber = 0; //nfa状态个数，默认为0 int currState = 1; //开始状态编号，默认为1,不用输入 int endNum = 1; //nfa接受状态个数，默认为1 int *acceptStates = NULL; //nfa接受状态集 std::string **convertFrom = NULL; //转换表 std::string filePath; //文件输入对象 sstate shareState; //一个共享对象，用于转换 int acceptNum = 0; //转换出的dfa接受状态个数 intarr DfaAcceptstates; //dfa接受状态集 }; ``` 3）minimalDFA 类 最小化 dfa 的一个状态，用结构体描述 ``` struct minState { static int maxNum; //最大状态数 intarr sameState; //相同的输出的状态集合 int minNum; //这个最小dfa的状态标 int *nextState=NULL; //不同输入字符的情况下指向不同状态的集合 int isAcceptState=0; //是否为接受状态 }; ``` 最小化 dfa。算法思想： 先将状态划分为接受状态和非接受状态。对于 dfa 中在输入相同的字符转到相同的状态的状态把这些状态划分到一组。 ``` class minDfa { public: minDfa(std::string str); //构造函数 void read(); //读取数据 void divide(); //划分dfa void output(); //状态集 bool isqueal(); //判断两个最小化dfa是否相等 private: std::string charracters; //字符集 int charLength=0; int stateNum = 0; //状态个数，默认为0 int currState = 1; //开始状态编号，默认为1 int endNum = 1; //接受状态个数，默认为1 int *acceptState = NULL; //接受状态 int **convertFrom = NULL; //转换表 minState *states; //最小化dfa状态集 std::string path; //要读取文件的路劲 }; ``` ## 五、实验测试 - 输入的 nfa 文件中 ``` 第一行 为字符集 ,?表示空字符 第二行 为状态个数，默认为从状态1开始，所以不用输入开始状态 第三行 为行为接受状态个数 第四行 为接受状态 第五行 开始为状态转换表。列为字符集，对应为一个二维数组，在哪个状态输入哪个字符转到哪个状态，-1为错误状态。 ``` - NFA 转换为 DFA 1）nfa_to_dfa 的输入文件 nd：(aa|b)*(a|bb)* ``` ab? 4 1 3 2,1,3, 1,-1,-1, 3,4,-1, -1,3,-1, ``` 2）在文件 dfa_to_nfa 中输出: ``` ab 5 4 1 2 3 5 {1,3,} 2 3 {2,3,} 1 4 {1,3,4,} 2 3 {4,} -1 5 {3,} 5 4 ``` 3）作为 minDfa 的输入文件 dfa： ``` ab 5 4 1 2 3 5 2 3 1 4 2 3 -1 5 5 4 ``` 4）最小化 mindfa 输出 ``` {1,3,} 1: 2 1 isacceptstate:1 {2,} 2: 1 3 isacceptstate:1 {4,} 3: -1 4 isacceptstate:0 {5,} 4: 4 3 isacceptstate:1 *********** ``` ## 六、实验总结 来看怎么写的肯定要失望了，因为除了贴了些类的说明，也�