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

《形式语言与自动机理论--第七章(蒋宗礼)》由会员分享，可在线阅读，更多相关《形式语言与自动机理论--第七章(蒋宗礼)（52页珍藏版）》请在装配图网上搜索。

1、形式语言与自动机理论形式语言与自动机理论Formal Languages and Automata Theory蒋宗礼蒋宗礼课程目的和基本要求课程目的和基本要求 课程性质课程性质技术基础技术基础 基础知识要求基础知识要求 数学分析（或者高等数学），离散数学数学分析（或者高等数学），离散数学 主要特点主要特点 抽象和形式化抽象和形式化 理论证明和构造性理论证明和构造性 基本模型的建立与性质基本模型的建立与性质 课程目的和基本要求课程目的和基本要求 本专业人员本专业人员4 4种基本的专业能力种基本的专业能力计算思维能力计算思维能力算法的设计与分析能力算法的设计与分析能力程序设计和实现能力程序设计和

2、实现能力计算机软硬件系统的认知、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述构造模型对问题进行形式化描述理解和处理形式模型理解和处理形式模型课程目的和基本要求课程目的和基本要求 知识知识掌握正则语言、下文无关语言的文法、识别模掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。型及其基本性质、图灵机的基本知识。能力能力培养学生的形式化描述和抽象思维能力。培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握使学生了解和初步掌握“问题、形式化描述、

3、问题、形式化描述、自动化（计算机化）自动化（计算机化）”这一最典型的计算机问这一最典型的计算机问题求解思路。题求解思路。主要内容主要内容 语言的语言的文法文法描述。描述。RL RG、FA、RE、RL的性质的性质。CFL CFG(CNF、GNF)、PDA、CFL的性质。的性质。TM 基本基本TM、构造技术、构造技术、TM的修改。的修改。CSL CSG、LBA。教材及主要参考书目教材及主要参考书目1.1.蒋宗礼，姜守旭蒋宗礼，姜守旭.形式语言与自动机理论形式语言与自动机理论.北京：北京：清华大学出版社，清华大学出版社，2003年年 2.John E Hopcroft,Rajeev Motwani,

4、Jeffrey D Ullman.Introduction to Automata Theory,Languages,and Computation(2nd Edition).Addison-Wesley Publishing Company,2001 3.John E Hopcroft,Jeffrey D Ullman.Introduction to Automata Theory,Languages,and Computation.Addison-Wesley Publishing Company,1979第第7章下推自动机章下推自动机 PDA描述描述CFL，所以它应该与，所以它应该与CF

5、G等价。等价。PDA应该包含应该包含FA的各个元素，或者包含那的各个元素，或者包含那些可以取代些可以取代FA的各个元素的功能的元素。的各个元素的功能的元素。PDA按照最左派生的派生顺序，处理处于按照最左派生的派生顺序，处理处于当前句型最左边的变量，因此，需要采用当前句型最左边的变量，因此，需要采用栈作为其存储机构。栈作为其存储机构。按照按照FA的的“习惯习惯”，PDA用终态接受语言。用终态接受语言。模拟模拟GNF的派生的派生PDA用空栈接受语言。用空栈接受语言。第第7章下推自动机章下推自动机 主要内容主要内容 PDA的基本概念。的基本概念。PDA的构造举例。的构造举例。用终态接受语言和用空栈接

6、受语言的等价性。用终态接受语言和用空栈接受语言的等价性。PDA是是CFL的接受器。的接受器。重点重点 PDA的基本定义及其构造，的基本定义及其构造，PDA是是CFLCFL的等价描述。的等价描述。难点难点 根据根据PDA构造构造CFGCFG。7.1 基本定义基本定义 PDA的物理模型的物理模型7.1 基本定义基本定义 PDA应该应该含有三个基本结构含有三个基本结构 存放输入符号串的输入带。存放输入符号串的输入带。存放文法符号的栈。存放文法符号的栈。有穷状态控制器。有穷状态控制器。PDA的动作的动作 在有穷状态控制器的控制下根据它的当前状态、在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及

7、输入符号作出相应的动作，在栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。有的时候，不需要考虑输入符号。7.1 基本定义基本定义 下推自动机下推自动机(pushdown automaton，PDA)M=(Q，q0，Z0，F)Q状态的非空有穷集合。状态的非空有穷集合。qQ，q称为称为M的一个的一个状态状态(state)；输入字母表输入字母表(input alphabet)。要求。要求M的的输入字符串都是输入字符串都是上的字符串；上的字符串；栈符号表栈符号表(stack alphabet)。A，叫，叫做一个栈符号；做一个栈符号；7.1 基本定义基本定义 Z0Z0叫做叫做开始符

