形式语言与自动机理论（1）----基础介绍.pdf

形式语⾔与⾃动机理论（1）基础介绍

计算理论

计算：以机械⽽有效的⽅式，获取问题答案的过程。

计算理论的中⼼，逐渐从数学转到计算机科学。

计算理论和计算机科学所关⼼的核⼼问题是

计算机的基本能⼒和限制是什么？

包含两个内容，分别对应计算理论的两个重要研究⽅向。

⼀个是可计算性理论，⼀个是计算复杂性理论。

形式语⾔与⾃动机理论（本专栏）正是这两个⽅向的理论基础。

究竟哪些问题，可通过计算解决？—可计算性理论

计算作为⼀种能⼒，它是否有边界？是不是任何问题都可以通过计算来解决。

如果是，它会是什么样的？

如果不是，哪些问题可以，哪些问题不可以？为什么不可以？

为了能够严谨的研究机械⽽有效的计算过程，我们需要严格定义的概念去描述，需要严谨的计算模型去分析它。

这些模型，就是我们要学习的⾃动机理论。这些概念就是算法。

⼀个问题如果有了具体的算法之后，解决起来就不再需要太多的⼈的智慧，只需要根据算法的步骤，机械的计算就可以了。

⽐如，两个整数的最⼤公约数，使⽤欧⼏⾥得算法。

20世纪30年，数理逻辑学家在研究可计算的整数函数时，利⽤图灵机和lambda演算等计算模型，⾸次将算法的概念形式化。

从那以后，⼈们才能利⽤数理逻辑的⽅法，研究计算的本质。并且发现，计算也不是万能的。

确实存在⼀些问题，⽆法通过计算解决。或者说，这些问题是不存在算法的。（最后会给出这样的问题并给出证明）

解决可计算问题，究竟需要多少资源？—计算复杂性理论

利⽤计算去解决可计算问题，需要多少资源

计算⼀个问题需要消耗的计算时间和占⽤的存储空间会达到什么样的程度？

如果⼀个问题⽆论使⽤什么算法，求解过程都需要相当多的资源，那其中的原因是什么？究竟是什么造成⼀些问题很难计算。⽽另⼀些却很

容易，虽然其中原因未知，但是在分析各种有效计算模型的过程中。⼈们发现⼀个按照难度，给问题的分类的完美体系，如果元素周期表。

对化学元素性质分类⼀样。

由这个体系，我们可以将未知的体系按照难易程度分类，再选择使⽤什么样的对策来解决。

⽬前，计算复杂性理论的研究依然是计算机科学领域的研究热点，但是已经超出了本课程的内容。我们不会涉及太多。希望本课程为⼤家研

究计算复杂性做出⼀点⼉基础积累。

因为为了研究可计算性和计算复杂性。需要使⽤和构造什么样的计算模型？恰恰就是形式语⾔与⾃动机理论的主要内容

这些模型都是⾼度抽象化的计算装置。简单明确但功能强⼤。

不但便于在理论分析中便于理论推导和证明，在需要实际问题中也有很多直接的应⽤

为了研究计算，要使⽤哪些计算模型？形式语⾔与⾃动机理论

什么是⾃动机理论？

以这些抽象的计算装置为研究对象，分析这些装置，所能解决问题的理论。

最重要的图灵机，具有现在所有实际的计算机的所有能⼒，是计算机的理论模型。

区分了那些问题是可以计算，那些问题是不能计算。

在多项式时间内，图灵机以确定的⽅式和⾮确定的⽅式，所解决的问题的问题类是否相同，即p是否等于np，依然是计算机中悬⽽未决的问

题。

⽽且其他的稍简单的模型，⽐如说，有穷⾃动机。在数字电路，通信协议等实际问题中，有重要的应⽤。

⽂法，下推⾃动机在计算机程序设计语⾔的设计，和编译器的实现上，发挥了重要作⽤

什么是形式语⾔？

如果⾃动机是研究计算的模型，那么语⾔就是研究计算的问题或实例。

形式语⾔：经数学定义的语⾔。

以数学的⽅法，从解决问题的⾓度，研究计算，⾸先需要以数学的⽅法来描述问题。这种描述就是形式语⾔。

使⽤语⾔这个概念，似乎有些奇怪。但其实和我们的常识⼀致。

可以以这样的观点，理解语⾔的构成。

语⾔简单的由字符，单词，句⼦，语法。

如，⾃然语⾔中的英⽂和中⽂等。

⽽只要有严谨的数学定义，就可以称为形式语⾔。⽐如化学分⼦式，程序设计语⾔等。甚⾄是没有任何含义的语⾔。

定义⼀个语⾔，⾸先要确定基本的字符有哪些。再确定构成单词和句⼦的计算规则。单词和句⼦在形式语⾔中，我们都认为是字符串。最关

键的是如果描述这个基本规则。在形式语⾔与⾃动机理论中，这种描述实际上就是⾃动机。

所有形式语⾔和⾃动机是密不可分的。

⼀⽅⾯⾃动机以语⾔为处理对象，另⼀⽅⾯，语⾔是以⾃动机形式定义的。

基础知识

基本概念

1.字母表：符号（字符）的⾮空有穷集

∑={0,1}表⽰⼆进制数的字母表

1

∑2={a,b,c,d,…z}英语字母组成的语⾔

∑3={x|x是⼀个汉字}汉语所组成的⼀个语⾔

2.字符串：由某字母表中符号组成的有穷序列

若∑={0，1}，那么0,1,00，111001为