计算理论-计算模型-2016

教材:[1][王]王晓东,计算机算法设计与分析(第4版),电子工业.[2][S]唐常杰等译,Sipser著,计算理论导引,机械工业.参考资料:[3][C]潘金贵等译,Cormen等著,算法导论,机械工业.[4][M]黄林鹏等译,Manber著,算法引论-一种创造性方法,电子.[5][刘]刘汝佳等,算法艺术与信息学竞赛,清华大学.[6][L]Lewis等著,计算理论基础,清华大学.计算理论与算法分析设计刘庆晖计算理论第一部分计算模型[S]第1章有限自动机第2章上下文无关语言（不考）第3章图灵机第1章有限自动机从字符串匹配问题说起•输入:两个字符串x,y,(|x|=n,|y|=m)•输出:所有y在x中出现的起点位置•例:x=abaabababbabababbababaa,y=ababbababaa•输出13•直接法:以每个位置为起点对比一遍y.O((n-m+1)m)•观察改进方法x:abaabababbabababbababaay:|ababbababaay:|ababbababaay:|ababbababaay:|ababbababaa构造状态和转移函数y=ababbababaa01a2ab3aba4abab5ababb11ababbababaa10ababbababa9ababbabab8ababbaba7ababbab6ababbaaaaaaabbbbbbbbbaaaaabbaf:{0:11}{a,b}{0:11}x:abaabababbabababbababaa012312343456789104567891011输出23-10=13b输入x,y,串匹配的有限自动机算法符号集,m=Length(y),计算转移函数,Yi=y1y2…yi.1.对q=0:m2.对每个符号a,3.k=min{m,q+1}4.当Yk不是Yqa的后缀,k--5.f(q,a)=k={a,b}f(0,a)=1,f(0,b)=0,abab|b,f(4,b)=5,abab|a,f(4,a)=3,匹配算法1.n=Length(x),q=02.对i=1:n3.q=f(q,x[i]),4.若q=m,打印i-m+1字符串匹配算法算法预处理时间匹配时间朴素0O((n-m+1)m)自动机O(m||)(n)Knuth-Morris-Pratt(m)(n)其中是字母表字符串与语言字母表:任意一个有限集.常用记号,.符号:字母表中的元素字符串:字母表中符号组成的有限序列如asdf,通俗地说即单词串的长度|·|,例:|abcde|=5串的连接*,例:(abc)*(de)=abcde串的反转R,例:(abcde)R=edcba空词:记为,长度为0语言:给定字母表上一些字符串的集合*,语言,字典序取字母表={0,1},上的语言举例:A={0,00,0000},B={0,00,01,000,001,…}上所有有限长串记为*.上的任一语言都是*的子集.*(字典序):,0,1,00,01,10,11,000,…上所有无限长串记为N.上的语言与N一一对应.*0100011011000001…B00001000001…f(B)010110011…等势,可数,不可数等势:若两集合间存在一一对应,则称它们等势可数:若集合与有限集或与自然数集等势或者说集合元素可以按次序列出不可数:若集合不是可数的或者说集合元素不能按次序列出*可数N不可数(与[0,1]中全体实数一一对应)上的全体语言不可数决定性问题与语言一一对应决定性问题(DicisionProb):只需回答是与否的问题“一数是否是偶数”--------------{以0结尾的01串}“串0,1个数是否相等”------{0,1个数相等的01串}“串长度是否是2的幂次”----------------{02n:n0}“图是否连通”------------------{G|G是连通图}其中G是图G编码成的字符串.给定有限字母表,•每个输入是一个串,任意串都可以是输入串•一个决定性问题是满足某性质的串的集合(语言)•当机器从简单到复杂,能解决的问题也变复杂确定型有限(穷)自动机的形式定义定义:有限自动机是一个5元组(Q,,,s,F),1)Q是有限集,称为状态集;2)是有限集,称为字母表;3):QQ是转移函数;4)sQ是起始状态;5)FQ是接受状态集;•状态图等价于形式定义Q={q1,q2,q3},状态集={0,1},字母表s=q1,起始状态F={q2}接受状态集01q1q1q2q2q3q2q3q2q2M1q1q2q3000,111图灵对计算的观察图灵:计算通常是一个人拿着笔在纸上进行的.他根据眼睛看到的纸上符号,脑中的若干法则,指示笔在纸上擦掉或写上一些符号,再改变他所看到的范围.继续,直到他认为计算结束.脑:控制器纸:存储带眼睛和笔:读写头法则:转移函数有限自动机是简化的图灵机1101q1状态:q1,q2,q3起始状态q1接受状态q2转移:箭头运行:从起始状态开始沿转移箭头进行.输出:输入读完处于接受状态则接受,否则拒绝.接受:1,11,100,101,1101,…拒绝:,0,10,110,1010,…M1是读写头不能改写,且只能右移的图灵机q1q2q3000,111DFA计算的形式定义设M=(Q,,,s,F)是一个DFA,w=w1w2…wn是字母表上的一个字符串.若存在Q中的状态序列r0,r1,…,rn,满足1)r0=s;2)(ri,wi+1)=ri+1;3)rnF则M接受w.sw1r1w2r2rn-1wnrn…q1q2q3000,111有限自动机的语言:正则语言对有限自动机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,且最后一个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},根据关键信息设计状态,空,以0开始,以1开始以0结束,以1开始以1结束空0开始1开始0结束1开始1结束0110100,1有限自动机的设计{w{0,1}*|w含有子串1010}={0,1},关键信息:,1,10,101,10100,1101101010101010101有限自动机的设计{w{0,1}*|w倒数第2个符号是1}只需关注最后两个符号={0,1},关键信息:,0,00,1,01,10,11关键信息改进:,1,10,111001101101110有限自动机的设计{0k|k是2或3的倍数}={0},关键信息:,01,02,03,04,05.记为:0,1,2,3,4,5100002400305有限自动机的设计{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的倍数}{0k|k是2和3的倍数}={0k|k是2倍数}{0k|k是3的倍数}?(1,1)(0,0)000(0,2)(0,1)00(1,0)0(1,2)1000100020有限自动机的设计{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)(0,0)000(0,2)(0,1)00(1,0)0(1,2)1000100020正则语言的并是正则语言定理:设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,:QQ,a,r1Q1,r2Q2,((r1,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,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,:QQ,a,r1Q1,r2Q2,((r1,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是两个语言,定义正则运算并,连接,星号如下:并:AB={x|xA或xB}连接:AB={xy|xA且yB}星号:A*={x1x2…xk|k0且每个xiA}正则运算举例设字母表由标准的26个字母组成A={good,bad},B={boy,girl},则AB={good,bad,boy,girl}AB={goodboy,goodgirl,badboy,badgirl}A*={,good,bad,goodgood,goodbad,…}问题:1.正则语言对于正则运算是否封闭?2.如何判断一个语言是正则语言?非确定型机器(难点)前面因为:QQ是一个函数,所以•每步存在唯一的方式进入下一状态•称为确定型有限自动机(DFA)现在引入非确定型有限自动机(NFA)q1q2q3q40,110,10,1•每步可以0至多种方式进入下一步•转移箭头上的符号可以是空串,表示不读任何输入就可以转移过去非确定型计算q1q2q3q40,110,10,1输入01011q1q101q2q1q3×0q1q31q3q2q1q4q3q2q1×q41注:若起始状态有射出的箭头?NFA的计算方式Step1.设读到符号s,对(每个副本)机器状态q,若q有多个射出s箭头,则机器分裂成多个副本.状态相同的副本视为同一副本.Step2.对每个副本的状态,若其上有射出的箭头,则不读任何输入,机器分裂出相应副本.Step3.读下一个输入符号,转step1.若无输入符号,计算结束,并且,若此时有一个副本处于接受状态,则接受,否则拒绝.NFA的形式定义定义:NFA是一个5元组(Q,,,s,F),1)Q是状态集;2)是字母表;3):QP(Q)是转移函数;4)sQ是起始状态;5)FQ是接受状态集;其中={}状态图与形式定义包含相同信息q1q2q3q40,110,10,1试写出该状态图对应的形式定义(q1,1)(q2,)(q2,1)(q1,)={q1,q2}={q3}==如何定义NFA的计算q1q101q3q2q1×0q1q31q3q2q1q3q2q1×q4q41q1q2q3q40,110,10,1NNFA计算的形式定