形式语言自动机-上下文无关文法与下推自动机.ppt
《形式语言自动机-上下文无关文法与下推自动机.ppt》由会员分享,可在线阅读,更多相关《形式语言自动机-上下文无关文法与下推自动机.ppt(23页珍藏版)》请在装配图网上搜索。
1,CollegeofComputerScience(即将栈顶的A换为)(2)对每一aT,(q,a,a)=(q,).(即若栈顶为终结符,则退栈),从上下文无关文法构造等价的下推自动机,4,CollegeofComputerScienceTT*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,)对所有ba,+,*,(,),例3:从文法构造等价的下推自动机,10,CollegeofComputerScienceSq0,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,CollegeofComputerScienceTT*FF;F(E)a,练习:针对算术表达式的PDA反向构造其等价文法,21,CollegeofComputerScienceSq0,Z0,q1;Sq0,Z0,q2;,(5)由(q0,XZ0)(q0,0,Z0)得q0Z0qj0q0XqiqiZ0qj,i,j=0,1,2;,(6)由(q0,XX)(q0,0,X)得q0Xqj0q0XqiqiXqj,i,j=0,1,2;,(2)由(q1,)(q0,1,X)得q0Xq11;,(3)由(q1,)(q1,1,X)得q1Xq11;,(4)由(q2,)(q1,Z0)得q1Z0q2;,22,CollegeofComputerScienceq0Z0q20q0Xq1q1Z0q2q0Xq10q0Xq1q1Xq1q0Xq11;q1Xq11;q1Z0q2;,为简洁,记q0Z0q2为A,q0Xq1为B,q1Xq1为C,q1Z0q2为D,上述文法的产生式改写如下:SA;A0BD;B0BC;B1;C1;D;,23,CollegeofComputerScience&Technology,BUPT,作业:Ch4习题20,21,22,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 自动机 上下文 无关 文法 下推自动机
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文