计算理论_计算模型CH1_2016new

1、教材教材: 1王王 王晓东王晓东,计算机算法设计与分析计算机算法设计与分析(第第4版版),电子工业电子工业. 2S 唐常杰等译唐常杰等译, Sipser著著, 计算理论导引计算理论导引, 机械工业机械工业. 参考资料参考资料:3C 潘金贵等译潘金贵等译, Cormen等著等著, 算法导论算法导论, 机械工业机械工业. 4M 黄林鹏等译黄林鹏等译, Manber著著, 算法引论算法引论-一种创造性方法一种创造性方法, 电子电子. 5刘刘 刘汝佳等刘汝佳等, 算法艺术与信息学竞赛算法艺术与信息学竞赛, 清华大学清华大学.6L Lewis等著等著, 计算理论基础计算理论基础, 清华大学清华大学. 计

2、算理论与计算理论与算法分析设计算法分析设计 刘刘 庆庆 晖晖 计算理论计算理论 第一部分第一部分 计算模型计算模型 S第第1章章 有限自动机有限自动机 第第2章章 上下文无关语言上下文无关语言 第第3章章 图灵机图灵机 第第1章章 有限自动机有限自动机 从字符串匹配问题说起从字符串匹配问题说起 输入输入: 两个字符串两个字符串x, y, (|x|=n, |y|=m) 输出输出: 所有所有y在在x中出现的起点位置中出现的起点位置 例例: x=abaabababbabababbababaa, y=ababbababaa 输出输出13 直接法直接法: 以每个位置为起点对比一遍以每个位置为起点对比一遍

3、y. O(n-m+1)m) 观察改进方法观察改进方法 x: a b a a b a b a b b a b a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a 构造状态和转移函数构造状态和转移函数y=ababbababaa 0 1a2ab3aba4abab5ababb11ababbababaa10ababbababa9ababbabab8ababbaba7ababbab6ababbaaaaaaab

4、bbbbbbbbaaaaabbaf: 0:11 a,b 0:11 x: a b a a b a b a b b a b a b a b b a b a b a a 0 1 2 3 1 2 3 4 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 输出输出 23-10 = 13 b输入输入x,y, 串匹配的有限自动机算法串匹配的有限自动机算法符号集符号集 , m=Length(y), 计算计算转移函数转移函数, Yi=y1y2yi. 1. 对对 q = 0:m 2. 对每个符号对每个符号a , 3. k=minm,q+1 4. 当当 Yk不是不是Yqa的后缀的后缀, k- 5

5、. f(q,a)=k = a,bf(0,a)=1, f(0,b)=0, abab|b, f(4,b)=5,abab|a, f(4,a)=3, 匹配算法匹配算法 1. n=Length(x), q=0 2. 对对 i = 1:n 3. q=f(q,xi), 4. 若若q=m, 打印打印 i-m+1 字符串匹配算法字符串匹配算法算法算法预处理时间预处理时间匹配时间匹配时间朴素朴素0O(n-m+1)m)自动机自动机O(m| |) (n)Knuth-Morris-Pratt (m) (n)其中其中 是字母表是字母表 字符串与语言字符串与语言字母表字母表: 任意一个有限集任意一个有限集. 常用记号常用记

6、号 , . 符号符号: 字母表中的元素字母表中的元素字符串字符串: 字母表中符号组成的字母表中符号组成的有限序列有限序列 如如asdf, 通俗地说即单词通俗地说即单词串的串的长度长度|, 例例: |abcde|=5 串的串的连接连接*, 例例: (abc)*(de)=abcde 串的串的反转反转R, 例例: (abcde)R=edcba空词空词: 记为记为 , 长度为长度为0 语言语言: 给定字母表上一些给定字母表上一些字符串的集合字符串的集合 * *, ,语言语言, ,字典序字典序取字母表取字母表 = 0,1, 上的语言举例上的语言举例: A=0,00,0000, B=0,00,01,000

7、,001,l 上所有有限长串记为上所有有限长串记为 *. l 上上的任一语言都是的任一语言都是 *的子集的子集.l *(字典序字典序): , 0, 1, 00, 01, 10, 11, 000, l 上所有无限长串记为上所有无限长串记为 N. l 上的语言与上的语言与 N一一对应一一对应. * 0100011011000 001 B 0 0001 000 001 f(B)010110011等势等势, ,可数可数, ,不可数不可数l等势等势: 若两集合间存在一一对应若两集合间存在一一对应, 则称它们等势则称它们等势 l可数可数: 若若集合与集合与有限集或有限集或与自然数集等与自然数集等势势 或者

