编译原理教程课后习题答案.pdf

百度文库-让每个人平等地提升自我！

第二章词法分析
2.1完成下列选择题：
(1)词法分析器的输出结果是。
a.单词的种别编码b.单词在符号表中的位置
c.单词的种别编码和自身值d.单词自身值
(2)正规式M1和M2等价是指。
a.M1和M2的状态数相等
b.M1和M2的有向边条数相等
c.M1和M2所识别的语言集相等
d.M1和M2状态数和有向边条数相等
(3)DFAM(见图2-1)接受的字集为。
a.以0开头的二进制数组成的集合
b.以0结尾的二进制数组成的集合
c.含奇数个0的二进制数组成的集合
d.含偶数个0的二进制数组成的集合
【解答】
(1)c(2)c(3)d

0

XY1
0

图2-1习题2.1的DFAM
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是一非确定有限自动机。
先画出NFAM相应的状态图，如图2-2所示。
a

a

b
图2-2习题2.3的NFAMXYb
用子集法构造状态转换矩阵，如表2-1所示。b
表2-1状态转换矩阵

III
ab
{x}{x,y}{y}
{y}—{x,y}

1{x,y}{x,y}{x,y}

百度文库-让每个人平等地提升自我！

将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到
M′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。
表2-2状态转换矩阵
f字符
ab
状态
021
1—2
222

将图2-3所示的DFAM′最小化。首先，将M′的状态分成终态组{1,2}与非终态组{0}。其
次，考察{1,2}，由于{1,2}a={1,2}b={2}{1,2}，所以不再将其划分了，也即整个划分只有
两组：{0}和{1,2}。令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最
后，得到如图2-4所示的化简了的DFAM′。
a

02a,b

b
b

1

图2-3习题2.3的DFAM′
a

01a,b
b
图2-4图2-3化简后的DFAM′
2.4正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。
【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如
图2-6所示。
2

ab

a
X1Y
图2-5正规式(ab)*a对应的NFA

2

ba

a
X1Y

图2-6正规式a(ba)*对应的DFA
这两个正规式最终都可得到最简DFA，如图2-7所示。因此，这两个正规式等价。

2
百度文库-让每个人平等地提升自我！

a

01
b图2-7最简NFA

2.5设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}。
(1)给出描述该语言的正规表达式；
(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。
【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA
如图2-8所示。

256

aabbaa

abba
X134Y图2-8习题2-5的NFA
用子集法将图2-8确定化，如图2-9所示。
由图2-9重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)
{0,2}{1}{3,5}{4,6}{7}
按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-10所示。
IIISab
ab
{X}{1}—01—
{1}{2}{3}123
{2}{1}—21—
重新命名
{3}—{4}3—4
{4}{Y}{5}475
{5}—{4}5—4
{Y}{6}—76—
{6}{Y}—67—
图2-9习题2.5的状态转换矩阵
aba

abba
01234

图2-10习题2.5的最简DFA
2.6有语言L={w|w∈(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，
试构造接受该语言的确定有限状态自动机(DFA)。
【解答】对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；
也即在第一个1之前和最后一个1之后，对0的个数没有