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

形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求•课程性质–技术基础•基础知识要求–数学分析（或者高等数学），离散数学•主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质课程目的和基本要求•本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力•计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型课程目的和基本要求•知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。•能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容•语言的文法描述。•RL–RG、FA、RE、RL的性质。•CFL–CFG(CNF、GNF)、PDA、CFL的性质。•TM–基本TM、构造技术、TM的修改。•CSL–CSG、LBA。教材及主要参考书目1.蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年2.JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,20013.JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第9章图灵机•图灵机(Turingmachine)是由图灵(AlanMathisomTuring)在1936年提出的，它是一个通用的计算模型。•通过研究TM，来研究递归可枚举集(recursivelyenumerableset)和部分地归函数(partialrecursivefunction)。•对算法和可计算性进行研究提供形式化描述工具。第9章图灵机•有效过程(effectiveprocedure)与算法(algorithm)。•希尔伯特纲领。•1931年，奥地利25岁的数理逻辑学家哥德尔(KuriGödel)发表了著名的不完整性理论。•具有有穷描述的过程是可数无穷多的，但函数却是不可数无穷多的。•世界上存在着许多的问题和函数，是无法用具有有穷描述的过程完成计算的——是不可计算的(incomputable)。第9章图灵机•主要内容–TM作为一个计算模型，它的基本定义，即时描述，TM接受的语言；TM的构造技术；TM的变形；Church-Turing论题；通用TM。可计算语言、不可判定性、P-NP问题)。•重点–TM的定义、TM的构造。•难点–TM的构造。9.1基本概念•图灵提出TM具有以下两个性质–具有有穷描述。–过程必须是由离散的、可以机械执行的步骤组成。•基本模型包括–一个有穷控制器。–一条含有无穷多个带方格的输入带。–一个读头。9.1基本概念•一个移动将完成以下三个动作：–改变有穷控制器的状态；–在当前所读符号所在的带方格中印刷一个符号；–将读头向右或者向左移一格。直观物理模型9.1.1基本TM•图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,δ,q0,B,F)，•Q为状态的有穷集合，q∈Q，q为M的一个状态；•q0∈Q，是M的开始状态，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号；9.1.1基本TM•FQ，是M的终止状态集，q∈F，q为M的一个终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行。•Γ为带符号表(tapesymbol)，X∈Γ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上；9.1.1基本TM•B∈Γ，被称为空白符(blanksymbol)，含有空白符的带方格被认为是空的；•∑Γ-{B}为输入字母表，a∈∑，a为M的一个输入符号。除了空白符号B之外，只有∑中的符号才能在M启动时出现在输入带上；9.1.1基本TM•δ：Q×ΓQ×Γ×{R,L}，为M的移动函数(transactionfunction)。•δ(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,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)q29.1.1基本TM•即时描述(instantaneousdescription,ID)•α1α2∈Γ*，q∈Q，α1qα2称为M的即时描述–q为M的当前状态。–α1α2为M的输入带最左端到最右的非空白符号组成的符号串或者是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串–M正注视着α2的最左符号。9.1.1基本TM设X1X2…Xi-1qXiXi+1…Xn是M的一个ID如果δ(q,Xi)=(p,Y,R)，则，M的下一个ID为X1X2…Xi-1YpXi+1…Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn–表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…Xi-1YpXi+1…Xn。9.1.1基本TM•如果δ(q,Xi)=(p,Y,L)则，–当i≠1时，M的下一个ID为X1X2…pXi-1YXi+1…Xn•记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn–表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…pXi-1YXi+1…Xn；9.1.1基本TM•├M是Γ*QΓ*×Γ*QΓ*上的一个二元关系–├Mn表示├M的n次幂：├Mn=(├M)n–├M+表示├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的变换序列如下：q0000100├M0q000100├M00q00100├M000q0100├M0001q100├M00010q10├M000100q1├M000100Bq29.1.1基本TM（2）处理输入串0001的过程中经历的ID变换序列如下：q00001├M0q0001├M00q001├M000q01├M0001q1├M0001Bq2（3）处理输入串000101的过程中经历的ID变换序列如下：q0000101├M0q000101├M00q00101├M000q0101├M0001q101├M00010q119.1.1基本TM（4）处理输入串1的过程中经历的ID变换序列如下：q01├M1q1├M1Bq2（5）处理输入串00000的过程中经历的ID变换序列如下：q000000├M0q00000├M00q0000├M000q000├M0000q00├M00000q0B9.1.1基本TM•TM接受的语言L(M)={x|x∈∑*&q0x├M*α1qα2&q∈F&α1、α2∈Γ*}•TM接受的语言叫做递归可枚举语言(recursivelyenumerablelanguage，r.e.)。•如果存在TMM=(Q,∑,Γ,δ,q0,B,F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursivelylanguage)。9.1.1基本TM•例9-3设有M2=({q0,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)q39.1.1基本TM•为了弄清楚M2接受的语言，需要分析它的工作过程。（1）处理输入串00010101的过程中经历的ID变换序列如下：q000010101├0q00010101├00q0010101├000q010101├0001q10101├00010q1101├000101q201├0001010q21├00010101q39.1.1基本TM•M2在q0状态下，遇到0时状态仍然保持为q0，同时将读头向右移动一格而指向下一个符号；•在q1状态下遇到第一个1时状态改为q1，并继续右移读头，以寻找下一个1；在遇到第二个1时，动作类似，只是将状态改为q2；当遇到第三个1时，进入终止状态q3，此时它正好扫描完整个输入符号串，表示符号串被M2接受。9.1.1基本TM（2）处理输入串1001100101100的过程中经历的ID变换序列如下：q01001100101100├1q1001100101100├10q101100101100├100q11100101100├1001q2100101100├10011q300101100•M2遇到第三个1时，进入终止状态q3，输入串的后缀00101100还没有被处理。但是，由于M2已经进入终止状态，表示符号串1001100101100被M2接受9.1.1基本TM（3）处理输入串000101000的过程中经历的ID变换序列如下：q0000101000├0q000101000├00q00101000├000q0101000├0001q101000├00010q11000├000101q2000├0001010q200├00010100q20├000101000q2B•当M2的ID变为000101000q2B时，因为无法进行下一个移动而停机,不接受输入串000101000。9.1.1基本TM•M2接受的语言是字母表{0，1}上那些至少含有3个1的0、1符号串。请读者考虑，如何构造出接受字母表{0，1}上那些含且恰含有3个1的符号串的TM。9.1.1基本TM•例9-4构造TMM3，使L(M)={0n1n2n|n≥1}。分析：–不能通过“数”0、1、或者2的个数来实现检查。–最为原始的方法来比较它们的个数是否是相同的：消除一个0、然后消除一个1，最后消除一个2。–消除的0的带方格上印刷一个X，在消除的1的带方格上印刷一个Y，在消除的2的带方格上印刷一个Z。9.1.1基本TM–正常情况下，输入带上的符号串的一般形式为00…0011…1122…22–TM启动后，经过一段运行，输入带上的符号串的一般情况为X…X0…0Y…Y1…1Z…Z2…2BB–需要给予边界情况密切的关注。9.1.1基本TM•边界情况•X…XX…XY…YY…YZ…Z2…2BB•X…XX…XY…Y1…1Z…Z2…2BB•X…X0…0Y…YY…YZ…Z2…2BB•X…X0…0Y…Y1…1Z…ZZ…ZBB•X…X0…0Y…YY…YZ…ZZ…ZBB构造思路移动函数012XYZBq0(q0,X,R)(q4,Y,R)q1(q1,0,R)(q2,Y,R)(q1,Y,R)q2(q2,1,R)(q3,Z,L)(q