形式语言与自动机课件

1、形式语言与自动机理论为什么学？学什么？怎么学？ 计算机科学与技术专业人员的4种基本专业能力：（1）计算思维能力；（2）算法的设计与分析能力；（3）程序设计和实现能力；（4）计算机软硬件系统的认知、分析、设计与应用能力。引言 培养学生的形式化描述和抽象思维能力，了解和掌握 “问题形式化描述自动化（计算机化）” 的解题思路。“什么能被有效自动化”计算学科之主题计算机科学与技术专业人员的4种基本专业能力：（1）计算思维能力；（2）算法的设计与分析能力；（3）程序设计和实现能力；（4）计算机软硬件系统的认知、分析、设计与应用能力。引言 一、课程性质 Formal Languages and Autom

2、ata Theory The Fundamental of Computing Theory Introduction to the Theory of Computation二、课程特点： 抽象和形式化； 既有严格的理论证明； 又有很强的构造性； 包含一些基本模型的建立、性质等。三、课程主要内容 1、语言理论 2、自动机理论 3、可计算性基本理论本课程内容属于计算机科学的基本理论自然语言：人与人之间交流的基本手段。 如：汉语、英语、俄语、法语、等人工语言：主要用于人与计算机之间的交流。 如：程序设计语言 （也有例外，如世界语）语言理论： 语言自然语言人工语言形式语言：研究自然语言和人工语言都

3、必须遵循的一般规律 研究字符串集合及其性质的学科Chomsky文法体系：4种类型的文法及其产生的语言 正规文法RG正规语言RL； 上下文无关文法CFG上下文无关语言CFL； 上下文有关文法CSG上下文有关语言CSL； 无限制文法URG递归可枚举语言r.e.。计算机处理的主要对象自动机理论： 语言（形式语言）识别器 4种类型自动机与4类文法相对应 有限自动机FA RL RG 下推自动机PDA CFL CFG 线性界限自动机LBACSL CSG 图灵机TMr.e.URG 语言的运算及性质证明。可计算性基本理论： 判定问题与不可判定性形式语言（Formal Language）课程特点： 抽象和形式化

4、； 既有严格的理论证明； 又有很强的构造性； 包含一些基本模型的建立、性质等。四、教材与教学参考书教材：吴哲辉形式语言与自动机理论，北京，机械工业出版社，2007年4月，20。主要参考书：J.Hopcroft,J.D.Ullman,Introduction to Automata Theory, Language and ComputationCalifornia, Addison-Wesley Publishing Company, 1979.（2002年清华，影印版） 2 刘田 译，自动机理论、语言和计算导论，机械工业出版社，2005， 39。 3蒋宗礼，形式语言与自动机理论，清华大学出版

5、社，2003， 28。（另带习题解答）另外的预备知识 1、关于集合及运算（并、交、差、有限集、无限集、 幂集、笛卡尔乘积等） 2、关于二元关系（三歧性、等价关系、等价类等） 3、关于常用证明方法（演绎推导、反证、例证、数学归 纳、构造证明等） 4、树和图的应用第1章 语言及其表示 语言某个字母表上满足某些特定条件的字符串的集合1.1字母表、串和语言字母表（Alphabet）：由字符组成的非空有限集，通常用表示。 空 集 不能作为字母表 无限集 也不能作为字母表自然语言人工语言例如：英语的字母表=a, b, , y, z, A, B, Y,Z,，, 。, “，”,；=0,1也可以看作一个字母表，

6、一个二进制数可看作这个字母表上的一个字符串。串（String）：由某字符表上的字符组成的有限序列。例如：0100101 是字母表=0,1上的一个串。串的长度：一个串中字符的个数。 设x为字母表上的一个串，x的长度记为|x|。例如 |0100101|=7空串：不含任何字符的串，即长度为零的串，记为 。前缀、后缀、子串串的逆：把一个串中的字符逆向顺序重新排列得到的另一个串 设x为一个串，x的逆记为xR 例： 若x=0100101 则xR=1010010 易知 1）|xR|=|x| 2）空串的逆仍是空串：R=串的连接（concatenation）运算串的幂运算 串的连接运算又称为串的乘法运算。类似于

7、从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。 设x为一个串，则定义 代数系统 间的同构关系语言（Language）语言几种基本运算对语言的理解句型、推导与句子文法所产生的语言举例举例1.3 语言识别器 语言识别器同文法一样，都是对（可能为无限集的）语言提供有限表示的一种方式。语言识别器也称为自动机。 如果说文法是从产生语言的角度来表示语言，那么自动机是从识别语言的角度来表示语言。 自动机的结构可以大致表示成下图的形式。辅助存储器a1a2an有限状态控制器图1.1 自动机的大致结构即自动机由部分组成：有限状态器、输入带和辅助存储器。有的自动机可以没有辅助存储器。 输入带

