实验一 DFA的编程实现

实验一 DFA的编程实现

实验目的：通过本次实验，加深对DFA及其识别的语言的理解，学习对一般的DFA的表达方法与编程实现方法。

实验任务：编写一个C语言程序，模拟实现DFA识别字符串的过程。

实验内容：（1）DFA的输入；（2）DFA的存储与读写；（3）DFA的正确性检查；（4）DFA的语言集列表显示；（5）DFA的规则字符串判定；

内容说明：

（1）DFA的输入：

分别输入DFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容，并保存在设定的变量中。 （2）DFA的存储与读写：

将上述DFA的五元组保存在一个文本文件中，扩展名指定为.dfa。请自行设计DFA文件的存储格式，并说明其含义。能将保存在内存变量中的DFA写入DFA文件，也能将DFA文件读入内存中。（思考：对稀疏DFA（转换表中为空的地方较多）或用“或”表达转换的DFA（如下的测试用例三），如何改进DFA转换表的表达。） （3）DFA的正确性检查：

检查所有集合的元素的唯一性。

检查“开始状态”是否唯一，并是否包含在“状态集”中。 检查“接受状态集”是否为空，并是否包含在“状态集”中。 检查“状态转换表”是否满足DFA的要求。

检查“状态转换表”并非填满时的处理是否得当… （4）DFA的语言集列表显示：

输入待显示的字符串的最大长度N，输出以上定义的DFA的语言集中长度≤N的所有规则字符串。（提示：注意算法中while循环的次数） （5）DFA的规则字符串判定：

输入（或用字符集随机生成）一个字符串，模拟DFA识别字符串的过程判定该字符串是否是规则字符串（属于DFA的语言集）。

测试用例：

DFA（一）

DFA（二）

DFA（三）

实验要求：

按照《编译原理及实践》参考书第二章中描述的“while循环+双层case选择”的算法编程实现一般的DFA。

要求能通过以上三个测试用例的测试。 完成内容中（1）（5）部分，可得C。 完成内容中（1）（2）（5）部分，可得B。 完成内容中（1）（2）（4）（5）部分，可得A。 完成全部内容，可得奖励。

判定算法概要：

准备：开始状态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 ();

列语言算法概要：（深度优先搜索，类似于M进制的数的进位问题）

准备：开始状态s0, 接受状态集F, 状态转换表T(s, c), s?S, c?? 假设：?中的元素个数为M个, 存储于char A[M]中;

准备：长度N>0, 存储语言元素的字符串char L[N] (只存储其编号), 初值全为-1; while ( 1 ) {

for( i=N-1; i>=0; i-- ) if ( L[i] >= 0 )

break; // 找L串中的未用字符

if ( i < N-1 ) // 有未用字符, 用上它, 串长度加1 { L[i+1] = 0; // 用上?中的第1个字符

用判定算法判定字符串A[ L[0] ] ~ A[ L[i+1] ]是否属于语言集中 continue; }

if ( i == N-1 && L[i] < M-1 ) // 无未用部分, 但最后的字符未用完 { L[i]++; // 用上?中的下1个字符

用判定算法判定字符串A[ L[0] ] ~ A[ L[i] ]是否属于语言集中 continue; }

if ( i == N-1 && L[i] == M-1 ) // 无未用部分, 且最后的字符已用完 { for ( ; L[i]==M-1; i-- ) // 搜索前面的字符是否已用完 L[i] = -1; // 改已用完字符为未用字符 if ( i>=0 ) // 找到未用完字符

{ L[i]++; // 用上?中的下1个字符

用判定算法判定字符串A[ L[0] ] ~ A[ L[i] ]是否属于语言集中

continue; }

else // 全部字符都已用完 break; // 算法至此终止 } }

注1：可增加存储前成经过的状态序列，从而无须调用判定算法，直接使用一步状态转换即可。

注2：深度优先搜索无法实现相同长度的字符串显示在一块。若要求如此，需用宽度优先搜索。需定义一个函数用指定字符集生成长度刚好为n的字符串，然后定义主函数，让n从0循环到N，并调用判定算法判定所有长度为n的字符串是否属于语言集即可。

实验报告：

同时上交纸质报告与电子版报告。纸质报告以实验分析、实验中遇到的问题及解决方法、实验测试（含屏幕截图）、实验心得等为主，不得大量引用源程序（引用源程序总行数不得超过100行）。电子版报告以源程序、测试用例、输出文件等为主，包括纸质报告的电子版，须确保提并的源程序能编译运行，否则不要上交。电子版请发送到wenjiabao110@163.com，邮件标题请写明学号、姓名与实验编号，形如：<实验一> <学号> <姓名>。不得抄袭实验报告与源程序，否则后果自负！

本文来源：https://www.bwwdw.com/article/yvz3.html