您好，欢迎访问三一刀客
当前位置：首页 > 行业资料 > 其它行业文档 > 计算理论-计算模型-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=ababbababaa01a2ab3aba4abab5ababb11ababbababaa10ababbababa9ababbabab8ababbaba7ababbab6ababbaaaaaaabbbbbbbbbaaaaabbaf:{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…B00001000001…f(B)010110011…等势,可数,不可数等势:若两集合间存在一一对应,则称它们等势可数:若集合与有限集或与自然数集等势或者说集合元素可以按次序列出不可数:若集合不是可数的或者说集合元素不能按次序列出*可数N不可数(与[0,1]中全体实数一一对应)上的全体语言不可数决定性问题与语言一一对应决定性问题(DicisionProb):只需回答是与否的问题“一数是否是偶数”--------------{以0结尾的01串}“串0,1个数是否相等”------{0,1个数相等的01串}“串长度是否是2的幂次”----------------{02n:n0}“图是否连通”------------------{G|G是连通图}其中G是图G编码成的字符串.给定有限字母表,•每个输入是一个串,任意串都可以是输入串•一个决定性问题是满足某性质的串的集合(语言)•当机器从简单到复杂,能解决的问题也变复杂确定型有限(穷)自动机的形式定义定义:有限自动机是一个5元组(Q,,,s,F),1)Q是有限集,称为状态集;2)是有限集,称为字母表;3):QQ是转移函数;4)sQ是起始状态;5)FQ是接受状态集;•状态图等价于形式定义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)rnF则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,1101101010101010101有限自动机的设计{w{0,1}*|w倒数第2个符号是1}只需关注最后两个符号={0,1},关键信息:,0,00,1,01,10,11关键信息改进:,1,10,111001101101110有限自动机的设计{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都是上的正则语言,则AB也是正则语言.证明:设M1=(Q1,,1,s1,F1)和M2=(Q2,,2,s2,F2)是DFA,且L(M1)=A,L(M2)=B,令Q=Q1Q2,s=(s1,s2),F=F1Q2Q1F2,:QQ,a,r1Q1,r2Q2,((r1,r2),a)=(1(r1,a),(r2,a)),即对i=1,2,第i个分量按Mi的转移函数变化.令M=(Q,,,s,F),则x(xL(M)xAB)即L(M)=AB.证毕正则语言的交是正则语言定理:设A,B都是上的正则语言,则AB也是正则语言.证明:设M1=(Q1,,1,s1,F1)和M2=(Q2,,2,s2,F2)是DFA,且L(M1)=A,L(M2)=B,令Q=Q1Q2,s=(s1,s2),F=F1F2,:QQ,a,r1Q1,r2Q2,((r1,r2),a)=(1(r1,a),(r2,a)),即对i=1,2,第i个分量按Mi的转移函数变化.令M=(Q,,,s,F),则x(xL(M)xAB)即L(M)=AB.证毕证明特点:构造性证明正则语言与正则运算如果语言A被一DFA识别,则称A是正则语言算术中,对象是数,操作是运算,如+.计算理论中,对象是语言,操作是语言的运算.定义:设A和B是两个语言,定义正则运算并,连接,星号如下:并:AB={x|xA或xB}连接:AB={xy|xA且yB}星号:A*={x1x2…xk|k0且每个xiA}正则运算举例设字母表由标准的26个字母组成A={good,bad},B={boy,girl},则AB={good,bad,boy,girl}AB={goodboy,goodgirl,badboy,badgirl}A*={,good,bad,goodgood,goodbad,…}问题:1.正则语言对于正则运算是否封闭?2.如何判断一个语言是正则语言?非确定型机器(难点)前面因为:QQ是一个函数,所以•每步存在唯一的方式进入下一状态•称为确定型有限自动机(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):QP(Q)是转移函数;4)sQ是起始状态;5)FQ是接受状态集;其中={}状态图与形式定义包含相同信息q1q2q3q40,110,10,1试写出该状态图对应的形式定义(q1,1)(q2,)(q2,1)(q1,)={q1,q2}={q3}==如何定义NFA的计算q1q101q3q2q1×0q1q31q3q2q1q3q2q1×q4q41q1q2q3q40,110,10,1NNFA计算的形式定
三一刀客所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
扫描二维码
lung1421
本文标题：计算理论-计算模型-2016
链接地址：https://www.111doc.com/doc-1654649 .html