1、|C|b, CAS|b 实际上只去掉了无用符号a和c。 32 下面对G去掉单一产生式: 对任何A,B，如果有A*B，且B1|2|n 是 P中B的所有非单一产生式，则把所有A1|2|n 加到P 中。 P: SA, AAb|bS|C|b, CAS|b 下面去掉单一产生式SA, AC, 得P： SAb|bS|C|b , AAb|bS|AS|b, CAS|b 再去掉SC, 得 SAb|bS|AS|b , AAb|bS|AS|b, CAS|b 但是，可以看出C是无用符号，所以CAS|b也被去掉。 最后得：G=(S,A,b,P,S) P: SAb|bS|AS|b , AAb|bS|AS|b, 33 2给定
2、CFG G=(S,A,B,C,a,b,P,S)，其中， P：SABC, ABB|, BCC|a, CAA|b, 去掉G中的生成式。 解：首先求出可为零的变元，即可以推出的变元。 显然有A、C、B和S。 如果AX1X2XnP，则将所有形如A12n的 产生式都加到P中，其中 如果Xi不是可为零的，则iXi 。 如果Xi是可为零的，则iXi或者i。但是， 如果所有Xi(i=1,2,n)都是可为零的，则不可所有i。 于是最后得： SABC|BC|AC|AB|C|B|A, ABB|B, BCC|C|a, CAA|A|b, 34 3给定CFG G=(S,A ,0,1, P, S )，其中， P：SAA0,
3、 ASS1, 将G写成GNF形式。 解：此时G已经具备CNF形式。(ABC, Da) (1)变元重新命名：令A1=S, A2=A, P: A1A2A2 |0 , A2A1A1|1, (2)处理A2 A1A1|1, 变成： A2A2A2A1|0A1|1 , (3)处理左递归A2A2A2A1|0A1|1 , 变成： A20A1|1| 0A1Z2 |1Z2, Z2 A2A1| A2A1 Z2, (4)处理A1A2A2 |0 ，得 A1 0A1A2|1A2| 0A1Z2A2 |1Z2A2 | 0 (5)处理Z2 A2A1| A2A1 Z2, 分别得： Z2 0A1A1 |1A1 | 0A1Z2A1 |
4、 1Z2A1 Z2 0A1A1Z2 |1A1Z2 | 0A1Z2A1Z2 | 1Z2A1Z2 35 最后得G=(A1,A2,Z2,0,1,P,A1) P: A1 0A1A2|1A2| 0A1Z2A2 |1Z2A2 | 0 A20A1|1| 0A1Z2 |1Z2, Z2 0A1A1 |1A1 | 0A1Z2A1 | 1Z2A1 Z2 0A1A1Z2 |1A1Z2 | 0A1Z2A1Z2 | 1Z2A1Z2 36 4构造一个PDA M，使得 T(M)= w| wa,b* w 中a,b的个数相等。 解：设计思想： 有两个状态q1和q2 ：q1是开始状态， q2 是终止状态。 栈内符号：A，B，R (
5、R是开始时栈内符号)。 开始时：读a，向栈压入A；读b，向栈压入B。 之后：当读a时：如果栈顶是A，再向栈压入一个A； 如果栈顶是B，则B退栈。 当读b时：如果栈顶是B，再向栈压入一个B； 如果栈顶是A，则A退栈。 如果w中a,b的个数相等，则M读完w后，栈顶应该是R， 此时M进入终止状态q2 。 37 令M=(q1,q2,a,b,A,B,R, q1,R,q2) (q1,a,R)=(q1,AR) (q1,b,R)=(q1,BR) (q1,a,A)=(q1,AA) (q1,a,B)=(q1, ) (q1,b,A)=(q1, ) (q1,b,B)=(q1,BB) (q1, ,R)=(q2, ) 如
6、w=bbabaa 时，M识别w的过程： 表示ID间的变化。 (q1,bbabaa,R)(q1,babaa,BR)(q1, abaa,BBR) (q1, baa,BR) (q1,aa,BBR) (q1,a,BR) (q1,R) (q2,) 再如wabbab，看看M是如何拒绝接收的。 (q1,abbab,R)(q1, bbab,AR)(q1, baa, R)(q1, aa,BR) (q1,a,R) (q1,AR) 无下一个动作，wT(M) 38 5给定CFG G=（S,A,B,a,b,c,P,S），其中 P为：SaAB | aA AbSa | Ab | Bc | b， 求一个PDA M，使得T(M
7、)=L(G)。 解:(1)先简化G，因为G中无产生式和单一产生式，所 以只去掉无用符号：对G应用引理3-2.1，执行上述算法， 得到的结果如下表所示： 得G=(S,A,a,b,c,P,S) P：SaA AbSa | Ab | b， 循环次数i 初值 1 2 3 OLD NEW A, S A A A,SA, S 39 P：SaA AbSa | Ab | b， 再对G应用引理3-2.2处理，执行算法的结果如下表所示 ： 得G=(S,A,a,b,P,S) P: SaA AbSa | Ab | b， (2)将G变成GNF形式 先变成： SaA, AbSD | Ab | b , D a ， 处理左递归A
8、Ab | bSD | b , 变成：AbSD | b | bSDZ|bZ, Zb |bZ 最后得： SaA，AbSD|b|bSDZ|bZ, Zb|bZ，D a 循环次数i 初值 1 2 3 S S,A S,A T a a,b 40 SaA，AbSD| b| bSDZ| bZ, Zb | bz， D a ， (3)根据上述文法，构造PDAM使得N(M)=L(G) M=(q,a,b,S,A,D,Z,q,S,) :由SaA得： (q,a,S)=(q,A) 由AbSD| b| bSDZ| bZ得： (q,b,A)=(q,SD),(q,),(q,SDZ),(q,Z) 由Zb|bz得：(q,b,Z)=(q
9、,),(q,Z) 由D a 得： (q,a,D)=(q,) (4)根据M变成M,使得T(M)=N(M). M=(q0,q,q1,a,b,S,A,D,Z,E,q0,E,q1) : (q0,E)=(q,SE) (q,a,S)=(q,A) (q,b,A)=(q,SD),(q,),(q,SDZ),(q,Z) (q,b,Z)=(q,),(q,Z) (q,a,D)=(q,) (q,E)= (q1,) 41 6给定PDA M=(q0,q1,0,1,Z0 ,X , q0,)，其中 如下： (q0,1, Z0)=(q0, XZ0) (q0,1,X)=(q0, XX) (q0,0, X)=(q1, X) (q0,
10、 Z0)=(q0,) (q1,1, X)=( q1,) (q1,0, Z0)=(q0, Z0) 求一个CFG G 使得L(G)=N(M). 解：令M=(K,q0,Z0,)，N(M)=L。 构造一个CFG G =(,S)，其中 q,A,p|q,pK,AS =0,1 S,q0,Z0,q0,q0,Z0,q1,q1,Z0,q0,q1,Z0,q1, q0,X,q0,q0,X,q1, q1,X,q0, q1,X,q1 P中产生式有三种类型： 42 1对任何qK,有 Sq0,Z0,q。 1）Sq0,Z0,q0 2）Sq0,Z0,q1 2对K中任何q,q1,q2,qm,qm+1=p，任何a， 任何A,B1,B
11、2,Bm， 只要(q,a,A)中含有(q1,B1B2Bm)，则有产生式 q,A,paq1,B1,q2q2,B2,q3qm,Bm,p。 由 (q0,1, Z0)=(q0, XZ0) 3）q0,Z0,q01q0,X,q0q0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q0 5）q0,Z0,q11q0,X,q0q0,Z0,q1 6）q0,Z0,q11q0,X,q1q1,Z0,q1 43 由(q0,1,X)=(q0,XX)得 7）q0,X,q01q0,X,q0q0,X,q0 8）q0,X,q01q0,X,q1q1,X,q0 9）q0,X,q11q0,X,q0q0,X,q1 10）q0
12、,X,q11q0,X,q1q1,X,q1 由(q0,0,X)=(q1,X)得 11）q0,X,q00q1,X,q0 12）q0,X,q10 q1,X,q1 由(q1,0,Z0)=(q0, Z0)得 13）q1,Z0,q00q0,Z0,q0 14）q1,Z0,q10 q0,Z0,q1 44 3任何q,pK，任何a,任何A， 如果有(q,a,A)中含有(p,)，有生式 q,A,pa 。 由 (q0,Z0)=(q0,)得 15）q0,Z0,q0 由 (q1,1,X)=(q1,)得 16）q1,X,q11 下面对这些产生式进行整理。 45 1）Sq0,Z0,q0 2）Sq0,Z0,q1 3）q0,Z0
13、,q01q0,X,q0q0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q0 5）q0,Z0,q11q0,X,q0q0,Z0,q1 6）q0,Z0,q11q0,X,q1q1,Z0,q1 7）q0,X,q01q0,X,q0q0,X,q0 8）q0,X,q01q0,X,q1q1,X,q0 9）q0,X,q11q0,X,q0q0,X,q1 10）q0,X,q11q0,X,q1q1,X,q1 11）q0,X,q00q1,X,q0 12）q0,X,q10 q1,X,q1 13）q1,Z0,q00q0,Z0,q0 14）q1,Z0,q10 q0,Z0,q1 15）q0,Z0,q0 16）q
14、1,X,q11 无产生式 无产生式 死循环 无产生式 无产生式 无产生式 将14)代入后，死循环 去掉6)后,无产生式 去掉5)6)后,无产生式 46 最后得： 1） Sq0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q0 10）q0,X,q11q0,X,q1q1,X,q1 12）q0,X,q10 q1,X,q1 13）q1,Z0,q00q0,Z0,q0 15）q0,Z0,q0 16）q1,X,q11 47 7求证下面语言L不是CFL， L=a k| k是个素数。 证明：(1) 假设L是CFL。 (2)令n是L满足CFL泵作用引理常数。 (3)取zam，mn 且m是个素数。|
15、z|=mn, 根据CFL 的泵作用引理，可将z写成 z=uvwxy 形式，其中|vwx|n, |vx|1, 且对任何i0 有 uviwxiyL。 (4)令u=an1, v=an2, w=an3, x=an4, y=an5,于是|vx|=n2+n41, n1+n2+n3 +n4 + n5 =m , z=uvwxy=an1+n2+n3+n4+n5 = a m, uviwxiy=an1+in2+n3+in4+n5 =am+(i-1)n2+(i-1)n4= am+(i-1)(n2+n4) 取i=m+1,则 uvm+1wxm+1y=am+(m+1-1)(n2 +n4)=am+m(n2+n4) =am(1
16、+n2+n4) 由于n2 +n4 1，故1+ n2 +n4 2, 而m2, 所以m(1+n2 +n4 )不是素 数，故 uvm+1wxm+1y L，产生矛盾。所以L不是CFL。 48 和实行有效控制，尽 量缩短创新周期，强调高效率的研究开发和高质量 的产品生产，评价活动应贯穿创新的全过程。 88 （4）强调市场导向，强调满足用户需要， 尽可能地让潜在用户参与创新过程，为顾 客提供良好的技术服务。 （5）重视人力资源开发，吸引和培养高水 平的管理人员和技术人才并对他们进行有 效的激励，为他们提供充分发挥才能的机 会。 （6）采用有效的组织结构和组织方式，组 织要具有柔性，人员构成要适应创新工作
17、的要求。 89 技术创新成功的战略要素 （1）高级管理层对创新给予有力的支持， 愿意承担创新风险； （2）有一个长期的企业战略，创新在该战 略中起着关键作用； （3）形成了接纳创新，鼓励创新，积极响 应变革的机制和企业文化； （4）资源配置不仅考虑短期投资收益，更 重视企业的长远发展； （5）企业的技术、组织、制度和观念具有 柔性，能适应创新。 90 创新产品的性能和质量、创新产品优于现 行竞争产品的程度是决定创新能否成功的 先决条件。新产品与现有产品之间在技术 与生产上的兼容性、相关产业和技术对创 新的支持也是重要的创新成功因素。 任何一个企业的创新绩效与创新潜力，都 可看成是企业所处环境的
18、函数。金融环境 、市场环境、政策法律环境、社会环境、 文化环境、政治和制度环境都会对创新成 功产生影响。 技术创新成功的其他要素 91 何为最佳创新公司 创新的速度比对手快 创新的成本比对手低 拥有大量的知识资源 92 3M公司最富创新精神的公司 6万个员工拥有6万多个产品 每年新产品200-300个 93 我国首台核心路由器研制成功 由国防科技大学计算机学院和大唐电信科技 股份有限公司共同承担的国家“863”重大攻关课 题“中国高速信息示范网核心路由器” 在 北京通过国家技术鉴定，这标志着我国在信息 技术领域研究取得重大突破，实现了跨越式发 展。 这台名为“银河玉衡”的核心路由器， 是我国高
19、速信息示范网的关键设备，其报文转 发率为每秒2500万个，信息吞吐量每秒400亿比 特（计算机存储基本单位）以上，相当于每秒 传输25亿个汉字信息。 94 核心路由器是高速信息网发展的重中之重 ，代表着一个国家信息领域的技术水平。1999年，科 技部将研制中国高速信息示范网的核心路由器，作为 “863”信息领域跨主题的重大攻关项目在全国招标。拥 有雄厚技术实力的国防科技大学和大唐电信科技股份 有限公司中标后，由中国工程院院士、国防科技大学 计算机学院院长卢锡城挂帅的课题组，仅用一年多时 间，就高质量地完成了研制任务。 鉴定表明，“银河玉衡”核心路由器，是国 内第一台拥有自主知识产权的高端线速核心路由器。 它在分布体系结构、无阻塞交换网络、大步调度策略 、网络处理器、协议软件分布等关键技术上取得了突 破。 据介绍，这台核心路由器目前已应用到 北京中国高速信息示范网。它可以与现行网络设备互 连、互通、互操作，能满足国家、省级宽带骨干网和 局域网建设要求，可广泛应用于通信、电视、电力、 国防、金融等领域。 95
