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

课程目的和基本要求课程性质技术基础

基础知识要求

数学分析（或者高等数学），离散数学

主要特点

抽象和形式化

理论证明和构造性

基本模型的建立与性质

课程目的和基本要求本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型课程目的和基本要求

知识掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容

语言的文法描述。RLRG、FA、RE、RL的性质。CFLCFG(CNF、GNF)、PDA、CFL的性质。

TM基本TM、构造技术、TM的修改。CSLCSG、LBA。教材及主要参考书目蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年

JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,2001JohnEHopcroft,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×(∑∪{ε})×Γ

7.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|1SB A

0 B

1

7.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.1PDA用空栈接受和用终止状态接受等价

（2）证明N(M2)=L(M1)。

x∈L(M1)

(q01，x，Z01)├M1*(q，ε，γ)且q∈F

(q01，x，Z01Z02)├M1*(q，ε，γZ02)且q∈F

(q01，x，Z01Z02)├M2*(q，ε，γZ02)且q∈F7.2.1PDA用空栈接受和用终止状态接受等价

(q01，x，Z01Z02)├M2*(q，ε，γZ02)├M2*(qe，ε，ε)且q∈F

(q01，x，Z01 Z02)├M2*(qe，ε，ε)

(q02，x，Z02)├M2(q01，x，Z01Z02)├M2*(qe，ε，ε)

(q02，x，Z02)├M2*(qe，ε，ε)

x∈N(M2)7.2.1PDA用空栈接受和用终止状态接受等价

定理7-2

对于任意PDAM1，存在PDAM2，使得L(M2)=N(M1)。

证明要点：

(1)构造。设PDAM1=(Q，∑，Γ，δ1，q01，Z01，

Φ)

7.2.1PDA用空栈接受和用终止状态接受等价

取PDAM2=(Q∪{q02，qf}，∑，Γ∪{Z02}，δ，q02，Z02，{qf})其中Q∩{q02，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.1PDA用空栈接受和用终止状态接受等价

(2)证明L(M2)=N(M1)。x∈L(M2)

(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，ε，ε)。

x∈N(M1)。7.2.2PDA与CFG等价

定理7-3对于任意CFLL，存在PDAM，使得N(M)=L。

证明要点：先考虑识别L-{ε}的PDA，然后再考虑对ε的处理问题。

7.2.2PDA与CFG等价

(1)构造PDA。

设GNFG=(V，T，P，S)，使得L(G)=L-{ε}。取PDAM=({q}，T，V，δ，q，S，Φ)对于任意的A∈V，a∈T，

δ(q，a，A)={(q，γ)|A

aγ∈P}也就是说，(q，γ)∈δ(q，a，A)的充分必要条件是A

aγ∈P。

7.2.2PDA与CFG等价

(2)证明构造的正确性：N(M)=L-{ε}。施归纳于w的长度n，证明

(q，w，S)├Mn(q，ε，α)的充分必要条件为S

nwα。并且在假设结论对n=k成立，而证明结论对n=k+1成立时，取w=xa，|x|=k，a∈T。在证明必要性时有如下过程，充分性的证明过程是倒退回来。

7.2.2PDA与CFG等价

(q,w,S)=(q，xa，S)├Mk(q，a，γ)├M(q，ε，α)此时必定存在A∈V，γ=Aβ1，(q,β2)∈δ(q,a,A)。

(q,a,γ)=(q,a,Aβ1)├M(q,ε,β2β1)=(q，ε，α)。由(q，β2)∈δ(q，a，A)就可以得到A

aβ2∈P，再由归纳假设，得到

S

kxAβ1。合起来就有

S

kxAβ1

xaβ2β1。

7.2.2PDA与CFG等价

(3)考虑ε∈L的情况。

先按照(1)的构造方法构造出PDA M=({q}，T，V，δ，q，S，Φ)使得N(M)=L-{ε}。然后取

M1=({q，q0}，T，V∪{Z}，δ1，q0，Z，Φ)其中，q0≠q，Z

V，令δ1(q0，ε，Z)={(q0，ε)，(q，Z0)}，对于

(a，A)∈T×Vδ1(q，a，A)=δ(q，a，A)

7.2.2PDA与CFG等价

定理7-4

对于任意的PDAM，存在CFGG使得L(G)=N(M)。

证明要点：

(1)构造对应(q1，A1A2…An)∈δ(q，a，A)

难以用产生式[q，A]

a[q1，A1A2…An]模拟。同样也难以用[q，A]

a[q1，A1][q2，A2]…[qn，An]模拟。7.2.2PDA与CFG等价

PDA的移动(q1，A1A2…An)∈δ(q，a，A)需要用如下形式的产生式模拟。[q，A，qn+1]

a[q1，A1，q2][q2，A2，q3]…[qn，An，qn+1]q2，…，qn是分别对应PDA恰“处理完”A1进而处理A2，…，恰“处理完”An-1进而处理An的状态。当然就有了恰“处理完”An而进入的状态qn+1，这