评语： 课程设计成绩
考 勤
软 件
报 告
答 辩
总 成 绩
教师签名：
《编译原理》课程设计报告
自动机的确定化和最小化
学院（系）： 计算机科学与技术学院
班 级： 0404101
学生姓名： 李善超 学号 18
指导教师： 张华
时间： 从 07 年 3 月 5 日 到 07 年 3 月 16 日
目录
1．课程设计的目的.................................................2
2．课程设计内容及要求...........................................2
3．实现原理...........................................................2
3.1．NFA 的确定化有两种方式：......................................................................................2
3.2．DFA 的最小化：..........................................................................................................4
4．算法实现流程图.................................................4
4.1．程序主要功能：..........................................................................................................4
4.2．程序的流程图：..........................................................................................................5
4.3.重要函数的功能.............................................................................................................6
5．测试数据...........................................................6
6．结果输出及分析.................................................7
6.1．运行时界面：..............................................................................................................7
6.2．输入 NFA 的结果：.....................................................................................................9
6.3．输入 DFA 的结果：...................................................................................................10
7．软件运行环境及限制.........................................10
7.1．软件编译环境............................................................................................................10
7.2．软件运行环境.............................................................................................................11
8．心得体会.........................................................11
9．参考文献.........................................................11
1
1．课程设计的目的
通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译
原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设
计风格。同时通过某种可视化编程语言的应用，具备初步的 Windows 环境下
的编程思想。
2．课程设计内容及要求
1. 可以使用任何语言来完成，例如：Java、C++。
2. 文法中的空字符串统一使用@表示。
3. 以文件方式读取自动机。
4. 判断读取的自动机是确定的还是不确定的自动机。
5. 若是不确定的自动机，将自动机确定化。
6. 将确定化后的自动机最小化。
3．实现原理
程序可以以文件方式读取文法或自动机。
3.1．NFA 的确定化有两种方式：
一．子集法
1．先把 DFA M’中的 Q’和 F’置为空集；
2．M’的开始状态 q0’=[q0]，把[q0]置为未标记后加入到 Q’中；
3 ． 如 果 Q’ 中 存 在 未 标 记 的 状 态 [q1,q2,… ， qi] ， 则 对 每 个 a∈∑ 定 义 ：
δ’([q1,q2,…，qi],a)=[p1,p2,…,pi]当且仅当 δ({q1,q2,…，qi},a)={p1,p2,
…,pi}。如果[q1,q2,…，qi]不在 Q’中，则把它置为为标记后加入到 Q’中；如
果 p1,p2,…,pi 中至少有一个是 M 的终态，则同时把[p1,p2,…,pi]加入到 F’
中；然后给 Q’中所有的状态都标记为止；
4．重复执行（3），直到不能向 Q’中加入新状态，并且 Q’中所有的状态都
有标记为止；
2
5．重新命名 Q’中的状态，最后获得等价的 DFA M’。
二．对含 ε 变迁的 NFA 的确定化：
1．置 Q
’
, F
’
为空集；
2．令 q
0
’
=[ε_CLOSURE({q
0
})],并把[q
0
]置为未标记后加入到 Q
’
中；
3．如果 Q
’
中存在未标记状态[q
1
,q
2
,…,q
i
],则对每个 a∈∑定义：d
‘
([q
1
,q
2
,…
q
i
],a)=[p
1
,p
2
,…,p
j
] 当 且 仅 当 d({q
1
,q
2
,…q
i
},a)={r
1
,r
2
,…,r
k
},
ε_CLOSURE({r
1
,r
2
,…,r
k
})= {p
1
,p
2
,…,p
j
}。如果[p
1
,p
2
,…,p
j
]不在 Q
’
中，则把
它置为未标记后加入到 Q
’
中；如果 p
1
,p
2
,…,p
j
中至少有一个是 M 的终态，
则同时把[p
1
,p
2
,…,p
j
]加入到 F
’
中；然后给 Q
’
中的状态[q
1
,q
2
,…,q
i
]加上标记；
4．重复执行 3，直到不能向 Q
’
中加入新状态，并且 Q
’
中所有的状态都有标
记为止；
5．重新命名 Q
’
中的状态，然后获得等价的 DFA M
’
3
q1,qf
q
1
q2
Q2
q2
q
q
2
0 1
0
1
