正则表达式 描述模式的手段 例: (01)0* = ({0}{1}){0}* = {0,1}{0}* 《理论计算机科学基础》

例2.25 ={0,1} 是任意字母表 (01)* = {0,1}* = * 表示所有长为1的串组成的语言 * 表示所有串组成的语言 *1 表示所有以1结尾的串组成 的语言 (0*)(*1)表示所有以0开头或 以1结尾的串组成的语言 《理论计算机科学基础》

正则表达式的形式定义 定义2.26: R是正则表达式 当且仅当R是 L(R): R表示的语言 a, a; /* 表示 {a} */ ; /* 表示 {} */ ; /* 表示  */ (R1R2), R1和R2都是正则表达式; (R1R2), R1和R2都是正则表达式; (R1*), R1是正则表达式. L(R): R表示的语言 《理论计算机科学基础》

说明 归纳定义 省略括号 优先级 用较小的表达式定义较大的表达式 最外层 规定优先级 星号 > 连接 > 并 《理论计算机科学基础》

例2.27 设={0,1} 0*10* = { w | w恰好有一个1 } *1* = { w | w至少有一个1 } 《理论计算机科学基础》

例2.27(续) 0110 = { 01, 10 } 0*0  1*1  0  1 = { w | w首尾符号相同 } (0)1* = 01*1* (0)(1) = {,0,1,01} 1* =  * = {} 《理论计算机科学基础》

几个恒等式 R = R R = R 一般 R  R, R  R R = R{} R =  《理论计算机科学基础》

例 数值常量 {+,-,}(DD*DD*.D*D*.DD*) D={0,1,2,3,4,5,6,7,8,9} 72 3.14159 +7. -.01 《理论计算机科学基础》

正则表达式与自动机等价性 定理2.28: 一个语言是正则的 当且仅当可用正则表达式描述 这个语言. 引理2.29:正则表达式描述 正则语言. 引理2.32:正则语言可用 正则表达式描述. 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明思路: 把正则表达式转化成 等价NFA 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 1) R=a, a. L( R )={a}, N=({q1,q2},,,q1,{q2}), (q1,a)={q2}, (r,b)=, 若rq1或ba. a q1 q2 N 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 2) R=. L( R )={}, N=({q1},,,q1,{q1}), r,b, (r,b)=. q1 N 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 3) R=. L( R )=, N=({q1},,,q1,), r,b, (r,b)=. q1 N 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 4) R=(R1R2), N N1   N2 《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 5) R=(R1R2), N1 N2 N   《理论计算机科学基础》

引理2.29 引理2.29:正则表达式描述正则语言. 证明: 6) R=(R1*), N  N1   # 《理论计算机科学基础》

例2.30 (aba)* 《理论计算机科学基础》

例2.30 (aba)* a a 《理论计算机科学基础》

例2.30 (aba)* a b a b 《理论计算机科学基础》

例2.30 (aba)* a b ab a b a  b 《理论计算机科学基础》

例2.30 (aba)* a b ab aba a b a  b a  b  a  《理论计算机科学基础》

例2.30 (aba)* a b ab aba a b a  b a  b  a   a  b    a #  《理论计算机科学基础》

例2.31 (ab)*aba 《理论计算机科学基础》

例2.31 (ab)*aba a a 《理论计算机科学基础》

例2.31 (ab)*aba a b a b 《理论计算机科学基础》

例2.31 (ab)*aba a b ab a b a  b  《理论计算机科学基础》

例2.31 (ab)*aba a b ab (ab)* a b a  b   a    b  《理论计算机科学基础》

例2.31 (ab)*aba aba a b a a  b  a 《理论计算机科学基础》

例2.31 (ab)*aba (ab)* aba  a    b  a  b  a 《理论计算机科学基础》

例2.31 (ab)*aba  a    b     a  b  a # 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 证明思路 给定DFA或NFA,构造等价正则表达式 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 证明思路 给定DFA或NFA,构造等价正则表达式 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 证明思路 给定DFA或NFA,构造等价正则表达式 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 证明思路 广义非确定型有穷自动机(GNFA) 从DFA构造等价的GNFA 《理论计算机科学基础》

GNFA: 箭头标号是正则表达式 ab* aa qstart a* abba  (aa)* b* qaccept ab b 《理论计算机科学基础》