8、说集合元素可以按次序列出或者说集合元素可以按次序列出l不可数不可数: 若集合不是可数的若集合不是可数的 或者说集合元素不能按次序列出或者说集合元素不能按次序列出l * 可数可数 l N 不可数不可数(与与0,1中全体实数一一对应中全体实数一一对应)l 上上的全体语言不可数的全体语言不可数 决定性问题与语言一一对应决定性问题与语言一一对应决定性问题决定性问题(Dicision Prob): 只需回答是与否的问题只需回答是与否的问题 “一数是否是偶数一数是否是偶数” - 以以0结尾的结尾的01串串 “串串0,1个数是否相等个数是否相等”- 0,1个数相等的个数相等的01串串 “串长度是否是串长度是

9、否是2的幂次的幂次”- 02n : n 0 “图是否连通图是否连通”- | G是连通图是连通图 其中其中是图是图G编码成的字符串编码成的字符串.给定有限字母表给定有限字母表 , 每个输入是一个串每个输入是一个串, 任意串都可以是输入串任意串都可以是输入串 一个决定性问题是满足某性质的串的集合一个决定性问题是满足某性质的串的集合(语言语言) 当机器从简单到复杂当机器从简单到复杂, 能解决的问题也变复杂能解决的问题也变复杂确定型有限确定型有限(穷穷)自动机的形式定义自动机的形式定义定义定义: 有限自动机有限自动机是一个是一个5元组元组(Q, , ,s,F),1) Q是是有限集有限集, 称为称为状态

10、集状态集;2) 是是有限集有限集, 称为称为字母表字母表;3) : Q Q是是转移函数转移函数;4) s Q是是起始状态起始状态;5) F Q是是接受状态集接受状态集; 状态图等价于形式定义状态图等价于形式定义 Q=q1,q2,q3, 状态集状态集 =0,1, 字母表字母表 s=q1, 起始状态起始状态 F=q2接受状态集接受状态集 01q1q1q2q2q3q2q3q2q2M1q1q2q3000,111图灵对计算的观察图灵对计算的观察图灵图灵: 计算通常是一个计算通常是一个人人拿着拿着笔笔在在纸纸上进行的上进行的. 他他根据根据 眼睛眼睛看到的纸上符号看到的纸上符号, 脑脑中的若干中的若干法则

11、法则, 指示笔指示笔 在纸上在纸上擦掉或写上擦掉或写上一些符号一些符号, 再再改变他所看到的范围改变他所看到的范围. 继续继续, 直到他认为计算结束直到他认为计算结束. 脑脑:控制器控制器 纸纸:存储带存储带 眼睛和笔眼睛和笔:读写头读写头 法则法则:转移函数转移函数有限自动机是简化的图灵机有限自动机是简化的图灵机1101q1状态状态: q1,q2,q3 起始状态起始状态q1 接受状态接受状态q2 转移转移: 箭头箭头运行运行: 从起始状态开始沿转移箭头进行从起始状态开始沿转移箭头进行.输出输出: 输入读完处于接受状态则输入读完处于接受状态则接受接受, 否则否则拒绝拒绝. 接受接受: 1, 1

12、1, 100, 101, 1101, 拒绝拒绝: , 0, 10, 110, 1010, M1是读写头是读写头不能改写不能改写, 且且只能右移只能右移的图灵机的图灵机 q1q2q3000,111DFA计算计算的形式定义的形式定义设设M=(Q, , ,s,F)是一个是一个DFA,w=w1w2wn是字母表是字母表 上的一个字符串上的一个字符串.若若存在存在Q中中的状态序列的状态序列r0,r1,rn, 满足满足 1) r0 = s; 2) (ri, wi+1) = ri+1; 3) rn F则则M接受接受w.sw1r1w2r2rn-1wnrnq1q2q3000,111有限自动机的语言有限自动机的语言

13、:正则语言正则语言对有限自动机对有限自动机M, 若若 A = w* | M接受接受w , 即即A是有限自动机是有限自动机M的的语言语言, 记为记为L(M)=A, 也也称称M识别识别A. 注注: M的语言唯一的语言唯一. M不识别任何其它语言不识别任何其它语言. 若存在若存在DFA识别语言识别语言A, 则称则称A是是正则语言正则语言. 称两个有限自动机称两个有限自动机等价等价若它们语言相同若它们语言相同. q1q2q3000,111M1注注: 在任何状态在任何状态, 读到读到1后一定会进入状态后一定会进入状态q2. L(M1)=w | w是是0,1串串, 至少含一至少含一个个1, 且最后一个且最