8、号开始符号(start symbol)，是是M启动时候栈内惟一的一个符号。所以，启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；习惯地称其为栈底符号；q0q0Q，是，是M的的开始状态开始状态(initial state)，也可叫做也可叫做初始状态初始状态或者或者启动状态启动状态；FF Q，是，是M的的终止状态终止状态(final state)集集合，简称为终态集。合，简称为终态集。qF，q称为称为M的终的终止状态，也可称为止状态，也可称为接受状态接受状态(accept state)，简称为终态。简称为终态。7.1 基本定义基本定义 状态转移函数状态转移函数(transition fun

9、ction)，有时候又叫做状态转换函数状态转换函数或者移动函数。移动函数。：Q()*2Q7.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)

10、，(pm，m)表示表示M进行一次进行一次-移动移动(空移动空移动)，即，即M在状在状态态q，栈顶符号为，栈顶符号为Z时，无论输入符号是什时，无论输入符号是什么，对于么，对于i=1，2，m，可以选择地将状，可以选择地将状态变成态变成pi，并将栈顶符号，并将栈顶符号Z弹出，将弹出，将i中的中的符号从右到左依次压入栈，读头不移动。符号从右到左依次压入栈，读头不移动。7.1 基本定义基本定义 符号使用约定符号使用约定 英文字母表较为前面的小写字母，如英文字母表较为前面的小写字母，如a，b，c，表示输入符号；，表示输入符号；英文字母表较为后面的小写字母，如英文字母表较为后面的小写字母，如x，y，z，表示

11、由输入字符串；，表示由输入字符串；英文字母表的大写字母，表示栈符号；英文字母表的大写字母，表示栈符号；希腊字母希腊字母，表示栈符号串。，表示栈符号串。7.1 基本定义基本定义 即时描述即时描述(instantaneous description，ID)(q，w，)(Q，*，*)称为称为M的一个的一个即时描述即时描述。它表示。它表示M处于状态处于状态q，w是当前是当前还未处理的输入字符串，而且还未处理的输入字符串，而且M正注视着正注视着w的首字符，栈中的符号串为的首字符，栈中的符号串为，的最左符的最左符号为栈顶符号，最右符号为栈底的符号，号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面

12、，较右的符号在较左的符号在栈的较上面，较右的符号在栈的较下面。栈的较下面。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

13、，)M+(p，x，)7.1 基本定义基本定义 M接受的语言接受的语言 M用终态接受的语言用终态接受的语言 L(M)=w|(q0，w，Z0)*(p，)且且 pF M用空栈接受的语言用空栈接受的语言 N(M)=w|(q0，w，Z0)*(p，)7.1 基本定义基本定义 例例 7-1 考虑接受语言考虑接受语言L=w2wT|w0,1*的的PDA的设计。的设计。解法解法1：先设计产生先设计产生L的的CFG G1：G1：S2|0S0|1S1 再将此文法转化成再将此文法转化成GNF：G2：S2|0SA|1SBA0B1 7.1 基本定义基本定义句子句子0102010的最左派生和我们希望相应的的最左派生和我们希望

14、相应的PDA M的动作。的动作。派生派生M应该完成的动作应该完成的动作S0SA从从q0启动，读入启动，读入0，将，将S弹出栈，将弹出栈，将SA压入栈，状态不变压入栈，状态不变01SBA在状态在状态q0，读入，读入1，将，将S弹出栈，将弹出栈，将SB压入栈，状态不变压入栈，状态不变 010SABA在状态在状态q0，读入，读入0，将，将S弹出栈，将弹出栈，将SA压入栈，状态不变压入栈，状态不变0102ABA在状态在状态q0，读入，读入2，将，将S弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态不变01020BA在状态在状态q0，读入，读入0，将，将A弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态

15、不变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(

16、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|w0,1*，所以，所以PDA M3 的工作可以分成两大阶段。的工作可以分成两大阶段。在读到字符在读到字符2之前，为之前，为“记载记载”阶段：每读到阶段：每读到一个符号就在栈中做一次相应的记载。一个符

17、号就在栈中做一次相应的记载。在读到在读到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)=

18、(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同时用终止状态和空栈接受同时用终止状态和空栈接受同样的语言，还可以删除状态同样的语言，还

19、可以删除状态qf。这样我们。这样我们可以得到可以得到PDA M4。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)PD

