编译原理（清华大学第二版）资源-CSDN文库

共15个文件

ppt：15个

3星 · 超过75%的资源需积分: 9 140 浏览量 2008-10-23 22:54:59 上传评论收藏 978KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

package

.rar （15个子文件）

folder

《编译原理》课件（本）

第03章(1).ppt 835KB

第04章(4).ppt 311KB

第03章(2).ppt 1.12MB

第01章.ppt 294KB

第02章(2).ppt 699KB

第04章(3).ppt 388KB

第04章(8).ppt 872KB

第02(1).ppt 289KB

第05章.ppt 866KB

第07章.ppt 646KB

第04章(6).ppt 893KB

第04章(5).ppt 819KB

第04章(1).ppt 418KB

第04章(2).ppt 412KB

第04章(7).ppt 601KB

3.4.5 DFA 的化简

1. DFA 的化简

所谓一个 DFA M 的化简是指寻

找一个状态数比 M 少的 DFA M' ，

使得 L(M)=L(M') 。

(1) 没有多余状态。

化简了的 DFA 满足两个条件 :

(2) 它的状态集中没有两个状态

是

互相等价的。

所谓有穷自动机的多余状态是指

从该自动机的开始状态出发，任何输入

串也不能到达的状态。

3.4.5 DFA 的化简

2. 多余状态

3. 等价状态

设 DFA M ＝ (Q,Σ,f, S

0

, F), s, t∈

Q ，若对任何  

*

, f (s , )∈F 当且

仅当

f (t , )∈F ，则称状态 s 和 t 是等价的。

例如，终态与非终态是可区别的。因

为终态有一条到达自身的 ε 道路，而非

终态没有到达终态的 ε 道路。

3.4.5 DFA 的化简

如果 s 和 t 不等价 , 则称 s 和 t

是可区别的。

5. 化简方法

(1)一致性条件 : 状态 s 和 t 必须同时为

终态或非终态。

4. 两个状态等价的条件 :

(2)蔓延性条件 : 对于所有输入符号 a,

状态 s 和 t 必须转到等价的状态

里。

输入：一个 DFA

M 。

输出：接受与 M 相同语言的 DFA M

' ，

且其状态数最少。

3.4.5 DFA 的化简

无多余状态下把 M 的状态集 Q

分划成一些不相交的子集，使得每个子

集中任何两个状态是等价的，而任何两

个属于不同子集的状态都是可区别的。

化简方法 :

然后在每个子集中任取一个状态作

“代表” , 而删去子集中其余状态 , 并把

射向其余状态的箭弧都改作射向作“代

表”的状态中。

3.4.5 DFA 的化简

内容反馈

warlice

2012-07-28

学C、c++开发的不懂点编译原理，实在制肘。这本书的确是个好东西。
tswwangcc

2017-10-10

只有1-7章的PPT课件，没有pdf课本

puchuanqian

粉丝: 5
资源: 15

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip