《形式語言自動(dòng)機(jī)-上下文無關(guān)文法與下推自動(dòng)機(jī).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《形式語言自動(dòng)機(jī)-上下文無關(guān)文法與下推自動(dòng)機(jī).ppt（23頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、1,College of Computer Science （即將棧頂?shù)腁換為） (2) 對(duì)每一 aT, (q, a, a) = (q, ) . （即若棧頂為終結(jié)符，則退棧）,從上下文無關(guān)文法構(gòu)造等價(jià)的下推自動(dòng)機(jī),4,College of Computer Science TT*FF; F( E )a 解：構(gòu)造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, ) 對(duì)所有 b a,+,*,(,) ,
2、例3: 從文法構(gòu)造等價(jià)的下推自動(dòng)機(jī),10,College of Computer Science Sq0,z0,q1 （2）對(duì)式，可構(gòu)造 由（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,練習(xí)：針對(duì)算術(shù)表達(dá)式的PDA反向構(gòu)造其等價(jià)文法,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，上述文法的產(chǎn)生式改寫如下： S A; A 0BD; B 0BC; B 1; C 1; D ;,23,College of Computer Science & Technology, BUPT,作業(yè): Ch4 習(xí)題 20，21，22,
形式語言自動(dòng)機(jī)-上下文無關(guān)文法與下推自動(dòng)機(jī).ppt