20、A(q，a，Z)Q，|(q，a，Z)|+|(q，Z)|1 PDA在每一个状态在每一个状态q和一个栈顶符号下的和一个栈顶符号下的动作都是惟一的。动作都是惟一的。关键关键 对于对于(q，Z)Q，M此时如果有非空移动，此时如果有非空移动，就不能有空移动。就不能有空移动。每一种情况下的移动都是惟一的。每一种情况下的移动都是惟一的。7.1 基本定义基本定义 例例 7-2 构造接受构造接受L=wwT|w0,1*的的PDA。差异差异(q0，0，A)=(q0，AA)，(q1，)0是是w中的中的0或者是或者是wT的首字符的首字符0；(q0，1，B)=(q0，BB)，(q1，)1是是w中的中的1或者是或者是wT的

21、首字符的首字符1。7.2 PDA与与CFG等价等价 对于任意对于任意PDA M1，存在，存在PDA M2，使得，使得L(M2)=N(M1)；对于任意对于任意PDA M1，存在，存在PDA M2，使得，使得N(M2)=L(M1)。CFL可以用空栈接受语言的可以用空栈接受语言的PDA接受。接受。PDA接受语言可以用接受语言可以用CFG描述。描述。7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价 定理定理 7-1 对于任意对于任意PDA M1，存在，存在PDA M2，使得使得N(M2)=L(M1)。证明要点：证明要点：（1）构造。构造。设设PDA M1=(Q，1，q01

22、，Z01，F)取取PDA M2=(Qq02，qe，Z02，q02，Z02，F)其中其中Qq02，qe=Z02=。7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价 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)F2(q,Z)=1(q,Z)(qe,)；qF,2(q,Z02)=(qe,)；ZZ02,2(qe,Z)=(qe,)7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价（2）证明证明N(M2)=L(M1)。xL(M1)(q01

23、，x，Z01)M1*(q，)且且qF(q01，x，Z01Z02)M1*(q，Z02)且且qF(q01，x，Z01Z02)M2*(q，Z02)且且qF7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价(q01，x，Z01Z02)M2*(q，Z02)M2*(qe，)且且qF(q01，x，Z01Z02)M2*(qe，)(q02，x，Z02)M2(q01，x，Z01Z02)M2*(qe，)(q02，x，Z02)M2*(qe，)xN(M2)7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价 定理定理 7-2 对于任意对于任意PDA M1，存在，存在

24、PDA M2，使得使得L(M2)=N(M1)。证明要点：证明要点：(1)构造。构造。设设PDA M1=(Q，1，q01，Z01，)7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价 取取PDA M2=(Qq02，qf，Z02，q02，Z02，qf)其中其中Qq02，qf=Z02=。2的定义如下，的定义如下，2(q02，Z02)=(q01，Z01Z02)对于对于(q，a，Z)Q(),2(q，a，Z)=1(q，a，Z)。2(q，Z02)=(qf，)7.2.1 PDA用空栈接受和用终止用空栈接受和用终止状态接受等价状态接受等价(2)证明证明L(M2)=N(M1)。xL(M

25、2)(q02，x，Z02)M2*(qf，)(q02，x，Z02)M2(q01，x，Z01Z02)(q02，x，Z02)M2(q01，x,Z01Z02)M2*(qf,)。(q01，x，Z01Z02)M2*(q，Z02)且且(q，Z02)M2*(qf，)(q01，x，Z01Z02)M1*(q，Z02)。(q01，x，Z01)M1*(q，)。xN(M1)。7.2.2 PDA与与CFG等价等价 定理定理 7-3 对于任意对于任意CFL L，存在，存在PDA M，使，使得得N(M)=L。证明要点：先考虑识别证明要点：先考虑识别L-的的PDA，然后再，然后再考虑对考虑对的处理问题。的处理问题。7.2.2

26、PDA与与CFG等价等价(1)构造构造PDA。设设GNF G=(V，T，P，S)，使得，使得L(G)=L-。取取PDA M=(q，T，V，q，S，)对于任意的对于任意的AV，aT，(q，a，A)=(q，)|AaP也就是说，也就是说，(q，)(q，a，A)的充分必要的充分必要条件是条件是AaP。7.2.2 PDA与与CFG等价等价(2)证明构造的正确性：证明构造的正确性：N(M)=L-。施归纳于施归纳于w的长度的长度n，证明，证明 (q，w，S)Mn(q，)的充分必要条件为的充分必要条件为Snw。并且在假设结论对并且在假设结论对n=k成立，而证明结成立，而证明结论对论对n=k+1成立时，取成立时