14、后一个1后面含有偶数个后面含有偶数个0 注注: 任何其它语言都不是任何其它语言都不是M1的语言的语言.有限自动机的设计有限自动机的设计(难点难点) 自己即自动机自己即自动机 寻找需要记录的寻找需要记录的关键信息关键信息 设计识别下列语言的设计识别下列语言的DFA: w 0,1* | w从从1开始开始, 以以0结束结束 w 0,1* | w含有子串含有子串1010 w 0,1* | w的倒数第的倒数第2个符号是个符号是1 0k | k是是2或或3的倍数的倍数 有限自动机的设计有限自动机的设计 w 0,1* | w从从1开始开始, 以以0结束结束 =0,1, 根据根据关键信息设计状态关键信息设计状

15、态, 空空, 以以0开始开始, 以以1开始开始以以0结束结束, 以以1开始开始以以1结束结束 空空0开始开始1开始开始0结束结束1开始开始1结束结束0 1 10 10 0,1 有限自动机的设计有限自动机的设计 w 0,1* | w含有子串含有子串1010 =0,1, 关键信息关键信息: , 1, 10, 101, 1010 0,1 1 0 1 1010101010 1 0 1 0 1 有限自动机的设计有限自动机的设计 w 0,1* | w倒数第倒数第2个符号是个符号是1 只需关注最后两个符号只需关注最后两个符号 =0,1, 关键信息关键信息: , 0, 00, 1, 01, 10, 11 关键

16、信息改进关键信息改进: , 1, 10, 111 0 0 1 10110 1 1 1 0 有限自动机的设计有限自动机的设计 0k | k是是2或或3的倍数的倍数 =0, 关键信息关键信息: ,01,02,03,04,05. 记为记为: 0,1,2,3,4,5100 0 0 240 0 30 5有限自动机的设计有限自动机的设计 0k | k是是2或或3的倍数的倍数 =0, 关键信息关键信息: ,01,02,03,04,05, 记记为为: 0,1,2,3,4,5 或或 (0,0), (1,1), (0,2), (1,0), (0,1), (1,2) 0k|k是是2或或3的倍数的倍数 = 0k|k是

17、是2倍数倍数 0k|k是是3的倍数的倍数 0k|k是是2和和3的倍数的倍数 = 0k|k是是2倍数倍数 0k|k是是3的倍数的倍数?(1,1)(0,0)0 0 0 (0,2)(0,1)0 0 (1,0)0 (1,2)100 0 100 0 20 有限自动机的设计有限自动机的设计 0k | k是是2和和3的倍数的倍数 =0, 关键信息关键信息: ,01,02,03,04,05, 记记为为: 0,1,2,3,4,5 或或 (0,0), (1,1), (0,2), (1,0), (0,1), (1,2) 0k|k是是2和和3的倍数的倍数 = 0k|k是是2倍数倍数 0k|k是是3的倍数的倍数(1,1

18、)(0,0)0 0 0 (0,2)(0,1)0 0 (1,0)0 (1,2)100 0 100 0 20 正则语言的并是正则语言正则语言的并是正则语言定理定理: 设设A,B都是都是 上的上的正则语言正则语言, 则则A B也是正则语言也是正则语言. 证明证明: 设设M1=(Q1, , 1,s1,F1)和和M2=(Q2, , 2,s2,F2)是是DFA, 且且 L(M1)=A, L(M2)=B, 令令Q=Q1 Q2, s=(s1,s2), F = F1 Q2 Q1 F2, : QQ, a, r1 Q1, r2 Q2, ( (r1,r2) , a ) = ( 1(r1,a), (r2,a) ), 即

19、对即对i=1,2, 第第i个分量按个分量按Mi的转移函数变化的转移函数变化. 令令M=(Q, , ,s,F), 则则 x ( x L(M) x A B ) 即即 L(M) = A B. 证毕证毕正则语言的交是正则语言正则语言的交是正则语言定理定理: 设设A,B都是都是 上的上的正则语言正则语言, 则则A B也是正则语言也是正则语言. 证明证明: 设设M1=(Q1, , 1,s1,F1)和和M2=(Q2, , 2,s2,F2)是是DFA, 且且 L(M1)=A, L(M2)=B, 令令Q=Q1 Q2, s=(s1,s2), F=F1 F2, : QQ, a, r1 Q1, r2 Q2, ( (r

20、1,r2) , a ) = ( 1(r1,a), (r2,a) ), 即对即对i=1,2, 第第i个分量按个分量按Mi的转移函数变化的转移函数变化. 令令M=(Q, , ,s,F), 则则 x ( x L(M) x A B ) 即即 L(M) = A B. 证毕证毕 证明特点证明特点: 构造性证明构造性证明 正则语言与正则运算正则语言与正则运算如果语言如果语言A被一被一DFA识别识别,则称则称A是是正则语言正则语言算术中算术中, 对象是对象是数数, 操作是操作是运算运算, 如如+ .计算理论中计算理论中, 对象是语言对象是语言, 操作是语言的运算操作是语言的运算.定义定义: 设设A和和B是两个

