又由文法可知iiiei有两棵不同的语法树。 所以该文法是二义性文法。
第三章
练习3.1
1．画出下述文法的状态图 〈Z〉::=〈B〉e 〈B〉::=〈A〉f 〈A〉::= e |〈A〉e
使用该状态图检查下列句子是否是该文法的合法句子 f，eeff，eefe
2、有下列状态图，其中S为初态，Z为终态。 （1） 写出相应的正则文法： （2） 写出该文法的V，Vn和Vt； （3） 该文法确定的语言是什么？ 解：（1） Z→A1|0 A→A0|0 （2） V={A,Z,0,1}
Vn={A,Z} Vt={0,1}
（3） L (G[S])= {0或0n1,n≥1} L (G[S])= {0|00*1} 练习3.2
1．令A，B，C是任意正则表达式，证明 以下关系成立： A|A=A （A*）*= A* A*=ε| AA*
（AB）*A = A（BA）*
（A|B）* =（A*B*）*=（A*|B*） 证明：
⑴A∣A＝｛x∣x∈L(A)或x∈L(A)｝＝｛ x∣x∈L(A)｝＝A
⑵（A*）*＝（A*）0∪（A*）1∪（A*）2∪…∪（＝ε∪(A0∪A 1∪A2∪…∪An) ∪(A1…) ＝ε∪A0∪A 1∪A2∪…∪An ＝A*
⑶ε︱AA*所表示的语言是: {ε}∪LA·LA*
＝LA0∪LA（LA0∪LA1∪LA2∪…）
A*）n ＝LA0∪LA1∪LA2∪…＝LA* 故ε︱AA*＝A* ⑷
(LALB)*LA=({ε}∪L(A)LB∪LALBLALB∪LALBLALBLALB ∪…) LA
=LA∪LALBLA∪LALBLALBLA∪LALBLALBL ALB∪LA…
= LA∪({ε}∪LBLA∪LBLALBLA∪…) = LA(LBLA) ∴(AB)*A=A(BA)*
⑸三个表达式所描述的语言都是LALB中 任意组合
∴（A|B）*=(A*B*)=(A*|B*)* 2. 构造下列正则表达式相应的DFA （1） 1（0|1）*|0
（2） 1（1010*|1（010）*1）*0
4.
5. 构造一DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。