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

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

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

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

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

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

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

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

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

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

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

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

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

12 引理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 《理论计算机科学基础》

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48 过程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’). 《理论计算机科学基础》

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

66 断言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的所有字符串. 《理论计算机科学基础》

67 断言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. 《理论计算机科学基础》

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

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

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

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

72 断言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 # 《理论计算机科学基础》

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

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

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

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

77 引理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 《理论计算机科学基础》

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

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

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

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

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

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

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

85 例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 《理论计算机科学基础》

86 例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)* 《理论计算机科学基础》

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

106 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. 《理论计算机科学基础》

107 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. 《理论计算机科学基础》

108 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. 《理论计算机科学基础》

109 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. 《理论计算机科学基础》

110 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. 《理论计算机科学基础》

111 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. # 《理论计算机科学基础》

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

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

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

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

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

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

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

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

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

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

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

123 例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多, 矛盾; 《理论计算机科学基础》

124 例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*, 矛盾. # 《理论计算机科学基础》

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

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

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

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

129 例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的个数多, 《理论计算机科学基础》

130 例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, 矛盾. # 《理论计算机科学基础》

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

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

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

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

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

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

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

138 例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. 《理论计算机科学基础》

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

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

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

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

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

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

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

146 例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. 《理论计算机科学基础》

147 例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, 《理论计算机科学基础》

148 例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. 《理论计算机科学基础》

149 例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矛盾. # 《理论计算机科学基础》

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

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

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

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

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

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

156 例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的成员, 这与泵引理矛盾. # 《理论计算机科学基础》