21、语言是两个语言,定义定义正则运算正则运算 并并,连接连接,星号星号如下如下: 并并: A B = x|x A或或x B 连接连接: A B = xy|x A且且y B 星号星号: A* = x1x2xk|k 0且每个且每个xi A 正则运算举例正则运算举例设字母表设字母表 由由标准的标准的2626个字母组成个字母组成A=good,bad, B=boy,girl, 则则A B= good, bad, boy, girl A B= goodboy, goodgirl, badboy, badgirl A*= , good, bad, goodgood, goodbad, 问题问题:1. 正则语言对

22、于正则运算是否封闭正则语言对于正则运算是否封闭? 2. 如何判断一个语言是正则语言如何判断一个语言是正则语言?非确定型机器非确定型机器(难点难点)前面因为前面因为 : Q Q是一个函数是一个函数, 所以所以 每步存在唯一的方式进入下一状态每步存在唯一的方式进入下一状态 称为称为确定型确定型有限自动机有限自动机(DFA) 现在引入现在引入非确定型非确定型有限自动机有限自动机(NFA) q1q2q3q40,110,10,1 每步可以每步可以0至多种方式进入下一步至多种方式进入下一步 转移箭头上的符号可以是空串转移箭头上的符号可以是空串 , 表示不读任何输入就可以转移过去表示不读任何输入就可以转移过

23、去 非确定型计算非确定型计算q1q2q3q40,110,10,1输入输入01011q1q101q2q1q30q1q31q3q2q1q4q3q2q1q41注注: 若起始状态有射出的若起始状态有射出的 箭头箭头? NFA的计算方式的计算方式Step 1.设读到符号设读到符号s, 对对(每个副本每个副本)机器状态机器状态q, 若若q有多个射出有多个射出s箭头箭头,则机器分裂成多个副本则机器分裂成多个副本. 状态相同的副本视为同一副本状态相同的副本视为同一副本.Step 2. 对每个副本的状态对每个副本的状态,若其上有射出的若其上有射出的 箭头箭头, 则不读任何输入则不读任何输入, 机器分裂出相应副本

24、机器分裂出相应副本.Step 3. 读下一个输入符号读下一个输入符号, 转转step1. 若无输入符号若无输入符号, 计算结束计算结束, 并且并且, 若此时有一个副本处于接受状态若此时有一个副本处于接受状态,则接受则接受, 否则拒绝否则拒绝.NFA的形式定义的形式定义定义定义: NFA是一个是一个5元组元组(Q, , ,s,F),1) Q是是状态集状态集;2) 是字母表是字母表;3) : Q P(Q)是转移函数是转移函数;4) s Q是是起始状态起始状态;5) F Q是是接受状态集接受状态集; 其中其中 = 状态图状态图与与 形式定义形式定义 包含包含相同信息相同信息q1q2q3q40,110

25、,10,1试写出该状态图试写出该状态图 对应的形式定义对应的形式定义 (q1,1) (q2, ) (q2,1) (q1, )= q1,q2 = q3 = = 如何定义如何定义NFA的计算的计算q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA计算的形式定义计算的形式定义设设N=(Q, , ,q0,F)是一台是一台NFA, w是是 上字符串上字符串 称称 N接受接受w, 若若 w能写作能写作w=w1w2wn, wi ,且且 存在存在Q中的状态序列中的状态序列r0,r1,rn, 满足满足 1) r0 = q0; 2) ri+1(ri,

26、 wi+1); 3) rn Fr0w1r1w2r2rn-1wnrn对于输入对于输入, NFA计算的路径可能不唯一计算的路径可能不唯一.NFA计算形式定义举例计算形式定义举例q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA的设计的设计(难点难点) 自己即自动机自己即自动机 寻找需要记录的关键信息寻找需要记录的关键信息 设计识别设计识别0,1上以下语言的上以下语言的NFA: w 0,1* | w从从1开始开始, 以以0结束结束 w 0,1* | w含有子串含有子串1010 w 0,1* | w是倒数第是倒数第2位是位是1 0k |

