形式语言与自动机理论--第九章（蒋宗礼）

《形式语言与自动机理论--第九章（蒋宗礼）》由会员分享，可在线阅读，更多相关《形式语言与自动机理论--第九章（蒋宗礼）（110页珍藏版）》请在金锄头文库上搜索。

1、形式语言与自动机理论 Formal Languages and Automata Theory蒋宗礼课程目的和基本要求 课程性质 技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质 课程目的和基本要求 本专业人员4种基本的专业能力 计算思维能力 算法的设计与分析能力 程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力 逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述 理解和处理形式模型课程目的和基本要求 知识 掌握正则语言、下文无关语言的文法、识别 模型及其基本性质、图灵机的基本知识。

2、能力 培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握“问题、形式化描述 、自动化（计算机化）”这一最典型的计算机 问题求解思路。 主要内容 语言的文法描述。 RL RG、 FA、RE、RL的性质 。 CFL CFG(CNF、GNF)、PDA、CFL的性质。 TM 基本TM、构造技术、TM的修改。 CSL CSG、LBA。教材及主要参考书目 蒋宗礼，姜守旭. 形式语言与自动机理论. 北京： 清华大学出版社，2003年 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory,

3、Languages, and Computation (2nd Edition). Addison- Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979第9章 图灵机 图灵机(Turing machine)是由图灵(Alan MathisomTuring)在1936年提出的，它是一个 通用的计算模型。 通过研究TM

4、，来研究递归可枚举集 (recursively enumerable set)和部分地归函 数(partial recursive function)。 对算法和可计算性进行研究提供形式化描 述工具。第9章 图灵机 有效过程(effective procedure)与算法 (algorithm)。 希尔伯特纲领。 1931年，奥地利25岁的数理逻辑学家哥德尔(Kuri Gdel)发表了著名的不完整性理论。 具有有穷描述的过程是可数无穷多的，但函数却 是不可数无穷多的。 世界上存在着许多的问题和函数，是无法用具有 有穷描述的过程完成计算的是不可计算的 (incomputable) 。第9章 图灵

5、机 主要内容 TM作为一个计算模型，它的基本定义，即 时描述，TM接受的语言；TM的构造技术； TM的变形；Church-Turing论题；通用TM。 可计算语言、不可判定性、P-NP问题)。 重点 TM的定义、TM的构造。 难点 TM的构造。 9.1 基本概念 图灵提出TM具有以下两个性质具有有穷描述。 过程必须是由离散的、可以机械执行的步骤 组成。 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 9.1 基本概念 一个移动将完成以下三个动作： 改变有穷控制器的状态； 在当前所读符号所在的带方格中印刷 一个符号； 将读头向右或者向左移一格。直观物理模型9.1.1

6、 基本TM 图灵机(Turing machine)/基本的图灵机TM M=(Q, , , ,q0 , B , F) ， Q为状态的有穷集合，qQ，q为M的一 个状态； q0Q，是M的开始状态，对于一个给定的 输入串，M从状态q0启动，读头正注视着输 入带最左端的符号；9.1.1 基本TM FQ，是M的终止状态集，qF，q为M 的一个终止状态。与FA和PDA不同，一般地 ，一旦M进入终止状态，它就停止运行。 为带符号表(tape symbol)，X，X为 M的一个带符号，表示在M的运行过程中，X 可以在某一时刻出现在输入带上；9.1.1 基本TM B，被称为空白符(blank symbol)，含

7、有 空白符的带方格被认为是空的； -B为输入字母表，a，a为M的 一个输入符号。除了空白符号B之外，只有 中的符号才能在M启动时出现在输入带上； 9.1.1 基本TM ：QQR, L，为M的移动函数 (transaction function)。 (q , X)=(p , Y, R)表示M在状态q读入符号X ，将状态改为p，并在这个X所在的带方格中 印刷符号Y，然后将读头向右移一格； (q , X)=(p , Y , L)表示M在状态q读入符号 X，将状态改为p，并在这个X所在的带方格 中印刷符号Y，然后将读头向左移一格。 9.1.1 基本TM 例 9-1 设M1=(q0, q1, q2,0,

8、 1,0, 1, B,q0 , B ,q2)，其中的定义如下，对于此定义， 也可以用表9-1表示。 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, B)= (q2, B, R) 9.1.1 基本TM01Bq0(q0, 0, R)(q1, 1, R) q1(q1, 0, R) (q2, B, R)q2 9.1.1 基本TM 即时描述(instantaneous description, ID) 12*，qQ，1q2称为M的即时描述 q为M的当前状态。 12为M的输入带最左端到最右的非空白符 号组成的符号串或者是M的

