哈工大编译原理习题及答案

第三章 习题解答

1．从略 2．

3 假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河

用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸 4:狐狸和山羊在右岸5:狐狸和白菜在右岸 6:山羊和白菜在右岸F:全在右岸

4 证明：只须证明文法G:A→αB 或A→α （A,B∈VN, α∈VT+） 等价于G1:A→aB 或A→a (a∈VT+)

?

G1的产生式中 A→aB, 则B也有B→bC ,C→cD ….

所以有 A →abc?B’,a,b,c?∈VT,B’∈VN

所以与G等价。

2）G的产生式A→αB，α∈VT+，因为α是字符串，所以肯定存在着一个终结符a， 使A→aB 可见两者等价，所以由此文法产生的语言是正规语言。 5

6 根据文法知其产生的语言是 L={ambnci| m,n,i≧1}

可以构造如下的文法VN={S,A,B,C}, VT={a,b,c}

P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:

7 (1) 其对应的右线性文法是:

A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B (2) 最短输入串011 (3) 任意接受的四个串 011,0110,0011,000011 (4) 任意以1打头的串. 8 从略。 9

（2）相应的3型文法

(i) S →aAS→bS A→aA A→bB B→a|aB B→b|bB (ii) S→aA|a S→bB B→aB | bB A→aB A→b|bA

(iii) S→aA S→bB A→bA A→aC B→aB B→bC C→a|aC C→b|bC (iv) S→bS S→aA A→aC A→bB B→aB B→bC C→a|aC C→b|bC （3）用自然语言描述输入串的特征

(i) 以任意个(包括0)b开头，中间有任意个（大于1）a，跟一个b,还可以有一个由a,b组成的任意字符串

(ii) 以a打头，后跟任意个（包括0）b