27、k是是2或或3的倍数的倍数 NFA的设计的设计 w 0,1* | w从从1开始开始, 以以0结束结束 =0,1, 根据根据关键信息设计状态关键信息设计状态, 空空, 以以0开始开始, 以以1开始开始以以1结束结束, 以以1开始以开始以0结束结束 0 空空0开始开始 1开始开始0结束结束 1开始开始1结束结束 0 1 10 10,1 DFA 空空1开始开始 0结束结束1开始开始 0,1 0 1NFA NFA的设计的设计 w 0,1* | w含有子串含有子串1010 =0,1, 关键信息关键信息: 忽略忽略( ), 1, 10, 101, 1010 0,1 1 1 0 0 1010100 1 0

28、1011 1 DFA 1忽略忽略 1 0 0,1 1010100 0,1 1011 NFA NFA的设计的设计 w 0,1* | w倒数第倒数第2个符号是个符号是1 =0,1, 关键信息关键信息: 忽略忽略( ), 1, 1x, 1 1 0 0 10110 1 1 1 0 DFA 1忽略忽略 1 0,1 0,1 1xNFA NFA与与DFA等价等价定理定理: 每个每个NFA都有一台等价的都有一台等价的DFA.q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1N构造构造DFA 关键关键信息信息 每个时刻每个时刻 所有所有副本状态副本状态的集

29、合的集合每个每个NFA都有等价的都有等价的DFAq1q2q3q40,110,10,1编号编号 011q1q1q1, q2, q322q1, q2, q3q1, q33q1, q2, q3, q443q1, q3q1q1, q2, q3, q44*q1, q2, q3, q4q1, q3, q45q1, q2, q3, q45*q1, q3, q4q1, q46q1, q2, q3, q46*q1, q4q1, q4q1, q2, q3, q4以原状态的子集以原状态的子集 为新机器的状态为新机器的状态 每个每个NFA都有等价的都有等价的DFA证明证明: 设设N = (Q1, , 1,s1,F1)

30、是是NFA, /设计设计Q,F, s, 令令 Q = P(Q1), /全体子集全体子集 F = A Q : F1 A , s = E(s1), E(A) = q : r A, r经经0到多个到多个 箭头可达箭头可达q : QQ, a, A Q, ( A, a ) = E( r A 1(r,a) ) M = (Q, , ,s,F), 则则 x ( x L(M) x L(N) ), 即即 L(M) = L(N). 证证毕毕 q1q2q3q40,110,10,1正则运算的封闭性正则运算的封闭性定理定理: 正则语言对正则语言对并并运算封闭运算封闭.定理定理: 正则语言对正则语言对连接连接运算封闭运算封

31、闭. 定理定理: 正则语言对正则语言对星号星号运算封闭运算封闭. 证明证明: 画状态图画状态图.证明若证明若A, B正则正则, 则则A B正则正则DFA: M1=(Q1, , 1,s1,F1), M2=(Q2, , 2,s2,F2), L(M1)=A, L(M2)=B, 令令 Q = Q1 Q2 s 不不交并交并, F = F1 F2 不交并不交并 i=1,2, r Qi, a, (r,a) = i(r,a) (s, ) = s1,s2 M=(Q, , ,s,F), 则则 L(M) = A B. M1 s1M2 s2M1 M2 s M s1s2证明若证明若A, B正则正则, 则则A B正则正则

32、DFA: M1=(Q1, , 1,s1,F1), M2=(Q2, , 2,s2,F2), L(M1)=A, L(M2)=B, 令令 Q = Q1 Q2 不不交并交并, F = F2 , r F1, (r, ) = s2 i=1,2, r Qi, a, (r,a) = i(r,a) M=(Q, , ,s1,F), 则则 L(M) = A B. M1 s1M2 s2M1 M2 M s1s2证明若证明若A正则正则, 则则A*正则正则DFA: M1=(Q1, , 1,s1,F1), L(M1)=A, 令令 Q = Q1 s 不不交并交并, F = F1 s 不交并不交并 r Q1, a, (r,a)

33、= 1(r,a) r F1, (r, ) = s1, (s, ) = s1, M=(Q, , ,s,F), 则则 L(M) = A*. M1 s1M1 s1s M 正则表达式正则表达式定义定义: 称称R是一个正则表达式是一个正则表达式, 若若R是是 1) a, a ; 2) ; 3) ; 4) (R1 R2), R1和和R2是正则表达式是正则表达式; 5) (R1 R2), R1和和R2是正则表达式是正则表达式; 6) (R1*), R1是正则表达式是正则表达式;每个正则表达式每个正则表达式R表示一个语言表示一个语言(?),记为记为L(R).例例: 0*10*, 01 10, ()*, 1*,