27、，取w=xa，|x|=k，aT。在证明必要性时有如下过程，充分性的证在证明必要性时有如下过程，充分性的证明过程是倒退回来。明过程是倒退回来。7.2.2 PDA与与CFG等价等价(q,w,S)=(q，xa，S)Mk(q，a，)M(q，)此时必定存在此时必定存在AV，=A1，(q,2)(q,a,A)。(q,a,)=(q,a,A1)M(q,21)=(q，)。由由(q，2)(q，a，A)就可以得到就可以得到Aa2P，再，再由归纳假设，得到由归纳假设，得到Skx A1。合起来就有合起来就有Skx A1xa21。7.2.2 PDA与与CFG等价等价(3)考虑考虑L的情况。的情况。先按照先按照(1)的构造方

28、法构造出的构造方法构造出PDA M=(q，T，V，q，S，)使得使得N(M)=L-。然后取。然后取M1=(q，q0，T，VZ，1，q0，Z，)其中，其中，q0q，Z V，令，令1(q0，Z)=(q0，)，(q，Z0)，对于对于(a，A)TV1(q，a，A)=(q，a，A)7.2.2 PDA与与CFG等价等价 定理定理 7-4 对于任意的对于任意的PDA M，存在，存在CFG G使使得得L(G)=N(M)。证明要点：证明要点：(1)构造构造对应对应(q1，A1A2An)(q，a，A)难以用产难以用产生式生式q，A aq1，A1A2An模拟。模拟。同样也难以用同样也难以用q，A aq1，A1 q2

29、，A2qn，An模拟。模拟。7.2.2 PDA与与CFG等价等价 PDA的移动的移动(q1，A1A2An)(q，a，A)需需要用如下形式的产生式模拟。要用如下形式的产生式模拟。q，A，qn+1 aq1，A1，q2 q2，A2，q3 qn，An，qn+1 q2，qn是分别对应是分别对应PDA恰恰“处理完处理完”A1进进而处理而处理A2，恰，恰“处理完处理完”An-1进而处理进而处理An的状态。当然就有了恰的状态。当然就有了恰“处理完处理完”An而进入的而进入的状态状态qn+1，这个状态就是，这个状态就是“处理完处理完”A后其次栈后其次栈顶变为栈顶的状态。顶变为栈顶的状态。7.2.2 PDA与与C

30、FG等价等价 取取CFG G=(V，P，S)，其中：，其中：V=SQQP=Sq0，Z0，q|qQq，A，qn+1 aq1，A1，q2 q2，A2，q3qn，An，qn+1|(q1，A1A2An)(q，a，A)且且a，q2、q3、qn、qn+1Q且且n1q，A，q1 a|(q1，)(q，a，A)7.2.2 PDA与与CFG等价等价(2)构造的正确性。构造的正确性。先证一个更一般的结论：先证一个更一般的结论：q，A，p*x的的充分必要条件是充分必要条件是(q，x，A)(p，)，然，然后根据这个一般的结论得到后根据这个一般的结论得到q=q0，A=S时的时的特殊结论特殊结论构造的正确性。构造的正确性。

31、必要性：设必要性：设 q，A，p i x，施归纳于，施归纳于i，证明证明(q，x，A)*(p，)充分性：设充分性：设(q，x，A)i(p，)成立，施成立，施归纳于归纳于i证明证明q，A，p*X。7.3 小结小结 PDA M是一个七元组：是一个七元组：M=(Q，q0，Z0，F)它是它是CFL的识别模型，它比的识别模型，它比FA多了栈符号，多了栈符号，这些符号和状态一起用来记录相关的语法这些符号和状态一起用来记录相关的语法信息。信息。在决定移动时，它将栈顶符号作为考虑的在决定移动时，它将栈顶符号作为考虑的因素之一。因素之一。7.3 小结小结 PDA可以用终态接受语言，也可以用空栈可以用终态接受语言，也可以用空栈接受语言。接受语言。与与DFA不同，不同，(q，a，Z)Q，DPDA仅要求仅要求|(q，a，Z)|+|(q，Z)|1 7.3 小结小结 关于关于CFG和和PDA主要有如下结论：主要有如下结论：(1)对于任意对于任意PDA M1，存在，存在PDA M2，使，使得得N(M2)=L(M1);(2)对于任意对于任意PDA M1，存在，存在PDA M2，使，使得得L(M2)=N(M1);(3)对于任意对于任意CFL L，存在，存在PDA M，使得，使得N(M)=L;(4)对于任意的对于任意的PDA M，存在，存在CFG G使得使得L(G)=N(M)。