GNFA的特殊形式 初始状态 接受状态 其他每个状态 有到所有其他状态的箭头 所有其他状态都没有到它的箭头 唯一, 且与初始状态不同 没有到任何其他状态的箭头 所有其他状态都有到它的箭头 其他每个状态 都有到自身和其他状态的箭头 《理论计算机科学基础》

从DFA到GNFA a DFA b    GNFA  ab  《理论计算机科学基础》

从GNFA到正则表达式 依次把GNFA状态数减少1个 R4 qi qj R1 R3 qrip R2 (R1)(R2)*(R3)(R4) 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用 正则表达式描述. 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用 正则表达式描述. 证明: 设正则语言A被DFA M识别. 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用 正则表达式描述. 证明: 设正则语言A被DFA M识别. 把M转换成等价的GNFA G. 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用 正则表达式描述. 证明: 设正则语言A被DFA M识别. 把M转换成等价的GNFA G. 利用过程CONVERT(G)把G转换成等价的正则表达式. 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用 正则表达式描述. 证明: 下面分别给出: GNFA的形式定义 过程CONVERT(G) 《理论计算机科学基础》

GNFA的形式定义 GNFA是5元组(Q,,,qstart,qaccept) Q是有穷状态集 是输入字母表 :(Q-{qaccept})(Q-{qstart})R 是转移函数 (R是字母表上 全体正则表达式的集合) qstart是初始状态 qaccept是接受状态 《理论计算机科学基础》

GNFA计算的形式定义 输入w=w1w2…wk, wi* 计算: 状态序列 q0,q1,…,qk 接受计算: q0=qstart 是初始状态 i, wiL(Ri), Ri=(qi-1,qi) 接受计算: qk=qaccept是接受状态 《理论计算机科学基础》

过程CONVERT(G) 令k是G的状态数. 若k=2, 则返回正则表达式 (qstart,qaccept). 若k>2, 则 任取qripQ-{qstart,qaccept}, Q’=Q-{qrip}. 对每个qiQ’-{qaccept}和qjQ’-{qstart}, ’(qi,qj)=(R1)(R2)*(R3)(R4), 其中 R1=(qi,qrip), R2=(qrip,qrip), R3=(qrip,qj), R4=(qi,qj) GNFA G’=(Q’,,’,qstart,qaccept). 返回CONVERT(G’). 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 1) k=2时. 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 1) k=2时. 当G只有2个状态时, 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 1) k=2时. 当G只有2个状态时, G只能有一个箭头从初始状态到接受状态, 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 1) k=2时. 当G只有2个状态时, G只能有一个箭头从初始状态到接受状态, 箭头上标记的正则表达式描述能使G到达接受状态的所有字符串. 《理论计算机科学基础》

断言2.34 断言2.34: 对于任意GNFA G, CONVERT(G)都等价于G. 证明: 对G的状态数k作归纳证明. 1) k=2时. 当G只有2个状态时, G只能有一个箭头从初始状态到接受状态, 箭头上标记的正则表达式描述能使G到达接受状态的所有字符串. 因此这个表达式等价于G. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 则删除这些qrip, 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 则删除这些qrip,得到G’的接受计算. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 则删除这些qrip,得到G’的接受计算. 设状态qi和qj之间有若干连续的qrip, 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 则删除这些qrip,得到G’的接受计算. 设状态qi和qj之间有若干连续的qrip,则它们之间箭头上的新正则表达式就描述G中使qi经过qrip到qj的所有字符串. 《理论计算机科学基础》

断言2.34 证明: (续) 2) 设断言对k-1个状态为真. 先证明G与G’等价. 设G接受输入w, 设一种可能的计算为qstart,q1,q2,q3,…,qaccept. 若该计算中不含被删除的状态qrip, 则G’显然也接受w. 若该计算中含有qrip, 则删除这些qrip,得到G’的接受计算. 设状态qi和qj之间有若干连续的qrip,则它们之间箭头上的新正则表达式就描述G中使qi经过qrip到qj的所有字符串. 因此G’接受w. 《理论计算机科学基础》

断言2.34 证明: (续) 设G’接受输入w, 《理论计算机科学基础》

断言2.34 证明: (续) 设G’接受输入w, 由于G’中任意两个状态qi和qj之间箭头上的正则表达式描述G中使qi直接或经过qrip到qj的所有字符串, 《理论计算机科学基础》

