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

形式语言与自动机理论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第10章上下文有关语言•主要内容–TM与PSG的等价性。–线性界限自动机(LBA)。–LBA作为CSL的识别器。•重点–LBA、LBA作为CSL的识别器。•难点–LBA作为CSL的识别器。•本章的内容是介绍性。10.1TM与PSG的等价性•例10-1构造产生语言{0n|n为2的非负整数次幂}的文法。设计思想：–在文法中设置变量C，充当TM中的读头的作用，它从左到右扫描0，并且在每次遇到一个0时，都用00替换之，这使得当它从最左端移到最右端时，就完成了当前串的加倍工作，为了使串中的0再次被加倍，变量D充当将这个“读头”从右端移回到最左端的作用。为了标记出端点，文法用A、B分别表示串的最左端和最右端。10.1TM与PSG的等价性•G1：S0产生句子0。•SAC0B产生句型AC0B，A、B分别表示左右端点，C为向右的倍增“扫描器”。•C000CC向右扫描，将每一个0变成00，以实现0个数的加倍。10.1TM与PSG的等价性•CBDBC到达句型的左端点，变成D，准备进行从右到左的扫描，以实现对句型中0的个数的再次加倍。•CBEC到达句型的左端点，变成E，表示加倍工作已完成，准备结束。10.1TM与PSG的等价性•0DD0D移回到左端点。•ADAC当D到达左端点时，变成C，此时已经做好了进行下一次加倍的准备工作。•0EE0E向右移动，以寻找左端点A。•AEεE找到A后，一同变成ε，从而得到一个句子。10.1TM与PSG的等价性G2：SAC0BC000CCBDB0DD00CBEADACACFF00F0EE0AEεFBε另一个相关的文法10.1TM与PSG的等价性定理10-1对于任一PSGG=(V，T，P，S)，存在TMM，使得L(M)=L(G)。证明要点：基本思想如下。–M具有两条带，其中一条带用来存放输入字符串w，第二条带用来试着产生w。即，第二条带上存放的将是一个句型。我们希望该句型能够派生出w。在开始启动时，这个句型就是S。10.1TM与PSG的等价性•设第二条带上的句型为γ，M按照某种策略在γ中选择为G的某个产生式左部的子串α，再按照非确定的方式选择α产生式的某一个候选式β，用β替换α。在需要时，利用适当的移动技术，让TM可以实现将句型中的α替换成β的工作。•当第二条带上的内容为一个终极符号行时，就把它与第一条带上的w进行比较，如果相等，就接受；如果不相等，就去寻找是否存在可以产生w的派生。10.1TM与PSG的等价性•由于G为PSG，所以，在整个“试派生”过程中，我们是无法总能根据当前句型的长度来决定该派生是否需要继续进行下去。这样一来，对于一个给定的输入字符串，如果它不是L(G)的句子，我们构造的TM可能会陷入用不停机的工作过程中。这从另一方面说明，短语结构语言不一定是递归语言。10.1TM与PSG的等价性定理10-2对于任一TMM，存在PSGG=(V，T，P，S)，使得L(G)=L(M)。证明要点：①设TMM=(Q,∑,Γ,δ,q0,B,F)，L=(M)。②让G可以产生∑*中的任意一个字符串的变形，然后让G模拟M处理这个字符串。如果M接受它，则G就将此字符串的变形还原成该字符串。③变形是让每个字符对应一个二元组。[a1,a1][a2,a2]…[an,an]∈(∑×∑)*，被看成a1a2…an的两个副本。10.1TM与PSG的等价性④G在一个副本上模拟M的识别动作，如果M进入终止状态，则G将句型中除另一个副本外的所有字符消去。G=((∑∪{ε})×Γ∪{A1,A2,A3}∪Q,∑,P,A1)(1)A1q0A2准备模拟M从q0启动；(2)A2[a,a]A2a∈∑，A2首先生成任意的形如[a1,a1][a2,a2]…[an,an]的串；10.1TM与PSG的等价性•(3)A2A3在预生成双副本子串[a1,a1][a2,a2]……[an,an]后，准备用A3在该子串之后生成一系列的相当于空白符的子串，为G能够顺利地模拟M在处理相应的输入字符串的过程中，需要将读头移向输入串右侧的初始为B的地方做准备；10.1TM与PSG的等价性•(4)A3[ε,B]A3由于M在处理一个字符时，不知道将需要用到输入串右侧的多少个初始为B的带方格，所以，我们让A3生成一系列的相当于空白符的子串[ε,B][ε,B]……[ε,B]。在派生过程中，其个数依据实际需要而定；10.1TM与PSG的等价性•(5)A3ε•(6)a∈∑∪{ε}，q,p∈Q，X,Y∈Γ，如果δ(q,X)=(p,Y,R)，则–q[a,X][a,Y]p–G模拟M的一次右移；10.1TM与PSG的等价性•(7)对于a,b∈∑∪{ε}，q,p∈Q，X,Y,Z∈Γ，如果δ(q,X)=(p,Y,L)，则–[b,Z]q[a,X]p[b,Z][a,Y]–G模拟M的一次左移；•(8)对于a∈∑∪{ε}，q∈F则–[a,X]qqaqG先将句型中的[、]、X等消除；–q[a,X]qaq–qε最后再消除句型中的状态q10.2LBA及其与CSG的等价性•线性有界自动机(linearboundedautomaton，LBA)–非确定的TM。–输入字母表包含两个特殊的符号￠和$，其中，￠作为输入符号串的左端标志，$作为输入符号串的右端标志。–LBA的读头只能在￠和$之间移动，它不能在端点符号￠和$上面打印另外一个符号。10.2LBA及其与CSG的等价性•LBA可以被看成一个八元组，M=(Q,∑,Γ,δ,q0,￠,$,F)其中，Q、∑、Γ、δ、q0、F与TM中的定义相同，￠∈∑，$∈∑，M接受的语言L(M)={w|w∈(∑-{￠,$})*&q∈F使得q0￠w$├*￠αqβ$。10.2LBA及其与CSG的等价性定理10-3如果L的CSL，εL，则存在LBAM，使得L=L(M)。证明要点：①设CSGG=(V，T，P，S)，使得L=L(G)。。②用一个两道TM模拟G。一道存放字符串￠w$，另一道用来生成w的推导。LBA及其与CSG的等价性③CSG保证只用考察长度不超过|w|句型。④将句型的长度限制在|w|以内，所以，M的运行不会超出符号￠和$规定的范围。⑤对于任意输入，LBA均会停机，这表明CSL是递归语言。10.2LBA及其与CSG的等价性定理10-4对于任意L，εL，存在LBAM，使得L=L(M)。则L是CSL。证明：与定理10-2的证明类似，主要是根据给定的LBAM构造出CSGG。这里的双副本串是形如[a1,q0￠a1][a2,a2]…[an,an$]的符号行，当长度为1时，此符号行为[a,q0￠a$]。10.2LBA及其与CSG的等价性（1）对于a∈∑-{￠,$}，A1[a,q0￠a]A2准备模拟M从q0启动，生成形如[a1,q0￠a1][a2,a2]…[an,an$]的双副本串(句型)中的[a1,q0￠a1]，并将生成子串[a2,a2]…[an,an$]的任务交给A2；A1[a,q0￠a$]生成双副本串[a,q0￠a$]；10.2LBA及其与CSG的等价性（2）对于a∈∑-{￠,$}，A2[a,a]A2A2首先生成任意的形如[a1,q0￠a1][a2,a2]…[an,an$]的双副本串中的子串[a2,a2]…[an-1,an-1]；（3）对于a∈∑-{￠,$}，A2[a,a$]A2最后生成任意的形如[a1,q0￠a1][a2,a2]…[an,an$]的双副本中的子串[an,an$]；10.2LBA及其与CSG的等价性(4)对于a∈∑-{$}，q,p∈Q，X,Y,Z∈Γ，X≠$，如果δ(q,X)=(p,Y,R)，则–[a,qX][b,Z][a,Y][b,pZ]–G模拟M的一次右移；(5)对于a,b∈∑-{￠}，q,p∈Q，X,Y,Z∈Γ，如果δ(q,X)=(p,Y,L)，则–[b,Z][a,qX][b,pZ][a,Y]–G模拟M的一次左移；10.2LBA及其与CSG的等价性(6)对于a∈∑，q∈F，X,Y∈Γ-{B}，[a,XqY]a–由于q为终止状态，所以可以消除它(7)对于a∈∑-{￠,$}，X∈Γ-{B}，–[a,X]bab–a[b,X]ab10.3小结本章讨论TM与PSG的等价性，介绍了识别CSL的装置——LBA。(1)对于任一PSGG=(V，T，P，S)，存在TMM，使得L(M)=L(G)；(2)对于任一TMM，存在PSGG=(V，T，P，S)，使得L(G)=L(M)；(3)LBA是一种非确定的TM，它的输入串被用符号￠和$括起来，而且读头只能在￠和$之间移动；10.2LBA及其与CSG的等价性(4)如果L是CSL，εL，则存在LBAM，使得L=L(M)；(5)对于任意L，εL，存在LBAM，使得L=L(M)，则L是CSL。