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

形式语言与自动机理论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第7章下推自动机•PDA描述CFL，所以它应该与CFG等价。•PDA应该包含FA的各个元素，或者包含那些可以取代FA的各个元素的功能的元素。•PDA按照最左派生的派生顺序，处理处于当前句型最左边的变量，因此，需要采用栈作为其存储机构。•按照FA的“习惯”，PDA用终态接受语言。•模拟GNF的派生PDA用空栈接受语言。第7章下推自动机•主要内容–PDA的基本概念。–PDA的构造举例。–用终态接受语言和用空栈接受语言的等价性。–PDA是CFL的接受器。•重点–PDA的基本定义及其构造，PDA是CFL的等价描述。•难点–根据PDA构造CFG。7.1基本定义•PDA的物理模型7.1基本定义•PDA应该含有三个基本结构–存放输入符号串的输入带。–存放文法符号的栈。–有穷状态控制器。•PDA的动作–在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。7.1基本定义•下推自动机(pushdownautomaton，PDA)M=(Q，∑，Γ，δ，q0，Z0，F)Q——状态的非空有穷集合。q∈Q，q称为M的一个状态(state)；∑——输入字母表(inputalphabet)。要求M的输入字符串都是∑上的字符串；Γ——栈符号表(stackalphabet)。A∈Γ，叫做一个栈符号；7.1基本定义•Z0——Z0∈Γ叫做开始符号(startsymbol)，是M启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；•q0——q0∈Q，是M的开始状态(initialstate)，也可叫做初始状态或者启动状态；•F——FQ，是M的终止状态(finalstate)集合，简称为终态集。q∈F，q称为M的终止状态，也可称为接受状态(acceptstate)，简称为终态。7.1基本定义•δ——状态转移函数(transitionfunction)，有时候又叫做状态转换函数或者移动函数。δ：Q×(∑∪{ε})×Γ*2Q7.1基本定义δ(q，a，Z)={(p1，γ1)，(p2，γ2)，…，(pm，γm)}•表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1，2，…，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将γi中的符号从右到左依次压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。7.1基本定义δ(q，ε，Z)={(p1，γ1)，(p2，γ2)，…，(pm，γm)}•表示M进行一次ε-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1，2，…，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将γi中的符号从右到左依次压入栈，读头不移动。7.1基本定义•符号使用约定•英文字母表较为前面的小写字母，如a，b，c，…，表示输入符号；•英文字母表较为后面的小写字母，如x，y，z，…，表示由输入字符串；•英文字母表的大写字母，表示栈符号；•希腊字母α，β，γ，…，表示栈符号串。7.1基本定义•即时描述(instantaneousdescription，ID)(q，w，γ)∈(Q，∑*，Γ*)称为M的一个即时描述。它表示M处于状态q，w是当前还未处理的输入字符串，而且M正注视着w的首字符，栈中的符号串为γ，γ的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面，较右的符号在栈的较下面。7.1基本定义如果(p，γ)∈δ(q，a，Z)，a∈∑，则(q，aw，Zβ)├M(p，w，γβ)表示M做一次非空移动，从ID(q，aw，Zβ)变成ID(p，w，γβ)。如果(p，γ)∈δ(q，ε，Z)，则(q，w，Zβ)├M(p，w，γβ)表示M做一次空移动，从ID(q，aw，Zβ)变成ID(p，w，γβ)。7.1基本定义•├Mn是├M的n次幂–(q1，w1，β1)├Mn(qn，wn，βn)•├M*是├M的克林闭包–(q，w，α)├M*(p，x，β)•├M+是├M的正闭包–(q，w，α)├M+(p，x，β)7.1基本定义•M接受的语言–M用终态接受的语言•L(M)={w|(q0，w，Z0)├*(p，ε，β)且p∈F}–M用空栈接受的语言•N(M)={w|(q0，w，Z0)├*(p，ε，ε)}7.1基本定义•例7-1考虑接受语言L={w2wT|w∈{0,1}*}的PDA的设计。•解法1：•先设计产生L的CFGG1：G1：S2|0S0|1S1•再将此文法转化成GNF：G2：S2|0SA|1SBA0B17.1基本定义•句子0102010的最左派生和我们希望相应的PDAM的动作。派生M应该完成的动作S0SA从q0启动，读入0，将S弹出栈，将SA压入栈，状态不变01SBA在状态q0，读入1，将S弹出栈，将SB压入栈，状态不变010SABA在状态q0，读入0，将S弹出栈，将SA压入栈，状态不变0102ABA在状态q0，读入2，将S弹出栈，将ε压入栈，状态不变01020BA在状态q0，读入0，将A弹出栈，将ε压入栈，状态不变010201A在状态q0，读入1，将B弹出栈，将ε压入栈，状态不变0102010在状态q0，读入0，将A弹出栈，将ε压入栈，状态不变7.1基本定义M1=({q0}，{0，1，2}，{S，A，B}，δ1，q0，S，Φ)。其中：δ1(q0，0，S)={(q0，SA)}δ1(q0，1，S)={(q0，SB)}δ1(q0，2，S)={(q0，ε)}δ1(q0，0，A)={(q0，ε)}δ1(q0，1，B)={(q0，ε)}此时有：N(M1)=L。7.1基本定义M2=({q0,q1},{0,1,2},{S,A,B,Z0},δ2,q0,Z0,{q1})δ2(q0，0，Z0)={(q0，SAZ0)}δ2(q0，1，Z0)={(q0，SBZ0)}δ2(q0，2，Z0)={(q1，ε)}δ2(q0，0，S)={(q0，SA)}δ2(q0，1，S)={(q0，SB)}δ2(q0，2，S)={(q0，ε)}δ2(q0，0，A)={(q0，ε)}δ2(q0，1，B)={(q0，ε)}δ2(q0，ε，Z0)={(q1，ε)}此时有：N(M2)=L(M2)=L。7.1基本定义•解法2：•注意到L={w2wT|w∈{0,1}*}，所以PDAM3的工作可以分成两大阶段。–在读到字符2之前，为“记载”阶段：每读到一个符号就在栈中做一次相应的记载。–在读到2以后，再读到字符时，就应该进入“匹配”阶段：由于栈的“先进后出”特性正好与wT相对应，所以，用栈顶符号逐一地与输入字符匹配。7.1基本定义•M3=({q0，q1，q2，qf，qt}，{0，1，2}，{A，B，Z0}，δ3，q0，Z0，{qf})•q0为开始状态•q1为记录状态•q2为匹配状态•qf为终止状态•qt陷阱状态7.1基本定义δ3(q0，0，Z0)={(q1，AZ0)}δ3(q0，1，Z0)={(q1，BZ0)}δ3(q0，2，Z0)={(qf，ε)}δ3(q1，0，A)={(q1，AA)}δ3(q1，1，A)={(q1，BA)}δ3(q1，0，B)={(q1，AB)}δ3(q1，1，B)={(q1，BB)}7.1基本定义δ3(q1，2，A)={(q2，A)}δ3(q1，2，B)={(q2，B)}δ3(q2，0，A)={(q2，ε)}δ3(q2，0，B)={(qt，ε)}δ3(q2，1，B)={(q2，ε)}δ3(q2，1，A)={(qt，ε)}δ3(q2，ε，Z0)={(qf，ε)}此时有：N(M3)=L(M3)=L。7.1基本定义•不追求让PDA同时用终止状态和空栈接受同样的语言，还可以删除状态qf。这样我们可以得到PDAM4。•M4=({q0，q1，q2}，{0，1，2}，{A，B，Z0}，δ4，q0，Z0，Φ)δ4(q0，0，Z0)={(q1，AZ0)}δ4(q0，1，Z0)={(q1，BZ0)}δ4(q0，2，Z0)={(q2，ε)}7.1基本定义δ4(q1，0，A)={(q1，AA)}δ4(q1，1，A)={(q1，BA)}δ4(q1，0，B)={(q1，AB)}δ4(q1，1，B)={(q1，BB)}δ4(q1，2，A)={(q2，A)}δ4(q1，2，B)={(q2，B)}δ4(q2，0，A)={(q2，ε)}δ4(q2，1，B)={(q2，ε)}7.1基本定义•确定的(deterministic)PDA(q，a，Z)∈Q×∑×Γ，|δ(q，a，Z)|+|δ(q，ε，Z)|≤1•PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。•关键–对于(q，Z)∈Q×Γ，M此时如果有非空移动，就不能有空移动。–每一种情况下的移动都是惟一的。7.1基本定义•例7-2构造接受L={wwT|w∈{0,1}*}的PDA。•差异δ(q0，0，A)={(q0，AA)，(q1，ε)}0是w中的0或者是wT的首字符0；δ(q0，1，B)={(q0，BB)，(q1，ε)}1是w中的1或者是wT的首字符1。7.2PDA与CFG等价•对于任意PDAM1，存在PDAM2，使得L(M2)=N(M1)；•对于任意PDAM1，存在PDAM2，使得N(M2)=L(M1)。•CFL可以用空栈接受语言的PDA接受。•PDA接受语言可以用CFG描述。7.2.1PDA用空栈接受和用终止状态接受等价定理7-1对于任意PDAM1，存在PDAM2，使得N(M2)=L(M1)。证明要点：（1）构造。设PDAM1=(Q，∑，Γ，δ1，q01，Z01，F)取PDAM2=(Q∪{q02，qe}，∑，Γ∪{Z02}，δ，q02，Z02，F)其中Q∩{q02，qe}=Γ∩{Z02}=Φ。7.2.1PDA用空栈接受和用终止状态接受等价δ2(q02，ε，Z02)={(q01，Z01Z02)}(q,a,Z)∈Q×∑×Γ,δ2(q,a,Z)=δ1(q,a,Z)；(q,Z)∈(Q-F)×Γ,δ2(q,ε,Z)=δ1(q,ε,Z)；(q,Z)∈F×Γδ2(q,ε,Z)=δ1(q,ε,Z)∪{(qe,ε)}；q∈F,δ2(q,ε,Z02)={(qe,ε)}；Z∈Γ∪{Z02},δ2(qe,ε,Z)={(qe,ε)}7.2.1P