发布时间 : 星期二 文章哈工大编译原理习题及答案更新完毕开始阅读68851b05bed5b9f3f90f1ca1
(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,?}