当前位置：文档之家 › 编译原理中DFA最小化

编译原理中DFA最小化

  • 格式：pdf
  • 大小：79.36 KB
  • 文档页数：2

编译原理中DFA最⼩化

这⾥只是记录⼀下个⼈的理解，以备复习使⽤

DFA最⼩化的操作步骤：

1.将DFA未最⼩化前的状态划分为：终态和⾮终态

终态就是包含了NFA终点结点的状态集合，如下图的NFA，状态10为NFA的终点，所以在DFA的状态集合中，包含了10这个状态的集合就是DFA的终态，那么，不包含的就是⾮终态

了

值得⼀提的是，在DFA划分⾮终态和终态时，有可能得到的⾮终态是空集（仔细想想，此时

意味着所有的DFA的状态集合都包含了NFA的终点（如下图的10）），反之，终态不可能为

空集，因为NFA的终点⼀定会包含在某个DFA的状态集合中。

得到的DFA图如下：（双重圈表⽰终态，单层表⽰⾮终态，对照上⾯所说的，是不是包含了10的都是被归类为终态集合？）

但是，上⾯划分的终态和⾮终态只是⼀个初步的划分，可能在终态（或者⾮终态）集合内还

可以继续划分出多个状态集合

⾸先看定义：

在DFA中，两个状态等价的条件是：

⼀致性条件：状态s和t必须同时为终态或者⾮终态 （什么意思？就是意味着终态和⾮终态⾥

的状态集合不可能再被划分为相同的状态了，所以第⼀步划分终态和⾮终态可以理解为粗略

的划分）

蔓延性条件：对于所有输⼊符号，状态s和状态t必须转换到等价的状态⾥ 。（这该怎么理解

呢？请看第⼆个表）

⽐如我想知道第⼆个表中的状态集合[2,3,4,5,7,10]和状态集合[6,9,4,7,10,5] (也即是第⼆第三

⾏的初始状态集合）是不是属于同⼀个状态，这个蔓延性条件就是说[2,3,4,5,7,10]经过letter

和digit转换得到的[6,9,4,7,10,5] 和 [8,9,4,7,5,10] 与 [6,9,4,7,10,5]经过letter和digit转换得到的[6,9,4,7,10,5] 和 [8,9,4,7,5,10] 是不是同属于同⼀个状态。（此时可以看出它们都属于终

态）。

emmm，感觉我⾃⼰表述不清，⾃⼰多看书和上⾯给出的那个连接，应该不难理解的。

接下来说⼀下我⾃⼰划分状态集合的操作。

⾸先划分成终态和⾮终态，然后继续在终态和⾮终态的内部看每个状态之间是否属于同⼀个

状态………………还是以此图为例：

在图中可以看出终态集合为list = [ [2,3,4,5,7,10],[4,5,6,7,9,10],[4,5,7,8,9,10]] ⼀共三个集合，

要继续看这三个集合是否可以进⼀步细划

我的想法是递归操作，⾸先将上⾯的状态集合的第⼀个⼦集取出来，并找出其相应的状态

（放⼊⼀个state1的List中），接着遍历其他的⼦集，看是否和state1中的集合的状态相同，

是的话就放进state1这个List中，不是的话就放进state2这个状态集合中。最后遍历结束的结

果是将[ [2,3,4,5,7,10],[4,5,6,7,9,10],[4,5,7,8,9,10]]这个集合划分成两类，第⼀类state1是与第

⼀个集合list[0] 状态相同的 ，第⼆类state2是与第⼀个集合list[0] 状态相不同的。

接下来，可以判断state2是不是空，如果是空的话，就意味着list中的所有⼦集的状态都是相

同的，即state1，如果state2长度为1，也不⽤继续判断了，直接将list划分为state1和state2两

类了。

如果，state2的长度⼤于1，那么就得继续对state2进⾏划分，操作步骤和上⾯划分list的⼀

致，因此可以使⽤递归操作。

对于⾮终态，如果需要划分，操作和上⾯的⼀样，最后递归划分结束后，得到的是dfa所有的

状态。

当然，这只是初步的想法，不知道可不可以，我觉上述想法的难点可能在，当状态划分越来

越多的时候，判断两个状态是否属于同⼀个状态的⼯作可能会越来越⿇烦？

合集下载

编译原理第4章答案

编译原理第4章答案

第四章 词法分析

1．构造下列正规式相应的 DFA：

(1) 1(0|1) * 101

(2) 1(1010* | 1(010) * 1)* 0

(3) a((a|b) * |ab * a)* b

(4) b((ab)* | bb) * ab 解：

(1)1(0|1) * 101 对应的 NFA为

0

1 1 0 1

0 1 2 3 4

1

下表由子集法将 NFA 转换为 DFA：

I I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1))

