编译原理课后习题答案+清华大学出版社第二版

《编译原理》课后习题答案第四章

已知正规式： (1)((a|b)*|aa)*b; (2)(a|b)*b.

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

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

状态转换表 1

a b X124 1234 124Y 1234 1234 124Y 124Y 1234 124Y

状态转换表 2

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

盛威网（www.snwei.com）专业的计算机学习网站

22

《编译原理》课后习题答案第四章

2 3

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

a b X12 12 12Y 12 12 12Y 12Y 12 12Y 可化简得下表

a b 1 2 3 2 2 3 得 DFA 图

两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令 A 对应 1，B 对应 2 故为： A→aA|bB|b

B→aA|bB|b 即为 S→aS|bS|B,此即为所求正规文法。

问题 6：考虑正规表达式 r = a*b(a | b) ，构造可以生成语言 L(r) 的一个正规文法。 答案：

盛威网（www.snwei.com）专业的计算机学习网站

23

《编译原理》课后习题答案第四章

S → a*b(a | b) 变换为 S → aA, S → b(a | b) , A → aA , A → b(a | b) 变换为 S → aA, S → bB, B → (a | b) , A → aA , A → bC, C → (a | b) 变换为 S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b

所以，一个可能的正规文法为 G[S]：

S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b 或表示为：

S → aA | bB, B → a | b , A → aA | bC, C → a | b

（适当等价变换也可以，但要作说明，即要有步骤）

问题 7：

考虑下图所示的 NFA N，构造可以生成语言 L(N) 的一个正规文法。

答案： G[P]:

P → 0 P ?1 P ?1 Q

盛威网（www.snwei.com）专业的计算机学习网站

24

《编译原理》课后习题答案第四章

Q → 0 R ?1 R R → ε

问题 8：考虑如下文法 G[S]：

S → 0S?1S?1A A→ 0B?1B B → ε

a) 试构造语言为 L(G) 的一个正规表达式。 b) 试构造语言为 L(G) 的一个有限自动机。 答案：

由 A→ 0B ， B → ε 得 A→ 0 ; 由 A→ 1B ， B → ε 得 A→ 1 ; 由 A→ 0，A→ 1 得 A→ 0 ?1 ; 由 S→ 1A，A→ 0 ?1 得 S→ 1( 0 ?1 ) ; 由 S→ 1A，A→ 0 ?1 得 S→ 1( 0 ?1 ) ; 由 S→ 0S，S→ 1( 0 ?1 ) 得 S→ 0*1( 0 ?1 ) ; 由 S→ 1S，S→ 1( 0 ?1 ) 得 S→ 1*1( 0 ?1 ) ; 由 S→ 0*1( 0 ?1 )，S→ 1*1( 0 ?1 ) 得 S→ 0*1( 0 ?1 ) ? 1*1( 0 ?1 ) ; 所以，一个可能的正规表达式为：

0*1( 0 ?1 ) ? 1*1( 0 ?1 )

b)

盛威网（www.snwei.com）专业的计算机学习网站

25

a)

《编译原理》课后习题答案第四章

盛威网（www.snwei.com）专业的计算机学习网站26