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

(iii)以a打头，中间有任意个（包括0）b,再跟a,最后由一个a,b所组成的任意串结尾或者 以b打头，中间有任意个（包括0）a,再跟b,最后由一个a,b所组成的任意串结尾 (iv)以任意个（包括0）b开头,中间跟aa最后由一个a,b所组成的任意串结尾或者

以任意个（包括0）b开头，中间跟ab后再接任意（包括0）a再接b，最后由一个a,b所组成的任意串结尾

10 （1）G1的状态转换图：

G2的状态转换图：

(2) G1等价的左线性文法：

S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→a G2等价的右线性文法：

S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a （3）对G1文法,abb的推导序列是： S=>aA=>abB=>abb

对G1’文法，abb的推导序列是： S=>Bb=>Abb=>abb

对G2文法，aabca的推导序列是： S=>Aa=>Cca=>Babca=>aabca

对G2’文法，aabca的推导序列是： S=>aB=>aabC=>aabcA=>aabca

（4）对串acbd来说，G1,G1’文法都不能产生。 11将右线性文法化为左线性文法的算法：

o （1）对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则若A

不是开始符，B→Aa;

o （2）对于G中每一个形如A→a的产生式,将其变为S→Aa

12 (1)

状态矩阵是：

记[S]=q0 [B]=q1 [A B]=q2 [S A]=q3 ,最小化和确定化后如图

（2）记 [S]=q0, [A]=q1,[B S]=q2 最小化和确定化后的状态转换图如下

13 （1）将具有ε动作的NFA确定化后，其状态转换图如图： 记 { S0,S1,S3}=q0 {S1}=q1 {S2 S3}=q2 {S3}=q3

(2) 记{S}=q0 {Z}=q1 {U R}=q2 {S X}=q3 {Y U R}=q4 {X S U}=q5 {Y U R Z}=q6 {Z S}=q7

14（1）从略

(2)化简后S0和S1作为一个状态，S5和S6作为一个状态。 状态转换图如图

15从略。 16从略。

?

(1) r*表示的正规式集是{ε,r,rr,rrr,…}

(ε|r)*表示的正规式集是{ε, εε,?}∪{r,rr,rrr,?}={ε,r,rr,rrr,?} ε|rr*表示的正规式集是{ε,r,rr,rrr,?}