34、 *.正则表达式与正则表达式与DFA等价等价定理定理2.3.1: 语言语言A正则正则A可用正则表达式描述可用正则表达式描述. () 若若 语言语言A可用正则表达式描述可用正则表达式描述, 则则 A正则正则. (容易容易)() 若语言若语言A正则正则, 则则A可用正则表达式描述可用正则表达式描述. (困难困难)A有正则表达式有正则表达式A正则正则数学归纳法数学归纳法 R是一个正则表达式是一个正则表达式, 若若R是是 1) a, a 2) 3) 4) (R1 R2) 5) (R1 R2) 6) (R1*)aA正则正则A有正则表达式有正则表达式构造广义非确定有限自动机构造广义非确定有限自动机(GNF

35、A) 非确定有限自动机非确定有限自动机 转移箭头可以用任何正则表达式作标号转移箭头可以用任何正则表达式作标号 证明中的特殊要求证明中的特殊要求: 起始状态无射入箭头起始状态无射入箭头. 唯一接受状态唯一接受状态(无射出箭头无射出箭头).手段手段: 一个一个地去掉中间状态一个一个地去掉中间状态.删除一个中间状态删除一个中间状态设设qrip为待删中间状态为待删中间状态, 对任意两个状态对任意两个状态qi, qj都需要修改箭头标号都需要修改箭头标号 qiqjqripR4 R2 R1 R3 qiqj(R1)(R2)*(R3)(R4) 举例举例: A正则正则A有正则表达式有正则表达式123a a a b

36、 b b 123a a a b b b sac 添起始状态添起始状态s(无无进入箭头进入箭头), 接受状态接受状态ac(无射无射出箭头出箭头), 改掉其它接受状态改掉其它接受状态 s23a ba a ab bb b aa b ac 删状态删状态1 s3a(aa b)* (ba a)(aa b)* (ba a)(aa b)*ab bb a(aa b)*ab b ac删除状态删除状态2 s( (a(aa b)*ab b)(ba a)(aa b)*ab bb)* (ba a)(aa b)*) ) ( a(aa b)*)ac删除状态删除状态3 非正则语言非正则语言B= 0n1n | n 0 C= w

37、| w中中0和和1的个数相等的个数相等 D= w | w中中01和和10的个数相等的个数相等 哪些是哪些是正则语言正则语言?泵引理的等价描述泵引理的等价描述定理定理(泵引理泵引理): 设设A是正则语言是正则语言,则则存在存在p0使得使得 对对任意任意w A, |w| p, 存在存在分割分割w=xyz满足满足 1) 对对任意任意 i 0, xyiz A; 2) |y|0; 3) |xy| p. 若若A是正则是正则语言语言, 则则 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A.若若 p0 w A(|w| p) x,y,z(|y|0, |x

38、y| p, w=xyz) i 0, xyiz A. 则则A非非正则语言正则语言 B = 0n1n | n 0 非正则非正则 p0, 令令w=0p1p, x,y,z(|y|0, |xy| p, w=xyz) 令令i=0, xz = 0p-|y|1p B B非非正则语言正则语言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 则则A非非正则语言正则语言 C = ww | w 0,1* 非正则非正则 p0, 令令w=0p10p1, x,y,z(|y|0, |xy| p, w=xyz) 令令i=0, xz = 0p-|y|10p1 C

39、C非非正则语言正则语言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 则则A非非正则语言正则语言 D = 1k | k=2n, n 0 非正则非正则 p0, 令令w=1k, k=2p+1, x,y,z(|y|0, |xy| p, w=xyz) 令令i=2, 2p+1|xy2z|=k+|y|0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 则则A非非正则语言正则语言泵引理的证明泵引理的证明定理定理(泵引理泵引理): 设设A是正则语言是正则语言,则则存在存在p0使得使得 对对

40、任意任意w A, |w| p, 存在存在分割分割w=xyz满足满足 1) 对对任意任意 k 0, xykz A; 2) |y|0; 3) |xy| p. 证明证明: 令令M=(Q, , ,s,F) 且且 L(M)=A, 令令p=|Q|, 设设 w = w1w2wn A, wi, 且且n p, 则有则有 s=r0w1r1w2r2rn-1wnrn F 由鸽巢原理由鸽巢原理, 存在存在ij p使得使得ri=rj, 令令x=w1wi, y=wi+1wj, z=wj+1wn. 那么对那么对 k 0, xykz A. 本章作业本章作业1.1 下图给出了两台下图给出了两台DFA M1和和M2的状态图。的状态