断言2.34 证明: (续) 设G’接受输入w, 由于G’中任意两个状态qi和qj之间箭头上的正则表达式描述G中使qi直接或经过qrip到qj的所有字符串, 因此G接受w. 《理论计算机科学基础》

断言2.34 证明: (续) 设G’接受输入w, 由于G’中任意两个状态qi和qj之间箭头上的正则表达式描述G中使qi直接或经过qrip到qj的所有字符串, 因此G接受w. 因此, G和G’等价. 《理论计算机科学基础》

断言2.34 证明: (续) 设G’接受输入w, 由于G’中任意两个状态qi和qj之间箭头上的正则表达式描述G中使qi直接或经过qrip到qj的所有字符串, 因此G接受w. 因此, G和G’等价. 由归纳假设, CONVERT(G’)等价于G’. 由于CONVERT(G)就是CONVERT(G’), 所以CONVERT(G)等价于G. # 《理论计算机科学基础》

引理2.32 引理2.32: 正则语言可用正则表达式描述. 《理论计算机科学基础》

引理2.32(不严格证明) 引理2.32: 正则语言可用正则表达式描述. 证明: 1) 加新始终点 (使始点不再进, 终点不再出);  《理论计算机科学基础》

引理2.32(不严格证明) 引理2.32: 正则语言可用正则表达式描述. 证明: 1) 加新始终点 (使始点不再进, 终点不再出); 2) 合并平行边;  r s (rs) 《理论计算机科学基础》

引理2.32(不严格证明) 引理2.32: 正则语言可用正则表达式描述. 证明: 1) 加新始终点 (使始点不再进, 终点不再出); 2) 合并平行边; 3) 去中间点 (使顶点个数减少);  r s (rs) r1 rk s1 sh t rk i j rit*sj 《理论计算机科学基础》

引理2.32(不严格证明) 引理2.32: 正则语言可用正则表达式描述. 证明: # 1) 加新始终点 (使始点不再进, 终点不再出); 2) 合并平行边; 3) 去中间点 (使顶点个数减少); 4) 重复2)和3)至完成. #  r s (rs) r1 rk s1 sh t rk i j rit*sj R 《理论计算机科学基础》

例2.35 1 2 a b a,b 《理论计算机科学基础》

例2.35 1 2 a b a,b s  《理论计算机科学基础》

例2.35 1 2 a b a,b s  b(ab)* 《理论计算机科学基础》

例2.35 1 2 a b a,b s  b(ab)* a*b(ab)* 《理论计算机科学基础》

例2.36 1 3 2 a b 《理论计算机科学基础》

例2.36 1 3 2 a b s  《理论计算机科学基础》

例2.36 1 3 2 a b s  3 2 a baa aab s b ab  bb 《理论计算机科学基础》

例2.36 1 3 2 a b s  3 2 a baa aab s b ab  bb a(aab)* a(aab)*abb (baa)(aab)*abbb 《理论计算机科学基础》

例2.36 1 3 2 a b s  3 2 a baa aab s b ab  bb a(aab)* a(aab)*abb (baa)(aab)*abbb s 3 (a(aab)*abb)((baa)(aab)*abbb)* ((baa)(aab)*)a(aab)* 《理论计算机科学基础》

非正则语言 为 B = { 0n1n | n0 } 设计DFA ? 《理论计算机科学基础》

非正则语言 为 B={0n1n | n0} 设计DFA ? B={0n1n | n0}是不是正则的 ? 《理论计算机科学基础》

非正则语言 设 ={0,1} B={0n1n | n0} ? 《理论计算机科学基础》

非正则语言 设 ={0,1} B={0n1n | n0} ? C={w | w中0和1一样多} ? 《理论计算机科学基础》

非正则语言 设 ={0,1} B={0n1n | n0} ? C={w | w中0和1一样多} ? B=C0*1* 《理论计算机科学基础》

非正则语言 设 ={0,1} B={0n1n | n0} ? C={w | w中0和1一样多} ? B=C0*1* D={w | w中子串01和10一样多} ? 《理论计算机科学基础》

非正则语言 设 ={0,1} B={0n1n | n0} ? C={w | w中0和1一样多} ? B=C0*1* D={w | w中子串01和10一样多 } ? 01000000111111100101110111 《理论计算机科学基础》

