DFA编程实现报告.doc

实验一实验一 DFADFA 的编程实现的编程实现1、、实验目的：实验目的：通过本次实验，加深对 DFA 及其识别的语言的理解，学习对一般的 DFA 的表达 方 法与编程实现方法2、、实验任务：实验任务：编写一个 C 语言程序，模拟实现 DFA 识别字符串的过程3、、实验内容：实验内容： （1）DFA 的输入； （2）DFA 的存储与读写； （3）DFA 的正确性检查； （4）DFA 的语言集列表显示； （5）DFA 的规则字符串判定；四、实验分析：四、实验分析：DFA 的初始化的初始化 一个 DFA 的基本信息 状态集、字符集、开始状态、结束状态集、状态转换 表； 在程序中状态集、字符集、开始状态、结束状态集都用 string 类型来表 示，即可不用考虑用户输入内容的长度但缺点是字符集只能是字符而不可以 是字符串 状态转换表：为三个字符的字符串，第一个为当前状态，第二个为输入字 符，第三个为下一状态 用 vector 容器存放转换函数的内容字符串判断字符串判断 初始化一个 DFA，后可以通过一下算法判断一个字符串是否符合该 DFA判定算法概要： 准备：开始状态 s0, 接受状态集 F, 状态转换表 T(s, c), sS, c c = getchar(); s = 开始状态 s0; while ( c != EOF ) // 输入未结束则循环… { s = T(s, c); if (s == NULL)error();c = getchar(); } if (s  接受状态集 F)accept (); else error ();在实际编写代码中的体现为 void identify() //判断字符串 {cout>str; int i=0; char present=StartStates; while(i容器 存储即可； 实验用例：实验用例：实验结果：实验结果： DFA的初始化判断字符串：显示小于N的语言集：读取DFA文件：五、实验总结：五、实验总结：在这次实验中，学习对一般的 DFA 的表达方法与编程实现方法。

对课本提 供的算法有了更深刻的认识在编写和调试代码的过程中对自身的编程能力也 有了很大的提高对自动机和其识别语言有了更透彻的理解在动手编程之前 一定要好好明确实验的理论准备和思路的理清，能帮助我们在实验过程中少走 更多的弯路总之在这次实验中收获很多，提高了动手能力和分析问题的能力源代码：源代码： //构造一个DFA #include #include #include #includeusing namespace std;class TransitionTable { public: char present;//当前状态 char next;//下一状态 char input;//输入字符 TransitionTable(char P,char I,char D){ present=P; next=D; input=I; } };class DFA { public: DFA() { cout>select; if(select==1) inti(); if(select==2) read(); } string States;//状态集 char StartStates;//开始状态 string FinalStates; //结束状态集 string Alphabet;//字符集 vector Trans; //转换函数void inti()//初始化自动机 { cout>States; cout>Alphabet; cout>input; if(strcmp(input,“#“)==0) break; TransitionTable Temp(input[0],input[1],input[2]); Trans.push_back(Temp);}cout>StartStates; cout>FinalStates; }void identify()//识别字符串 {cout>str;int i=0; char present=StartStates;while(i>N; example.Traversal(example.StartStates,N); example.write(); system(“pause“); return 0; } /*测试用例 输入状态转换表 0a1 0b2 1b2 2a1 1a3 2b3 3a3 3b3 #0a1 0b2 2a1 1b2 1a3 2b5 3a3 5b5 3b4 5a6 6b4 4a6 6a3 4b5 */。