A[0] B[1]

B[1] B[1] C[1,2]

C[1,2] D[1,3] C[1,2]

D[1,3] B[1] E[1,4]

E[1,4] B[1] B[1]

0 0

1 1 0 1

A B C D E

1

1

0,1

(2)1(1010 * | 1(010) * 1)* 0 对应的 NFA 为

ε

ε

1 1 0 1 0 1 0

0 1 2 3 4 5 6 1

0

1 ε ε

0

0 1

9

7 8

ε

下表由子集法将 NFA 转换为 DFA：

I I

= ε-closure(MoveTo(I,0)) I

1 = ε-closure(MoveTo(I,1)) 0

A[0] B[1,6]

B[1,6] C[10] D[2,5,7]

C[10]

D[2,5,7] E[3,8] B[1,6]

E[3,8] F[1,4,6,9]

F[1,4,6,9] G[1,2,5,6,9,10] D[2,5,7]

G[1,2,5,6,9,10] H[1,3,6,9,10] I[1,2,5,6,7]

H[1,3,6,9,10] J[1,6,9,10] K[2,4,5,7]

编译原理第3章 习题解答

编译原理第3章 习题解答

第3章 习题解答

1.构造正规式1(0|1)*101相应的DFA.

[答案]

先构造NFA

确定化 0 1

X A

A A AB

AB AC AB

AC A ABY

ABY AC AB

重新命名，令AB为B、AC为C、ABY为D

0 1

X A

A A B

B C B

C A D

D C B

转化成DFA：

==============================================================

2.将下图确定化：

[答案] 0 1

S VQ QU

VQ VZ QU

QU V QUZ

VZ Z Z

V Z

QUZ VZ QUZ

Z Z Z

重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。

0 1

S A B

A C B

B D E

C F F

D F

E C E

F F F

转化为DFA：

================================================================

3.把下图最小化：

[答案]

（1）初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组进行审查： {1,2,3,4,5}a {0,1,3,5}

而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}

∵{4} a {0}，所以得新分划

（2）Π1：{0}，{4}，{1,2,3,5}

对{1,2,3,5}进行审查：

∵{1,5} b {4}

{2,3} b {1,2,3,5}，故得新分划

（3）Π2：{0}，{4}，{1, 5}，{2,3}

{1, 5} a {1, 5}

{2,3} a {1,3}，故状态2和状态3不等价，得新分划

编译原理三、四章答案(清华版)

编译原理三、四章答案(清华版)

第三章 习题解答

6．每个表达式的推导及语法树分别如下：

(1)

=>

=>

=> i

(2)

=>

=>

=>()

=>()

=>()

=>(i)

(3)

=>

=>*

=>*

=>i*

=>i*i

(4)

=> +

=> +

=> *+

=> *+

=> i*+

=> i*i+

=> i*i+

=> i*i+i

(5)

=> +

=> +

=> +

=> i+

=> i+

=>i+

=>i+(+)

=> i+(+) => i+(+)

=> i+(i+)

=> i+(i+)

=>i+(i+i)

(6)

=> +

=> +

=> +

=> i+

=> i+*

=> i+*

=> i+i*

=> i+i*i

i()i*ii图（1）图（2）图（3） ()+*iii+i+ii图（4）图（5）

+i图（6）*ii

11．根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：

E => E+T => E+T*F ，所以E+T*F是该文法的一个句型。由右图的语法树也可以看出，E+T*F是该文法的一个句型。

这个句型的所有短语为：E+T*F, T*F

直接短语为：T*F

句柄为：T*F

13． EE + TT * F(1)最左推导：S=>ABS

=>a1BS

=> a1SBBS

=> a1BBS

=> a1b1BS

=> a1b1b2S

=> a1b1b2Aa3

=> a1b1b2a2a3

最右推导：S=>ABS

=> ABAa3

=> ABa2a3

=> ASBBa2a3

=> ASBb2a2a3

=> ASb1b2a2a3

=> Ab1b2a2a3

=> a1b1b2a2a3

(2)该文法产生式集合P可能有如下规则：S→ABS|Aa|ε

编译实验三NFA转换成DFA和DFA化简

编译实验三NFA转换成DFA和DFA化简

1 / 20

实验三（一）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 // 以空格分隔的字符集。 2 / 20 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中的各种信息。根据子集构造法，构造相应的函数。