8、可以有限长或无限长，有限状态控制器对输入带可以只允许读，不允许写，也可以读和写。 根据不同的规定，自动机可以分为几种类型。第 2 章 正规表达式、正规文法与有限自动机 正规语言是Chomsky文法体系中最简单的一类语言。产生这种语言的文法是正规文法，识别这类语言的是有限自动机。此外，这类语言也可以用正规表达式表示。因此，正规语言也叫正规集。 2.2 正规文法和正规语言 正规文法是Chomsky文法体系中最简单的一种文法。说它简单，是指它的产生式的形式简单，因为产生式集是一个文法的核心。 定义和例子 2.3 有限自动机（finite automaton,FA） 2.8 正规表达式和有限自动机的应

9、用 许多控制系统的控制部件都是时序电路。对于一个控制系统，可以把它的时序电路转化为一个带输出的有限自动机来分析系统的运行。反过来，要设计一个复杂的控制系统，可以先设计出能够实现所要求得有限自动机，然后把它转化为时序电路。 本节主要讨论两个问题：1）怎样用一个有限自动机描述一个时序电路？2）怎样用一个时序电路来实现一个有限自动机。用有限自动机描述时序电路 我们对前面给出的时序电路的轮廓模型来加以说明。由于x1, ，xn是一组输入信号，所以有限自动机的输入字母表为 =0，1ny1, ,yk可以看作是系统的当前状态，加工后得到的w1,w2, ,wk，则是系统的下一状态，从而系统的状态集为 Q=0，1

10、kz1, ,z2是系统的输出信号，所以输出字母表为 =0，1m这样，我们就得到一个带输出的有限自动机 用时序电路实现有限自动机 把M1中的状态看作为k位逻辑值，输入字符看作为n位逻辑值，输出字母看作是m位逻辑值，这样状态转换函数和输出函数都可以用逻辑表达式表示，最后，就可以用逻辑电路（时序电路）来实现这些逻辑公式。 下面通过一个例子来说明用时序电路实现带输出的有限自动机的全过程。s1s2xu1u2t1t200000010011000010010001100111000000101101011001101111000第3章 上下文无关文法与下推自动机 3.1 上下文无关文法（context-fr

11、ee grammer） 3.2 推导树（derivation tree） 3.3 上下文无关文法的化简 3.4 乔姆斯基范式和格雷巴赫范式 3.5 上下文无关语言的固有歧义性第 4 章 图灵机 4.2 图灵机的基本概念 4.3 图灵机用于计算整函数 4.5 变型图灵机 除了定义4.1中给出的图灵机的基本模型以外，图灵机还可以有许多变型模型。这些模型的描述能力（接受语言的能力或计算函数的能力）同定义4.1的基本模型是等价的。下面列举几种：双向无限带图灵机 这种图灵机的读写带是向右、向左两个方向无限延伸的。多带图灵机 这种图灵机有多条读写带，每条读写带上都有读写头。在一个状态下，图灵机要把各条带上

12、当前格的信息都扫描到后，才能决定动作函数的值。不确定的图灵机 这种图灵机在一个状态下，扫描到一个字符，可以有多种动作，其原理与NFA和NPDA类似。脱线图灵机 这种图灵机专门用一条带存放输入串，不能在在这条带上写。图灵机另有工作带，把输入带上的信息复制到工作带后，在工作带上可以读和写 4.6 邱奇图灵论题 自从歌德尔不完全性定理提出以后，计算科学家们认识到存在不可计算的函数（不可判定的问题）。那么，什么样的函数是可计算的，哪些函数是不可计算的，有没有一个鉴别标准呢？不久，图灵、邱奇和克林尼克分别提出图灵机、验算和递归函数等不同的计算模型。而且邱奇和图灵都宣称他们提出的模型是可计算性的标准。由于

13、随后证明了这三种模型的计算能力是等价的，因此，只要其中一种可以作为可计算性的衡量标准，另外两种也就可以作为可计算性的衡量标准。因此，人们把邱奇和图灵的断言合称为邱奇图灵论题。 之所以称为论题（hypohtesis），而不称为定理，是因为对“可计算”这个术语无法给出形式定义，因此无法直接给出证明。书上通过证明可以用图灵机模拟现代电子计算的极限模型随机存取机（RAM）对邱奇图灵论题给出有力的支持。 4.9 图灵机带符号的化简 在前面我们构造图灵机模型时，除了字母表中的字符以外，为了模拟方便，往往引入多个带符号。其实，这种情况不是必须的。通过增加状态的设置，可以把输入字母以外的带符号减少到只含一个空白符。4.10 图灵机编码与通用图灵机4.10.1 图灵机编码 对于一个图灵机，只要按顺序列出它的全