非正则语言 设 ={0,1} D是正则的, B和C不是 B={0n1n | n0} ? C={w | w中0和1一样多} ? D={w | w中子串01和10一样多 } ? 01000000111111100101110111 D是正则的, B和C不是 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则s=xyz, 并且满足下述条件: 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则s=xyz, 并且满足下述条件: 1) i0, xyizA; 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则s=xyz, 并且满足下述条件: 1) i0, xyizA; 2) |y|>0; 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则s=xyz, 并且满足下述条件: 1) i0, xyizA; 2) |y|>0; 3) |xy|p. 《理论计算机科学基础》

泵引理 定理2.37(泵引理): 设A是正则语言, 则存在常数p(称为泵长度), 使得若sA且|s|p, 则s=xyz, 并且满足下述条件: 1) i0, xyizA; 2) |y|>0; 3) |xy|p. x y z 《理论计算机科学基础》

x y z 泵引理 证明: 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), 《理论计算机科学基础》

泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. y x z 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 根据鸽巢原理, 存在j<l,使得 rj=rl, lp+1. 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 根据鸽巢原理, 存在j<l,使得 rj=rl, lp+1. 令 x=s1…sj-1, y=sj…sl-1, z=sl…sn+1. 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 根据鸽巢原理, 存在j<l,使得 rj=rl, lp+1. 令 x=s1…sj-1, y=sj…sl-1, z=sl…sn+1. 由于x让M从r1到rj, y让M从rj到rj, z让M从rj到rn+1, 而rn+1是接受状态, 所以i0, xyizA. 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 根据鸽巢原理, 存在j<l,使得 rj=rl, lp+1. 令 x=s1…sj-1, y=sj…sl-1, z=sl…sn+1. 由于x让M从r1到rj, y让M从rj到rj, z让M从rj到rn+1, 而rn+1是接受状态, 所以i0, xyizA. 由于jl, 所以|y|>0. 《理论计算机科学基础》

x y z 泵引理 证明: 设A=L(M), M=(Q,,,q1,F), |Q|=p, s=s1s2…snA, np. 设M在s上计算r1,r2,…,rn+1, (ri,si)=ri+1. 根据鸽巢原理, 存在j<l,使得 rj=rl, lp+1. 令 x=s1…sj-1, y=sj…sl-1, z=sl…sn+1. 由于x让M从r1到rj, y让M从rj到rj, z让M从rj到rn+1, 而rn+1是接受状态, 所以i0, xyizA. 由于jl, 所以|y|>0. 由于lp+1, 所以|xy|p. # 《理论计算机科学基础》

泵引理用法 证明语言B不是正则的. 《理论计算机科学基础》

泵引理用法 证明语言B不是正则的. (反证) 假设B是正则的, 设p是泵长度. 《理论计算机科学基础》

泵引理用法 证明语言B不是正则的. (反证) 假设B是正则的, 设p是泵长度. 取sB, |s|p. 《理论计算机科学基础》

泵引理用法 证明语言B不是正则的. (反证) 假设B是正则的, 设p是泵长度. 取sB, |s|p. 根据泵引理, s=xyz, i0, xyizB. |xy|p, |y|>0, 《理论计算机科学基础》

泵引理用法 证明语言B不是正则的. (反证) 假设B是正则的, 设p是泵长度. 取sB, |s|p. 根据泵引理, s=xyz, i0, xyizB. |xy|p, |y|>0, 证明i0, 使得xyizB, 矛盾. 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 则s=xyz, 对任意i0, xyizB. 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 则s=xyz, 对任意i0, xyizB. 下面分3种情况: 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 则s=xyz, 对任意i0, xyizB. 下面分3种情况: y0*0, 则xy2z中0比1多, 矛盾; 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 则s=xyz, 对任意i0, xyizB. 下面分3种情况: y0*0, 则xy2z中0比1多, 矛盾; y1*1, 则xy2z中1比0多, 矛盾; 《理论计算机科学基础》