41、图。 回答下述关于这两台机器的问题。回答下述关于这两台机器的问题。 a. 它们的起始状态是什么它们的起始状态是什么? b. 它们的接受状态集是什么它们的接受状态集是什么? c. 对输入对输入aabb，它们经过的状态序列是什么，它们经过的状态序列是什么? d. 它们接受字符串它们接受字符串aabb吗吗? e.它们接受它们接受字符串字符串 吗吗? 1.6 画出识别下述语言的画出识别下述语言的DFA状态图。字母表为状态图。字母表为0,1 d. w | w的长度不小于的长度不小于3, 并且第并且第3个符号为个符号为0;1.7. 给出下述语言的给出下述语言的NFA，并且符合规定的状态数。，并且符合规定的

42、状态数。 字母表为字母表为0,1 e. 语言语言0*1*0*0, 3个状态。个状态。1.29 使用泵引理证明下述语言不是正则的。使用泵引理证明下述语言不是正则的。 b. A = www | w a,b* 第第4章章 图灵机图灵机1. 图灵机基础图灵机基础1.1 图灵机的定义图灵机的定义1.2 图灵机举例图灵机举例1.3 图灵机的描述图灵机的描述图灵对计算的观察图灵对计算的观察图灵图灵: 计算通常是一个计算通常是一个人人拿着拿着笔笔在在纸纸上进行的上进行的. 他他根据根据 眼睛眼睛看到的纸上符号看到的纸上符号, 脑脑中的若干中的若干法则法则, 指示笔指示笔 在纸上在纸上擦掉或写上擦掉或写上一些符

43、号一些符号, 再再改变他所看到的范围改变他所看到的范围. 继续继续, 直到他认为计算结束直到他认为计算结束. 脑脑:控制器控制器 纸纸:存储带存储带 眼睛和笔眼睛和笔:读写头读写头 法则法则:转移函数转移函数与有限自动机的区别与有限自动机的区别有限自动机有限自动机: 输入带长度有限输入带长度有限 只能只能读读和和右移右移, 不能不能写写和和左移左移 读完输入停机读完输入停机图灵机图灵机(TM)的形式化定义的形式化定义TM是一个是一个7元组元组(Q, , , , q0, qa, qr)1) Q是是状态集状态集.2) 是是输入字母表输入字母表,不包括空白符不包括空白符.3) 是是带字母表带字母表,

44、其中其中, .4) : QQL,R是是转移函数转移函数.5) q0 Q是是起始起始状态状态. 6) qa Q是是接受接受状态状态. 7) qr Q是是拒绝拒绝状态状态, qa qr .图灵机的初始化图灵机的初始化设设M=(Q, , , , q0, qa, qr), w=w1wnn, 输入带输入带: 将输入串将输入串w放在最左端放在最左端n格中格中, 带子其余部分补充空格带子其余部分补充空格. 读写头读写头: 指向工作带最左端指向工作带最左端.例例:设输入串为设输入串为0101, 则其初始形态为则其初始形态为图灵机的运行图灵机的运行 图灵机根据转移函数运行图灵机根据转移函数运行. 例例:设输入串

