编译原理第3章 习题解答

第3章 习题解答

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

[答案]

先构造NFA

确定化

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

转化成DFA：

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

2.将下图确定化：

[答案]

重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为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不等价，得新分划

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

这是最后分划了

（4）最小DFA：

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

4.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。

[答案]

按题意相应的正规表达式是0*(100*)*0*

构造相应的DFA，首先构造NFA为

用子集法确定化

DFA：

可最小化，终态组为G1={C, D}，非终态组为G2={S, A, B}

对于G2分析：f(S,0)=A, f(A,0)=A, 后继状态均属于G2

而f(B,0)=C, 后继状态属于G1

将G2分割成G21={S，A}， G22={B}

经检查DFA最小状态集有三个，可用S、B、D表示。

或：

按题意相应的正规表达式是0*(0 | 10)*0*

首先构造NFA为

用子集法确定化

DFA：

可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以1,2,4为等价状态，可合并。

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

5．给出下列文法所对应的正规式：

S->0A|1B

A->1S|1

B->0S|0

[答案]

解方程组S的解：

S=0A|1B

A=1S|1

B=0S|0

将A、B产生式的右部代入S中

S=01S|01|10S|10=（01|10）S|（01|10）

所以：S= (01|10)*(01|10)

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

6.为下边所描述的串写正规式，字母表是 {a,b}.

a) 以ab 结尾的所有串

b) 包含偶数个b但不含a的所有串

c) 包含偶数个b且含任意数目a的所有串

d) 只包含一个a的所有串

e) 包含ab子串的所有串

f) 不包含ab子串的所有串

[答案]

注意 正规式不唯一

a) (a|b)*ab

b) (bb)*

c) (a*ba*ba*)*

d) b*ab*

e) (a|b)*ab(a|b)*

f) b*a*

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

7.请描述下面正规式定义的串. 字母表S = {0，1}.

a) 0*(10+)*0*

b) (0|1)*(00|11) (0|1)*

c) 1(0|1)*0

[答案]

a) 每个1至少有一个0跟在后边的串

b) 所有含两个相继的0或两个相继的1的串

c) 必须以 1 开头和0结尾的串

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

8. 构造有穷自动机.

a) 构造一个DFA，接受字母表S = {0, 1}上的以01 结尾的所有串

b) 构造一个DFA，接受字母表S = {0, 1}上的不包含01 子串的所有串.

c) 构造一个NFA，接受字母表S = {x,y}上的正规式x(x|y)*x描述的集合

d) 构造一个NFA，接受字母表S = {a, b}上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA

[答案]

b)

c)

最小化的DFA

9.设有如图所示状态转换图，求其对应的正规表达式。

[答案]

可通过消结法得出正规式

R=(01)*((00|1)(0|1)*|0)

也可通过转换为正则文法，解方程得到正规式。

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

10. 已知正规式：

(1)((a|b)*|aa)*b;

(2)(a|b)*b.

试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。

[分析]

基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA，如这两个最小DFA一样，也就证明了这两个正规式是等价的。

[答案]

状态转换表1

状态转换表2

由于2与3完全一样，将两者合并，即见下表

而对正规式(2)可画NFA图，如图所示。

可化简得下表

得DFA图

两图完全一样，故两个自动机完全一样，所以两个正规文法等价。

对相应正规文法,令A对应1，B对应2

故为：

A->aA|bB|b

B->aA|bB|b

即为S->aS|bS|B,此即为所求正规文法。

本文来源：https://www.2haoxitong.net/k/doc/0f4d634e68eae009581b6bd97f1922791688be1a.html