例2.38 B = { 0n1n | n0 }不是正则的. 证明: (反证) 假设B是正则的, 设p是泵长度. 令s=0p1p, 则s=xyz, 对任意i0, xyizB. 下面分3种情况: y0*0, 则xy2z中0比1多, 矛盾; y1*1, 则xy2z中1比0多, 矛盾; y0*011*, 则xy2z0*1*, 矛盾. # 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 证明:(反证) 假设C是正则的. 设p是C的泵长度,令 s= 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 证明:(反证) 假设C是正则的. 设p是C的泵长度,令 s=0p1p. 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 证明:(反证) 假设C是正则的. 设p是C的泵长度,令 s=0p1p. 于是 s=xyz, |xy|p, y0*0, 且对任意i, xyiz 属于C. 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 证明:(反证) 假设C是正则的. 设p是C的泵长度,令 s=0p1p. 于是 s=xyz, |xy|p, y0*0, 且对任意i, xyiz 属于C. 但 xy2z 中 0的个数比1的个数多, 《理论计算机科学基础》

例2.39 C={ w|w中0和1个数相等 }不是正则的. 证明:(反证) 假设C是正则的. 设p是C的泵长度,令 s=0p1p. 于是 s=xyz, |xy|p, y0*0, 且对任意i, xyiz 属于C. 但 xy2z 中 0的个数比1的个数多, 所以 xy2z不属于C, 矛盾. # 《理论计算机科学基础》

例2.40 F={ ww | w{0,1}* }不是正则的. 《理论计算机科学基础》

例2.40 F={ ww | w{0,1}* }不是正则的. 证明:(反证) 假设F是正则的. 设p是F的泵长度,令s= 《理论计算机科学基础》

例2.40 F={ ww | w{0,1}* }不是正则的. 证明:(反证) 假设F是正则的. 设p是F的泵长度,令s=0p10p1. 《理论计算机科学基础》

例2.40 F={ ww | w{0,1}* }不是正则的. 证明:(反证) 假设F是正则的. 设p是F的泵长度,令s=0p10p1. 于是 s=xyz, |xy|p, y0*0, 且对任意i,xyiz属于F. 《理论计算机科学基础》

例2.40 F={ ww | w{0,1}* }不是正则的. 证明:(反证) 假设F是正则的. 设p是F的泵长度,令s=0p10p1. 于是 s=xyz, |xy|p, y0*0, 且对任意i,xyiz属于F. 但 xy2z 不属于F, 矛盾. # 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明思路: 完全平方序列 0, 1, 4, 9, 16, 25, ….. 中的间隔越来越大 泵引理中s=xyz, xy0z, xy1z, xy2z, xy3z, xy4z, …… 的长度间隔是固定的|y| 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明思路: 设m=n2 (n+1)2-n2= 2n+1= 2m+1 设|xyiz|=m 若|y|<2|xyiz|+1, 则产生矛盾 设p是泵长度 令s=1p^2=xyz, 则|y||s|=p2 欲让2|xyiz|+1>(i|y|)i p2  |y|, 只需取i=p4. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz, 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2, 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D.令i=p4, 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D.令i=p4,设|xyiz| =m=n2. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D.令i=p4,设|xyiz| =m=n2. 则(n+1)2-n2=2n+1 =2m+1=2|xyiz|+1>(i|y|) i p2, 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D.令i=p4,设|xyiz| =m=n2. 则(n+1)2-n2=2n+1 =2m+1=2|xyiz|+1>(i|y|) i p2,但|xyi+1z|-|xyiz|=|y|p2. 《理论计算机科学基础》

例2.41 D={ 1n^2 | n0 }不是正则的. 证明:(反证) 假设D是正则的.设p是D的泵长度,令s=1p^2.于是s=xyz,0<|y||s|=p2,且对任意i,xyiz属于D.令i=p4,设|xyiz| =m=n2. 则(n+1)2-n2=2n+1 =2m+1=2|xyiz|+1>(i|y|) i p2,但|xyi+1z|-|xyiz|=|y|p2. 这说明|xyi+1z|不是完全平方数,与xyi+1z属于D矛盾. # 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s= 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s=0p+11p. 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s=0p+11p. 于是s=xyz, y只含0. 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s=0p+11p. 于是s=xyz, y只含0. 考虑串xyyz. 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s=0p+11p. 于是s=xyz, y只含0. 考虑串xy0z=xz. 《理论计算机科学基础》

例2.42 E={ 0i1j | i>j }不是正则的. 证明:(反证) 假设E是正则的.设p是E的泵长度.令s=0p+11p. 于是s=xyz, y只含0. 考虑串xy0z=xz. 删除y使0的个数减少, s中0只比1多一个, 因此xz中的0不可能比1多, 所以xz不是E的成员, 这与泵引理矛盾. # 《理论计算机科学基础》