编译实验三(NFA转换成DFA和DFA化简)要点

实验三(一)NFA?DFA(2小时)

一. 问题描述

NFA?DFA。

1. 实验目的:学会编程实现子集构造法。

2. 实验任务:存储NFA与DFA,编程实现子集构造法将NFA转换成DFA。

3. 实验内容:(1)确定NFA与DFA的存储格式,为3个以上测试NFA准备好存储

文件。(2)用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。(3)经测试无误。测试不易。可求出NFA与DFA的语言集合的某个子集(如长度小于某个N),再证实两个语言集合完全相同!(4)测试用例参考:将下列语言用RE表示,再转换成NFA使用:

(a) 以a开头和结尾的小字字母串;a (a|b|…|z)*a | a

(b) 不包含三个连续的b的,由字母a与b组成的字符串;(? | b | bb) (a | ab | abb)* (c) (aa|b)*(a|bb)*

二.算法描述

1. NFA的输入:

分别输入NFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容,并保存在设定的变量中。

2. NFA的存储与读写:

将上述NFA的五元组保存在一个文本文件中。存储格式如下所示(以下图中NFA为例):

2 // 字符集中的字符个数 (以下两行也可合并成一行) a b // 以空格分隔的字符集。

4 // 状态个数 (以下两行也可合并成一行)

1 2 3 4 // 状态编号。若约定总是用从1开始的连续数字表示,则此行可省略 1 // 开始状态的编号。若约定为1,则此行可省略 1 // 结束状态个数。若约定为1,则此行可省略 3 // 结束状态的编号

3 2 1 // 状态1的所有出去的转换。按字符集中的字符顺序给出,并在最左边加上一列关于?的转换。-1表示出错状态。多个状态用逗号分隔。

-1 1 -1 -1 3 4 -1 -1 3

3. 基本算法描述

存储格式如上所示,程序开始时,从文件中读取数据以获得NFA中的各种信息。根据子集构造法,构造相应的函数。

子集构造法伪代码如下:

初始时, ε-closure(S0) 是 Dstates 中唯一的状态且未被标记; while Dstates 中存在一个未标记的状态T do begin 标记T;

for 每个输入符号 a do begin U := ε-closure ( move (T, a) ); if U 没在Dstates中 then

将U作为一个未被标记的状态添加到 Dstates. Dtran [ T, a ] := U end end

ε-closure 的计算

将T中所有状态压入栈stack; 将ε-closure (T) 初始化为T; while stack不空 do begin 将栈顶元素t弹出栈;

for 每个这样的状态u:从t到u有一条标记为 ε的边do if u 不在ε-closure ( T )中 do begin 将u 添加到ε-closure ( T ); 将u压入栈stack中 end end

子集构造法的流程图:

实验三(二)DFA化简(2小时)

一. 问题描述

DFA化简

1.实验目的:学会编程实现等价划分法化简DFA。

2.实验任务:先完善DFA,再化简DFA。

3.实验内容:

(1)准备3个以上测试DFA文件。 (2)DFA手动完善。(状态转换映射要是满映射)

(3)用C或JAVA语言编写用等价划分法化简DFA的程序。

(4)经测试无误。测试不易。可求出两个DFA的语言集合的某个子集(如长度小于某个N),再证实两个语言集合完全相同!

(5)编写实验报告。要求同实验一,不再详述。

二.算法描述

1. DFA的化简

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4