45、为设输入串为0101, 且且 (q0,0)=( p,#,R), 则有则有 注注: 若要在最左端左移若要在最左端左移, 读写头保持不动读写头保持不动. (q0,0)=( p,#,R)的状态图表示的状态图表示:简记为简记为判定器与语言分类判定器与语言分类 图灵机运行的三种结果图灵机运行的三种结果 1. 若若TM进入进入接受状态接受状态,则停机且接受输入则停机且接受输入, 2. 若若TM进入进入拒绝状态拒绝状态,则停机且拒绝输入则停机且拒绝输入, 3. 否则否则TM一直运行一直运行,不停机不停机. 定义定义: 称图灵机称图灵机M为为判定器判定器, 若若M对所有输入都停机对所有输入都停机. 定义不同语

46、言类定义不同语言类: 图灵图灵可判定可判定语言语言: 某个判定器的语言某个判定器的语言(也称也称递归语言递归语言) 图灵图灵可识别可识别语言语言: 某个图灵机的语言某个图灵机的语言, 也称为也称为递归可枚举语言递归可枚举语言 q1 q2 0L 1#, R 图灵机的格局图灵机的格局 描述图灵机运行的每一步需要如下信息描述图灵机运行的每一步需要如下信息: 控制器的控制器的状态状态; 存储带上存储带上字符串字符串; 读写头的读写头的位置位置. 定义定义: 对于图灵机对于图灵机M=(Q, , , , q0, qa, qr), 设设q Q, u,v*, 则则格局格局 uqv 表示表示 1) 当前控制器当

47、前控制器状态状态为为q ; 2) 存储带存储带上字符串为上字符串为uv(其余为空格其余为空格); 3) 读写头读写头指向指向v的第一个符号的第一个符号. 起始格局起始格局, 接受格局接受格局, 拒绝格局拒绝格局.q0 qa 0L 1R q0 qa 0L 1R qr |_|R 格局演化举例格局演化举例 s qa 0L 1R qr |_|R s 0 1 s 0 1 循环循环 s 1 0 1 qa 0 接受接受 s _ _ _ qr _ 拒绝拒绝 图灵机计算的形式定义图灵机计算的形式定义称图灵机称图灵机M接受接受字符串字符串w,若存在格局序列若存在格局序列C1,C2,Ck使得使得 1) C1是是M的

48、起始格局的起始格局q0w; 2) Ci产生产生Ci+1, i=1,k-1; 3) Ck是是M的接受格局的接受格局. M的的语言语言: M接受的所有字符串的集合接受的所有字符串的集合, 记为记为L(M).1. 图灵机基础图灵机基础1.1 图灵机的定义图灵机的定义1.2 图灵机举例图灵机举例1.3 图灵机的描述图灵机的描述图灵机举例图灵机举例 =0,1, A=0w1 : w* 正则语言正则语言 B=0n1n : n 0 上下文无关语言上下文无关语言 =0, C=0k:k=2n,n 0 图灵图灵可判定可判定语言语言 M=“对于输入串对于输入串w, 1) 若若w= , 则拒绝则拒绝. 2) 若只有若只

49、有1个个0,则接受则接受. 3) 若有奇数个若有奇数个0,则拒绝则拒绝. 4) 隔一个隔一个0,删一个删一个0. 转转(2).”L(M)=C, 即即M识别识别C.状态图状态图M=“对于输入对于输入w,1) 若若w= , 则拒绝则拒绝.2) 若只有若只有1个个0,则接受则接受.3) 若有奇数个若有奇数个0,则拒绝则拒绝.4) 隔一个隔一个0,删一个删一个0. 转转(2).”Rqrq0状态图状态图q0Rqrq10$,RRqaq20 x,RM=“对于输入对于输入w,1) 若若w= , 则拒绝则拒绝.2) 若只有若只有1个个0,则接受则接受.3) 若有奇数个若有奇数个0,则拒绝则拒绝.4) 隔一个隔一

50、个0,删一个删一个0. 转转(2).”状态图状态图q0Rqrq10$,RRqaq20 x,Rq30R0 x,RRM=“对于输入对于输入w,1) 若若w= , 则拒绝则拒绝.2) 若只有若只有1个个0,则接受则接受.3) 若有奇数个若有奇数个0,则拒绝则拒绝.4) 隔一个隔一个0,删一个删一个0. 转转(2).”状态图状态图q0Rqrq10$,RRqaq20 x,Rq30R0 x,RRq4L0LxL $RM=“对于输入对于输入w,1) 若若w= , 则拒绝则拒绝.2) 若只有若只有1个个0,则接受则接受.3) 若有奇数个若有奇数个0,则拒绝则拒绝.4) 隔一个隔一个0,删一个删一个0. 转转(2

51、).”状态图状态图q30R0 x,RRq0Rqrq10$,RRqaq20 x,Rq4L0LxL$RxRxRxRM=“对于输入对于输入w,1) 若若w= , 则拒绝则拒绝.2) 若只有若只有1个个0,则接受则接受.3) 若有奇数个若有奇数个0,则拒绝则拒绝.4) 隔一个隔一个0,删一个删一个0. 转转(2).”各种语言类的包含关系各种语言类的包含关系正则语言正则语言 上下文无关语言上下文无关语言 可判定语言可判定语言 图灵可识别语言图灵可识别语言 P( *)?图灵机的描述图灵机的描述(1) 形式水平的描述形式水平的描述(状态图或转移函数状态图或转移函数)(2) 实现水平的描述实现水平的描述(读写头的移动读写头的移动,改写改写)(3) 高水平描述高水平描述(使用日常语言使用日常语言)用带引号的文字段来表示图灵机用带引号的文