第6 章P231: 1、构造产生下列语言的CFG (2) {1n02m1n |n,m≥1} 解:需保证1 的个数相等且0 的个数为偶数 S1S1|1A1 A00A|00 (4)含有相同个数的0 和1 的所有0、1 串 S0AS|1BS|ε A1|0AA B0|1BB 错解1: S10S|01S|10|01|ε 错解2: S1S0|0S1|1A0|0A1, A10|01|ε (推不出 0110) 错解3: S10S|1S0|S10|01S|0S1|S01|ε (推不出 00111100) 讨论: 不能限制 0 和1 必须在同一次推导中都出现 15、构造与下列文法(原题中去 产生式后的文法)等价的CNF Sa|b|aB|aBB|bA|bAA Baa|aB|Ba|aBa Abb|bbA 解:第一步 Sa|b|BaB|BaBB|BbA|BbAA BBaBa|BaB|BBa|BaBBa ABbBb|BbBbA Baa Bbb 第二步 Sa|b|BaB|BaB1|BbA|BbA1 BBaBa|BaB|BBa|BaB2 ABbBb|BbB3 Baa Bbb B1BB A1AA B2BBa B3BbA 讨论: 这种题需要将步骤写清, 意义在于机械化这种事情是我们的目标, 你不必加入太多自己的智慧. Ba和Ba的区别? 第7 章 P257: 1、构造识别下列语言的PDA (2) L = {1n02m1n|n,m≥1} 要求 用两种方法做 用七元组表示 用推广的状态转换图表示 解法 1:先构造产生该语言的GNF 文法,再由文法推导的启示或依定理 7-3 的构造方法,设计出 PDA 构造出产生该语言的CFG S1S1|1B1 B00B|00 得到对应的GNF: S1SA|1BA A1 B0C|0CB C0 构造PDA M1=({q},{0,1},{S,A,B,C}, δ1, q, S, Φ) 其中δ1 为: δ1(q, 1, S)={(q, SA), (q, BA)} δ1(q, 1, A)={(q, ε) } δ1(q, 0, B)={(q, C), (q, CB)} δ1(q, 0, C)={(q, ε) } 有N(M1)= {1n02m1n|n,m≥ 1} 用推广的状态转换图如右所示: 提示,还可以仿照书中例题,加入终止状态qf 及初始栈符号Z, 使 N(M1)= L(M1)={1n02m1n|n,m≥1}, 注意: 如果要这样做, 请加适当的说明 解法1 拓展(2005 级崔卫华的想法):问能否把GNF 中Aa 中的a 用作00 思考: 崔同学实际是想设计接受{1nam1n|n,m≥1}的PDA 以简化, 但又没有底气 这种想法很大胆(褒义的"大胆") 也是可行的. 过程是: 先设计PDA 接受L={1nam1n|n,m≥1} 这儿={1,a} 构造代换f: f(1)=1, f(a)=00, 则f(L)就是我们要的={1,0} 上的语言, PDA随之而定 只是未向同学们介绍如何利用代换设计PDA 解法2 之一:可以将 PDA 的工作分为3 个阶段: (1...