《形式語言自動機-上下文無關文法與下推自動機.ppt》由會員分享，可在線閱讀，更多相關《形式語言自動機-上下文無關文法與下推自動機.ppt（23頁珍藏版）》請在裝配圖網上搜索。
1、1,College of Computer Science （即將棧頂?shù)腁換為） (2) 對每一 aT, (q, a, a) = (q, ) . （即若棧頂為終結符，則退棧）,從上下文無關文法構造等價的下推自動機,4,College of Computer Science TT*FF; 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,+,*,(,) ,
2、例3: 從文法構造等價的下推自動機,10,College of Computer Science Sq0,z0,q1 （2）對式，可構造 由（q0,b,A）=( q1,) 得 q0,A,q1b 由（q1,b,A）=( q1,) 得q1,A,q1b 由（q1,,A）=( q1,)得 q1,A,q1 由（q1,,z0）=( q1,)得 q1,z0,q1,16,College of Computer Science TT*FF; F( E )a,練習：針對算術表達式的PDA反向構造其等價文法,21,College of Computer Science S q0 , Z0 , q1 ;
3、 S q0 , Z0 , q2 ;,(5)由(q0,XZ0)(q0, 0, Z0) 得 q0Z0qj 0q0Xqi qiZ0qj , i, j = 0,1,2;,(6)由(q0,XX)(q0, 0, X) 得 q0Xqj 0q0Xqi 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,College of Computer Science q0Z0q2 0q0Xq1 q1Z0q2 q0Xq1 0q0Xq1 q1Xq1 q0Xq1 1; q1Xq1 1; q1Z0q2 ;,為簡潔，記 q0Z0q2 為A，q0Xq1 為B， q1Xq1 為C， q1Z0q2 為D，上述文法的產生式改寫如下： S A; A 0BD; B 0BC; B 1; C 1; D ;,23,College of Computer Science & Technology, BUPT,作業(yè): Ch4 習題 20，21，22,
形式語言自動機-上下文無關文法與下推自動機.ppt
