当前位置：文档之家 › 编译原理-NFA转化成DFA

编译原理-NFA转化成DFA

  • 格式：pdf
  • 大小：51.84 KB
  • 文档页数：1

编译原理-NFA转化成DFA

1.假定NFA M= 对M的状态转换图进⾏以下改造:

①引进新的初态结点X和终态结点Y, X,Y∈S, 从X到S0中的任意结点连⼀条ε箭弧，从F中任意结点到Y连⼀条ε箭弧。(解决初态的唯⼀性)

②引⼊新状态对M的状态转换图进⾏进⼀步的替换(简化弧上的标记)

2.NFA确定化：⼦集法(解决弧和转换问题)

设I是S的⼀个⼦集

①J为I中的某个状态经过⼀条a弧⽽到达的集合

②ε-closure(I)：I∪{s'|从s∈I出发经过任意条ε弧能到达s'}

③Ia=ε-closure(J)

例：

I=ε-closure({1})={1,2}

J={5,4,3}

Ia=ε-closure({5,4,3})={5,4,3,6,2,7,8}

3.状态集转换表：

设只含两个字符a,b

①置第⼀⾏第⼀列为ε-closure({X}),求出Ia,Ib

②检查Ia,Ib看其是否已出现在表中的第⼀列，把未曾出现的填⼊后⾯空⾏的第⼀列，再求出Ia,Ib

③重复上述过程，直到所有2,3列⼦集全部出现在第⼀列为⽌

例：

化简和确定化的状态转换图：

合集下载

编译原理第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|ε

编译原理(龙书)答案第三章

编译原理(龙书)答案第三章

3.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9,

3.6.3, 3.6.4, 3.6.5

3.7.1, 3.7.2, 3.7.3

3.8.1, 3.8.2

3.9.3

3.3.2 描述下列正则表达式代表的语言。

a) a(a|b)*a

b) ((ε|a)b*)*

c) (a|b)*a(a|b)(a|b)

d) a*ba*ba*ba*

e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

答案 (a) 由a开头并结尾的由a和b构成的字符串

(b) 由a和b构成的字符串

(c) 倒数第三位为a的由a和b构成的字符串

(d) 仅含3个b的由a和b构成的字符串

(e) 含有偶数个a和偶数个b的由a和b构成的字符串

注意：请准确描述语言的性质而不是列举满足正则表达式的串 3.3.6 写出满足下列定义的字符

a) The first ten letters in either upper or lower case

b) The lowercase consonants

c) The “digits” in a hexadecimal number

d) The characters that can appear at the end of a legitimate English

sentence

答案

(a) a-jA-J

(b) a-j

(c) 0-9a-f

(d) .?!

3.3.7 写出匹配字符串 “\ 的正则表达式

答案：

\”\\

《编译原理》（龙书）第三章答案

3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?

答案：

aabb的所有路径

01223 00111 012000 00000 01222 00011 00123

存在路径1223和0123所以能接受aabb

3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?

编译原理教程课后习题参考答案——

编译原理教程课后习题参考答案——

1 / 7 第二章 词法分析

2.1 完成下列选择题：

(1) 词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置

c. 单词的种别编码和自身值 d. 单词自身值

(2) 正规式M1和M2等价是指 。

a. M1和M2的状态数相等

b. M1和M2的有向边条数相等

c. M1和M2所识别的语言集相等

d. M1和M2状态数和有向边条数相等

(3) DFA M(见图2-1)接受的字集为 。

a. 以0开头的二进制数组成的集合

b. 以0结尾的二进制数组成的集合

c. 含奇数个0的二进制数组成的集合

d. 含偶数个0的二进制数组成的集合

【解答】

(1) c (2) c (3) d

图2-1 习题2.1的DFA M

2.2 什么是扫描器？扫描器的功能是什么？

【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f定义如下：

f(x,a)={x,y} f{x,b}={y}

f(y,a)=Φ f{y,b}={x,y}

试构造相应的确定有限自动机M′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。