编译答案陈意云高等教育原理

课后答案网，用心为你服务！ 

 大学答案 ---中学答案 ---考研答案 ---考试答案 最全最多的课后习题参考答案，尽在课后答案网()! Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 爱校园()课后答案网()淘答案() 

编译答案陈意云高等教育原理

编译原理习题课(1)

ww

w.

kh

栾俊 luanj@ 3/26/2010

da w.案

课后答

网

co m

编译答案陈意云高等教育原理

2.3课后答案网

ww2010-3-26

w.

0(0|1)*0 ((ε|0)1*)* (0|1)*0(0|1)(0|1) 0*10*10*10* (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

kh

da w.

叙述由下列正规式描述的语言

luanj@

co m2

编译答案陈意云高等教育原理

2.3 (续)课后答案网

ww2010-3-26

0(0|1)*0以0开头和结尾的长度至少是2的01串 ((ε|0)1*)*所有的01串 (0|1)*0(0|1)(0|1)倒数第三位是0的01串 0*10*10*10*含有3个1的01串 (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*含有偶数个0和偶数个1的01串(习题集P1/1.1)

w.

kh

da w.

一种表述(这里说的01串包括ε)

luanj@

co m3

编译答案陈意云高等教育原理

2.4课后答案网 为下列语言写正规定义

ww2010-3-26

包含5个元音的所有字母串，其中每个元音只出现一次且按序排列 按词典序排列的所有字母串 C语言的注释 相邻数字都不相同的所有数字串 最多只有一处相邻数字相同的所有数字串 由偶数个0和偶数个1组成的所有01串 由偶数个0和奇数个1组成的所有01串 不含字串011的01串

w.

kh

da w.

luanj@

co m4

编译答案陈意云高等教育原理

2.4 (续)课后答案网 一种答案

包含5个元音的所有字母串，其中每个元音只出现一次且按序排列 5个元音a, e, i, o, u 不含5个元音的任意字符：[B-DF-HJ-NP-TV-Zb-df-hj-np-tvz],记为α α*(a|A)α*(e|E)α*(i|I)α*(o|O)α*(u|U)α*

按词典序排列的所有字母串 A*a*B*b*…Z*z*

ww2010-3-26

w.

C语言的注释

不含/,*的任意字符记为α 不含*/的任意字符串: (**α+/*)* /*(**α+/*)**/luanj@ 5

kh

da w.

co m

编译答案陈意云高等教育原理

2.4 (续)课后答案网 一种答案(续)

相邻数字都不相同的所有数字串 123031357106678035 123 0 313571 0 6678 0 35 3 1 357 1 答案见习题集P2/1.3

ww2010-3-26

w.luanj@

kh

da w.

co m6

编译答案陈意云高等教育原理

2.4 (续)课后答案网 一种答案(续)

最多只有一处相邻数字相同的所有数字串 与上题类似 1230313571006678035 123 0 313571 00 6678 0 35 3 1 357 1 answer->double_0|double_1|…|double_9其中double_i表示相邻的数字是i double_0 -> 0?(no_00)*no_000(no_00)*no_0?|00 no_0 ->……

ww2010-3-26

w.

kh

da w.

luanj@

co m7

编译答案陈意云高等教育原理

2.4 (续)课后答

案网 一种答案(续)

最多只有一处相邻数字相同的所有数字串(续) double_i -> i?(no_ii)*no_iii(no_ii)*no_i?|ii no_i -> (0|no_0_i0)(no_0_i0)*(no_0_i?)|no_0_i no_0_i ->…… no_0-(i-2)_i ->… no_0-(i+1) ->…… 比如i=5 double_5 -> 5?(no_55)*no_555(no_55)*no_5?|55 no_5 -> 0|no_0_50)(no_0_50)*(no_0_5?)|no_0_5 no_0_5-> 1|no_0-1_51)(no_0-1_51)*(no_0-1_5?)|no_0-1_5 no_0-1_5->2|no_0-2_52)(no_0-2_52)*(no_0-2_5?)|no_0-2_5 no_0-2_5->3|no_0-3_53)(no_0-3_53)*(no_0-3_5?)|no_0-3_5 no_0-3_5->4|no_0-54)(no_0-54)*(no_0-5?)|no_0-5 no_0-5->……

ww2010-3-26

w.

kh

da w.

luanj@

co m8

编译答案陈意云高等教育原理

2.4 (续)课后答案网 一种答案(续)

由偶数个0和偶数个1组成的所有01串 习题集P2/1.2 习题集P2/1.2

由偶数个0和奇数个1组成的所有01串

ww2010-3-26

w.luanj@

kh

da w.

co m9

编译答案陈意云高等教育原理

2.4 (续)课后答 不含字串011的01串

当出现0后，1只能单独出现 1*(0+1)*0*

ww2010-3-26

w.luanj@

kh

da w.案10

网

一种答案(续)

co m

编译答案陈意云高等教育原理

2.7课后答案网

ww2010-3-26

w.

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

khluanj@

da w.

用算法2.4为下列正规式构造NFA,并给出处理ababbab的状态转换序列

co m

11

编译答案陈意云高等教育原理

2.7 (续)案网 ((ε|a)b*)*εε

da w.ε 0 2 a 1 3εεε 5ε

课后答

co mε 6 bε 7ε 8ε fε12

start

s

ε 4

ww2010-3-26

ababbab:s->4->0->1->5->6->7->8->4->0>1->5->6->7->6->7->8-> 4->0->1->5->6>7->8->f

w.

kh

luanj@

编译答案陈意云高等教育原理

2.11课后答案网

ww2010-3-26

w.luanj@

kh

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

da w.

可以通过正规式的最简DFA同构来证明正规式等价。证明下列正规式等价

co m

13

编译答案陈意云高等教育原理

2.11 (续)课后答案网a A b

w. ww2010-3-26

khstart

2)ε-closure(move(A,a))=ε-closure({1})={1,5,6,8,4,f,0,2,3}= B 3)ε-closure(move(A,b))=ε-closure({7})={7,6,8,4,f,0,2,3,5}= C 4)ε-closure(move(B,a))=ε-closure({1})= B 5)ε-closure(move(B,b))=ε-closure({7})= C 6)ε-closure(move(C,a))=ε-closure({1})= B 7)ε-closure(move(C,b))=ε-closure({7})= C B b a C b a

da w.

NFA->DFA{s,4,f,0,2,3,5,6,8}= A 1)ε-closure({s})=

luanj@

co m14

编译答案陈意云高等教育原理

2.11 (续)课后答案网 DFA->最简DFA

w. ww2010-3-26

kh

1)划分为接受状态集合F={A,B,C}和非接受状态SF={} 2)由于S-F为空集，只考虑F:对于A,输入a,转换为B,输入b,转换为C对于B,输入a,转换为B,输入b,转换为C对于C,输入a,转换为B,输入b,转换为C因此F不需进一步划分 a start s b

da w.

luanj@ b

co m15

编译答案陈意云高等教育原理

2.13课后答案网

习题集P3/1.4

ww2010-3-26

w.luanj@

kh

da w.

构造表示0,1个数都是偶数的01字符串的 DFA

co m

16

编译答案陈意云高等教育原理

2.14课后答 习题集P4/1.5

ww2010-3-26

w.luanj@

kh

da w.案17

网

能被5整除的二进制数

co m

编译答案陈意云高等教育原理

ww w. kh课后答案

da w.谢谢！!

网

co m