资源描述：
《计算引论论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算引论36060203柴巧珍浅谈计算模型计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论，通俗说来，就是研究用计算机求解问题的难易程度。它有两个度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类:常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(logn)、线形阶0(n)、线形对数阶0(nlogn)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n^k)、指
2、数阶0(2^n)。显然，时间复杂度为指数阶0(2^n)的算法效率极低，当n值稍大时就无法应用。不言而喻，对于任意给定的问题。设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标。而可计算性（calculability）是指一个实际问题是否可以使用计算机来解决．从广义上讲如“帮我洗衣服”这样的问题是无法用计算机来解决的（至少在目前）．而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决．事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“第8页共8页计算引论
3、36060203柴巧珍可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题．分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题集中．语言可以看作是一个非空的字母集合，自动机则是一种控制结构，是抽象的计算机模型。形式语言和自动机密切相关。图灵机——0型语言（递归可枚举）——无限制文法；下面我再说说看书时所得的关于其他自动机的内容。一、正则文法——正则语言——有穷
4、自动机（DFA、NFA）1、正则语言与正则表达式本质上相同：定理1.1：r是正则表达式，则一定存在某个带ε_转移的NFA接受r表示的语言L（r），因此，L（r）是正则语言。定理1.2：设L是正则语言，那么总存在正则表达式r，使得L＝L（r）。L是正则语言→L可被某个NFA接受→通过删除NFA节点的方法写出r2、右线性文法和左线性文法都是正则文法第8页共8页计算引论36060203柴巧珍也就是说，在正则文法中，任何产生式的右侧至多有一个非终结符（变量），且此非终结符一定在产生式右侧的最右端或最左端。如：A→xBA→x（右线性文法）或A→BxA→x（左线性文法）3、L是正则语言，当且
5、仅当存在正则文法G，满足L＝L（G）。4、DFA、NFA的定义定义一个DFAM是一个5元组M=(Q,∑,δ,q0,F)其中，Q：有限的状态集合（非空）∑：用穷的字母表δ：转移函数q0∈Q：初始状态FQ：终态集合δ(q,a)=p,扩充转移函数，就得到了NFAM。第8页共8页计算引论36060203柴巧珍5、定理1.3设L为某个NFAM接受，则存在一个DFAM接受L。——DFA和NFA的等价性6、识别非正则语言——泵引理泵引理设L是正则语言，那么一定存在一个只与L相关的正整常数m，使得对任意w∈L且
6、w
7、≥m，都可以分解成：w=xyz其中，
8、xy
9、≤m
10、y
11、≥1并且，对所有的i＝0,
12、1,2……,都有wi＝xyiz∈L。7、正则语言对并、交、补、连接、星闭包、代换（含同态、逆同态）运算都是封闭的。8、构造正则文法、DFA以及正则语言的判断例题见作业本。二、上下文无关文法CFG——上下文无关语言CFL——非确定型下推自动机（NPDA或PDA）1、定义：文法G＝（V,T,S,P）称为上下文无关文法CFG(context-freegrammar)，如果P中的产生式具有形式A→x其中，A∈V,x∈(V∪T)*。L是上下文无关语言CFL，当且仅当存在一个CFG，满足L=L(G)。对任何上下文无关语言CFL，都存在一个NPDAM第8页共8页计算引论36060203柴巧珍使
13、得L＝L(M)。NPDA（或PDA）的定义：DPDA的定义：2、识别非上下文无关语言CFL——泵引理泵引理设L是上下文无关语言CFL，那么一定存在一个只与L相关的正整常数m，使得对任意w∈L且
14、w
15、≥m，都可以分解成：w=uvxyz第8页共8页计算引论36060203柴巧珍其中，
16、vxy
17、≤m
18、vy
19、≥1并且，对所有的i＝0,1,2……,都有wi＝uvixyiz∈L。3、上下文无关语言对并、连接、闭包运算封闭，对交、补运算不封闭。4、设L1是一个CFL，L2是一个正则语言，则L1