9、输入带最左端到M 的读头注视的带方格中的符号组成的符号串 M正注视着2的最左符号。9.1.1 基本TM设X1X2Xi-1qXiXi+1Xn是M的一个ID 如果(q, Xi)=(p, Y, R)，则，M的下一个ID为 X1X2Xi-1YpXi+1Xn 记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，经过 一次移动，将ID变成X1X2Xi-1YpXi+1Xn 。9.1.1 基本TM 如果(q, Xi)=(p, Y, L)则， 当i1时，M的下一个ID为X1X2pXi-1YXi+1Xn 记作 X1X2Xi-1qXiXi+

10、1XnM X1X2pXi-1YXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，经过 一次移动，将ID变成X1X2pXi-1YXi+1Xn； 9.1.1 基本TM M是*Q*Q*上的一个二元关系 Mn表示M的n次幂：Mn =(M)nM+表示M的正闭包：M+ =(M)+M*表示M的克林闭包：M* =(M)* 在意义明确时，分别用、n 、+、*表 示M 、Mn、M+、M*。9.1.1 基本TM 例 9-2 例 9-1所给的M1在处理输入串的过程 中经历的ID变换序列。 （1）处理输入串000100的过程中经历的ID的 变换序列如下： q0000100M 0q000100M 00q0

11、0100 M 000q0100M 0001q100M 00010q10 M 000100 q1M 000100Bq2 9.1.1 基本TM（2）处理输入串0001的过程中经历的ID变换 序列如下： q00001M 0q0001M 00q001 M 000q01M 0001q1M 0001Bq2 （3）处理输入串000101的过程中经历的ID变 换序列如下： q0000101M 0q000101M 00q00101 M 000q0101M 0001q101M 00010q119.1.1 基本TM（4）处理输入串1的过程中经历的ID变换序 列如下： q01M 1q1M 1Bq2 （5）处理输入串0

12、0000的过程中经历的ID变 换序列如下： q000000M 0q00000M 00q0000 M 000q000M 0000 q00M 00000q0B9.1.1 基本TM TM接受的语言 L(M)=x | x* & q0xM* 1 q2 & qF &1、 2* TM接受的语言叫做递归可枚举语言(recursively enumerable language，r.e.)。 如果存在TM M=(Q, , , ,q0 , B , F)，L=L(M)， 并且对每一个输入串x，M都停机，则称L为递归语 言(recursively language)。 9.1.1 基本TM 例 9-3 设有M2=(q

13、0, q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定义如下： (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R)9.1.1 基本TM01Bq0(q0, 0, R)(q1, 1, R) q1(q1, 0, R)(q2, 1, R) q2(q2, 0, R)(q3, 1, R) q3 9.1.1 基本TM 为了弄清楚M2接受的语言，需要分析它的 工作过程。 （1）处理输入串000

14、10101的过程中经历的ID 变换序列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q39.1.1 基本TM M2在q0状态下，遇到0时状态仍然保持为q0 ，同时将读头向右移动一格而指向下一个符 号； 在q1状态下遇到第一个1时状态改为q1，并 继续右移读头，以寻找下一个1；在遇到第二 个1时，动作类似，只是将状态改为q2；当遇 到第三个1时，进入终止状态q3，此时它正好 扫描完整个输入符号串，表示符号串被M2接 受。 9.1.1 基本T

15、M（2）处理输入串1001100101100的过程中经 历的ID变换序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100 M2遇到第三个1时，进入终止状态q3，输入 串的后缀00101100还没有被处理。但是，由 于M2已经进入终止状态，表示符号串 1001100101100被M2接受 9.1.1 基本TM（3）处理输入串000101000的过程中经历的ID变换 序列如下： q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010 q200 00010100 q20 000101000 q2B 当M2的ID变为000101000q2B时，因