实验目的:通过本次实验,加深对DFA及其识别的语言的理解,学习对一般的DFA的表达方法与编程实现方法。
实验任务:编写一个C语言程序,模拟实现DFA识别字符串的过程。
实验内容:
内容说明:
实验要求:
判定算法概要:
准备:开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c
c = getchar(); s = 开始状态s0; while ( c != EOF ) // 输入未结束则循环… { s = T(s, c); if (s == NULL) error(); c = getchar(); } if (s 接受状态集F) accept (); else error ();
通用DFA存储格式的建议:
(用以上的第三个测试DFA为例)
3 // 字符集中的字符个数 (以下两行也可合并成一行) / * o // 以空格分隔的字符集。O代表任意非/和*的字符 5 // 状态个数 (以下两行也可合并成一行) 1 2 3 4 5 // 状态编号。若约定总是用从1开始的连续数字表示,则此行可省略 1 // 开始状态的编号。若约定为1,则此行可省略 1 // 结束状态个数。若约定为1,则此行可省略 5 // 结束状态的编号 2 -1 -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态 -1 3 -1 3 4 3 5 4 3 -1 -1 -1
列语言算法概要:
(深度优先搜索,类似于M进制的数的进位问题)
准备:开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, 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的字符串是否属于语言集即可。
提高内容: