《形式語言自動機-上下文無關文法與下推自動機.ppt》由會員分享，可在線閱讀，更多相關《形式語言自動機-上下文無關文法與下推自動機.ppt（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1,CollegeofComputerScience（即將棧頂?shù)腁換為β）(2)對每一a?T,?(q,a,a)={(q,?)}.（即若棧頂為終結符，則退棧）,從上下文無關文法構造等價的下推自動機,4,CollegeofComputerScienceT→T*F∣F;F→(E)∣a解：構造M＝（{q}，T，Γ，δ，q，E，φ）δ定義為：①δ(q,ε,E)＝{(q,E+T),(q,T)}②δ(q,ε,T)＝{(q,T*F),(q,F)}③δ(q,ε,F)＝{(q,(E)),(q,a)}④δ(q,b,b)＝{(q,ε)}對所有b∈{a,+,*,(,)},例3:從文法構造等價的下推自動機,10,CollegeofComputerScienceS→[q0,z0,q1]（2）對③④⑤⑥式，可構造由δ（q0,b,A）={(q1,ε)}得[q0,A,q1]→b由δ（q1,b,A）={(q1,ε)}得[q1,A,q1]→b由δ（q1,ε,A）={(q1,ε)}得[q1,A,q1]→ε由δ（q1,ε,z0）={(q1,ε)}得[q1,z0,q1]→ε,16,CollegeofComputerScienceT→T*F∣F;F→(E)∣a,練習：針對算術表達式的PDA反向構造其等價文法,21,CollegeofComputerScienceS?[q0,Z0,q1];S?[q0,Z0,q2];,(5)由(q0,XZ0)??(q0,0,Z0)得[q0Z0qj]?0[q0Xqi][qiZ0qj],i,j=0,1,2;,(6)由(q0,XX)??(q0,0,X)得[q0Xqj]?0[q0Xqi][qiXqj],i,j=0,1,2;,(2)由(q1,?)??(q0,1,X)得[q0Xq1]?1;,(3)由(q1,?)??(q1,1,X)得[q1Xq1]?1;,(4)由(q2,?)??(q1,?,Z0)得[q1Z0q2]??;,22,CollegeofComputerScience[q0Z0q2]?0[q0Xq1][q1Z0q2][q0Xq1]?0[q0Xq1][q1Xq1][q0Xq1]?1;[q1Xq1]?1;[q1Z0q2]??;,為簡潔，記[q0Z0q2]為A，[q0Xq1]為B，[q1Xq1]為C，[q1Z0q2]為D，上述文法的產(chǎn)生式改寫如下：S?A;A?0BD;B?0BC;B?1;C?1;D??;,23,CollegeofComputerScience&Technology,BUPT,作業(yè):Ch4習題20，21，22,