蒋立源编译原理第三版第三章习题与答案（修改后）

第3章 习题

3-1 试构造一右线性文法，使得它与如下的文法等价

S→AB A→UT U→aU|a D→bT|b B→cB|c

并根据所得的右线性文法，构造出相应的状态转换图。

3-2 对于如题图3-2所示的状态转换图

00D01A0B01C11F0E1题图3-2 (1) 写出相应的右线性文法； (2) 指出它接受的最短输入串；

(3) 任意列出它接受的另外4个输入串； (4) 任意列出它拒绝接受的4个输入串。

3-3 对于如下的状态转换矩阵：

a b a b SA S SA BA A B A B A BB B BB B(ⅰ) 初态:S终态:B(ⅲ) 初态:S终态:Ba b a b SAA B SA SC A A C B B B C B B CCC C CC C(ⅳ) 初态:S终态:C题图3-3

(1) 分别画出相应的状态转换图； (2) 写出相应的3型文法；

(3) 用自然语言描述它们所识别的输入串的特征。

3-4 将如下的NFA确定化和最小化：

(ⅱ) 初态:S终态:A,CaSaAbbBa(1)bSaAaC(2) aaBSaAbBb(3)bBaAaCa, b(4)a题图3-4

3-5 将如题图3-5所示的具有ε动作的NFA确定化。

SaABc(1)bCεεSaZbUabbRaεbXa(2)Y 题图3-5 具有ε动作的NFA

3-6 设有文法G[S]：

S→aA A→aA|bB B→bB|cC|c C→cC|c

试用正规式描述它所产生的语言。

3-7 分别构造与如下正规式相应的NFA。

(1) ((0* |1)(1* 0))* (2) b|a(aa*b)*b

3-8 构造与正规式(a|b)(aa|bb)(a|b)相应的DFA。

*

*

第3章 习题答案

3-1 解：根据文法知其产生的语言是:

L[G]={ambnci| m,n,i≧1}

可以构造与原文法等价的右线性文法:

S→aA A→aA|bB B→bB|cC|c C→cC|c

其状态转换图如下:

3-2 解:

(1) 其对应的右线性文法是G[A]:

A →0D B→0A|1C C→0A|1F|1 D→0B|1C E→0B|1C F→1A|0E|0

(2) 最短输入串为011

(3) 任意接受的四个输入串为：

0110,0011,000011,00110

(4) 任意拒绝接受的输入串为： 0111，1011，1100，1001

3-3 解:

(1) 相应的状态转换图为：