模式识别讲义第二章

模式识别讲义第二章第1页，共44页，2023年，2月20日，星期五短语结构文法文法可以形式地定义为一个四元组G=(VN,VT,P,S)，其中：VN是非终结符或变量的有穷集合，VT是终结符或常数的有穷集合，P是产生式或重写规则的有穷集合，S在VN中，是起始符。VN∩VT=Φ、V是集合VN∪VT

，P由形式为α→β的重写规则组成，其中α是在V*VNV*中，β是在V*中第2页，共44页，2023年，2月20日，星期五文法类型无约束文法：一个文法如果它的产生式的形式不受任何限制（除了串重写规则是有穷集合这个一般规定以外）则它就是无约束的。

上下文有关文法上下文无关文法正则文法：产生式的形式是A→aB或A→a，其中A和B在N中，以及a在Σ中。第3页，共44页，2023年，2月20日，星期五上下文有关文法上下文有关文法的产生式的形式是θAσ→θρσ，其中θ和σ在V*中，ρ在V*中，和A在VN中。术语“上下文有关”指的是仅当非终结符A出现在子串θ和σ的上下文之中时，才能被重写为ρ这个事实。与其等价的定义是：对任何产生式α→β，在β中的符号的总数（非终结符和终结符）必须不少于在α中的总数，也就是说，|α|≤|β|。

第4页，共44页，2023年，2月20日，星期五上下文无关文法上下文无关文法的产生式的形式是A→α，其中A在VN中，α在V+中。术语“上下文无关”是从这样的一个事实产生的：非终结符A可被重写为串α，而与A出现在什么样的上下文中无关。

第5页，共44页，2023年，2月20日，星期五有限自动机一个（不确定的）有限自动机是一个五元组A=（Σ，Q，δ，q0，F）规定的系统。其中

Q是状态的有穷集；

Σ是有穷输入字母表；

δ是从Q×Σ到2Q的映射，是Q的全体子集的集合

q0在Q中，是起始态；

F是终止或接受态，是Q的一个子集。第6页，共44页，2023年，2月20日，星期五有限自动机的一般表示

起始态总是q0，由∑+来的输入串x放在带上，从带的最左边单元开始一个符号挨者一个符号对带进行扫描。从q0开始，扫描整个x串并遵循一个状态序列，最后停在F中的一个状态上，我们就说串x被接受了或者说被识别了（带运动方向）输入带只读头有穷状态集Q有限自动机的一般表示第7页，共44页，2023年，2月20日，星期五有限自动机举例有限自动机A=（Σ，Q，δ，q0，F），其中：Q={q0，q1}Σ={a，b}F={q1}，而δ定义为：

δ（q0，a）={q0}，δ（q0，b）={q1}，δ（q1，a）=δ（q1，b）=φ。

模式基元L电感C电容

a终结符R电阻

b1.模式基元和终结符q0bq1a2.有限自动机的状态转移图第8页，共44页，2023年，2月20日，星期五有限自动机的确定化

不完全规定的自动机A=({a,b},{q0,q1},δ,q0,{q1}),构造确定的自动机A’=(∑’,Q’,δ’,q0’,F’)

其中：Q’=2Q。起始态q0’={q0}，终止态集为F’={q’|q’在2Q

中，q’至少包含F的一个状态}。δ’:δ’(q’，a)={p|p在Q中，对于子集q’中的某状态q来说p在δ(q，a)之中}。第9页，共44页，2023年，2月20日，星期五习题已知有限自动机如图：请将其确定化。q0bq1a有限自动机的状态转移图第10页，共44页，2023年，2月20日，星期五习题解答qAqBq0qφbb确定的有限自动机aababa第11页，共44页，2023年，2月20日，星期五正则文法→有限自动机正则文法G=(N,∑,P,，X0)，求对应有限自动机Af=(∑,Q,δ,q0,F)的方法如下：假设非终结符N={X0,X1,X2,……,Xn}组成，X0是起始符，那么，状态集Q={q0,q1…,qn,qn+1}组成。qi和Xi相对应，0≤i≤n，qn+1是个符加态。集合F就是{qn+1}。而输入符号集和G中的终结符集相同。δ映射规则定义，即:对于每个i和j，0≤i≤n，0≤j≤n，如果Xi→aXj在P中，则δ(qi，a)包括qj；如果Xi→a在P中，则δ(qi，a)包括qn+1。第12页，共44页，2023年，2月20日，星期五习题给定正则文法G=({S},{a,b},P,S)，其产生式为S→aSS→b。构造一个能识别L(G)的有限自动机Af=(∑,Q,δ,q0,F)

第13页，共44页，2023年，2月20日，星期五有限自动机→正则文法一个有限自动机Af=(Q,∑,δ,q0,F)，则我们可以规定出一个正则文法G=(N,∑,P,X0)，为此，令N和状态集Q对应，起始非终结符X0和q0对应，而G的产生式可用下述方法得到：1、如果qj在δ(qi,a)中，就有产生式Xi→aXj2、如果F中的一个状态在δ(qi,a)内，就有产生式Xi→a第14页，共44页，2023年，2月20日，星期五习题已给有限自动机Af=({0,1},{q0,q1,q2},δ,q0,{q2})，其状态转移图如图4.4所示。状态映射为：δ(q0,0)={q2}，

δ(q0,1)={q1}，

δ(q1,0)={q2}，

δ(q1,1)={q0}，

δ(q2,0)={q2}，

δ(q2,1)={q1}。

求其正则文法。q0q1110010图4.4有限自动机q2第15页，共44页，2023年，2月20日，星期五等价的上下文无关文法

如果L(G1)=L(G2)

那么，文法G1和G2是等价的。

等价变换：

1、无循环的文法

2、没有无用符号或产生式的文法

3、具有标准形产生式的文法

第16页，共44页，2023年，2月20日，星期五一个循环是一个形式为的导出，其中A是在N中。如果对任何非终结符A都不存在

的导出式，则这个文法就是无循环的。当且仅当存在以下这样一组只包含单个非终结符的产生式：A→B1，B1→B2，…，Bn-1→Bn，Bn→A，n>0时，才能出现循环。这样，如果把所有形式为A→B的产生式都去掉，循环就会被删除。

无循环的文法

A＝＞A+A＝＞A+第17页，共44页，2023年，2月20日，星期五无循环的文法变换（1）对某个具体的非终结符A，按下述递归规则定义非终结符集K（A）：(i)K0(A)={A}(ii)K1(A)=K0(A)∪{B|A→B是P中的一个产生式}(iii)Ki+1(A)=Ki(A)∪{C|对Ki(A)中的某个B来说，B→C是在P中的一个产生式}，i=1,2,3…从Ki(A)构成Ki+1(A)，如果不增加任何新的非终结符，我们有K(A)=Ki(A)=Ki+1(A)第18页，共44页，2023年，2月20日，星期五在对N中的每个非终结符A确定了集合K(A)以后，我们用定义等价文法G2=(N,∑,p,S)的方法删除所有的形式为A→B的产生式（从而删除了任何循环）。可根据下述要求来确定等价文法G2的产生式：对非终结符A和B来说，如果B是在K(A)中，并且在P中存在一个产生式B→β，其中β不是单个的非终结符，那么就把产生式A→β放在p中。

无循环的文法变换（2）^^第19页，共44页，2023年，2月20日，星期五习题已知：文法G1=({S，A，B}，{a，b}，P，S)，有产生式{S→aSA，S→A，A→BAb，A→B，B→aS，B→b}

求其等价文法G2，使其不含循环。第20页，共44页，2023年，2月20日，星期五非终结符A是无用的条件是：（i）不存在满足导出式的终结符串x；或

（ii）不存在满足导出式的句形αAβ。如果A是无用的，那么可以把所有的形式为A→θ(对任何的θ)的产生式，或所有形式为B→ωAσ（对任何的非结符B）的产生式删除，而不影响L(G1)。没有无用符号或产生式的文法

A=>xG1*S=>aAβG1*第21页，共44页，2023年，2月20日，星期五集合J(G1)包括，且仅包括那些至少能推导出一个终结符串的非终结符 用以下的方法由Ji(G1)构成Ji+1(G1)，0≤i，（i）J0(G1)=φ（ii）Ji+1(G1)=Ji(G1)∪{A|存在有一个产生式A→α，α在(Ji(G1)∪∑)*中}，i=0,1,2,…当Ji+1(G1)=Ji(G1)时，上述构成过程结束。G1等价的文法是G2=(N，∑，P，S)，其中，N=J(G1)，和P只包括那些来自P，并和N中的元素有关的那些产生式

消除不能导出终结符的A^^^^^第22页，共44页，2023年，2月20日，星期五习题已知文法G1=({S，A，B}，{a，b}，P，S)，具有产生式{S→aBA，S→bA，A→aA，A→b，B→aAB}

消除G1中导不出终结符的无用的非终结符，求其等价文法G2。第23页，共44页，2023年，2月20日，星期五消除不可到达的A从起始符S出发可达到的非终结符的集合记作R(S)。由Ri(S)构造Ri+1(S)0≤i,具体的方法如下：（i）

R0(S)={S}（ii）

Ri+1(S)=Ri(S)∪{A|A在N中，对Ri(S)中的某个B，存在一个产生式B→σAγ},i=0,1,2,…，当Ri+1(S)=Ri(S)时，构造过程终止G1等价的文法是G2=(N，∑，P，S)，其中，N=R(S)，P只包括P的一部分产生式，在这部分产生式中，只有N中的元素才出现在其左边或右边^^^^^第24页，共44页，2023年，2月20日，星期五习题假设文法G1=({S，A，B，C}，{a，b}，P，S)，以及产生式{S→aAA，A→aAb，A→aCA，B→b，B→Aa，C→b}。消除G1中不可到达无用的非终结符，求其等价文法G2。

第25页，共44页，2023年，2月20日，星期五具有乔姆斯基范式的文法

用乔姆斯基范式表示的产生式或者是A→BC形式（A，B，C在N中），或者是A→a的形式（A在N中，a在∑中），变换时产生式A→θ1θ2…θn替换为：

A→Y1Y2……n

Y2……n→Y2Y3……n

…… Yn-1,n→Yn-1Yn

带下标的Y是非终结符。如果，θi是非终结符，我们令Yi等于θi；如果θi是终结符，我们令Yi是一个新的非终结符，并引入产生式Yi→θi。第26页，共44页，2023年，2月20日，星期五习题假设文法G2=({S，A，B}，{a，b}，P，S)具有产生式{S→BA，A→a，A→abABa，B→b}。将其产生式转换为乔姆斯基范式，求其等价文法G2。第27页，共44页，2023年，2月20日，星期五习题解答新非终结符集是{S,A,B,Y1，Y2345

，Y2，Y345

，Y45

，Y5}乔姆斯基范式产生式是：

S→BA，A→a，B→b

A→Y1Y2345

Y1→a Y2345→Y2Y345

Y2→b Y345→AY45

Y45→BY5

Y5→a

第28页，共44页，2023年，2月20日，星期五具有格雷巴赫范式的文法如果文法的每个产生式都是A→aα形式的，其中A是非终结符，a是终结符，α是在N*中，那么这个文法是格雷巴赫（Greibach）范式的令重写某一特定非终结符A的产生式的整个集合是{A→γ1，A→γ2，…，A→γn}；那么，G1中的形式为B→σAθ的任何产生式可以用产生式集{B→σγ1θ，B→σγ2θ，…，B→σγnθ}代替

第29页，共44页，2023年，2月20日，星期五如果一种文法，其中至少存在一个非终结符A，对于(N∪∑)*中的γ，能使成立，那么称这个文法为右递归的。相似的，如果有一种文法，其中存在一个非终结符A，对(N∪∑)*中β的，能使成立，那么称这种文法为左递归的

递归定义A=>γA

+A=>Aβ

+第30页，共44页，2023年，2月20日，星期五消除左递归把重写非终结符A的产生式集分为两个子集。第一个子集产生式的右面是以A本身开始的，如{A→Aγ1,A→Aγ2,…,A→Aγn}；第二个子集是那些右面不是从A开始的，如{A→α1,A→α2,…,A→αm}。从这些产生式导出的句形是在集合{α1,…,αm}{γ1,…,γn}*中（i）A→α1,A→α2,…,A→αm（ii）A→α1A’,A→α2A’,…,A→αmA’，其中A’是新的非终结符。（iii）A’→γ1，A’→γ2，…，A’→γn

（iv）A’→γ1A’，A’→γ2A’，…，A’→γnA’第31页，共44页，2023年，2月20日，星期五格雷巴赫范式变换假设G1已经是乔姆斯基范式非终结符集记作{A1，A2，…，Am}，其中下标是任意分配的。调整产生式，以保证如果有Ai→Ajθ，则j>i。我们按i=1，2，…，m增加的次序进行调整。每个产生式都是Ak+1→aα形式，或者Ak+1→A1α形式，其中a在∑中，α在N*中，以及l≥k+1对每个Ak+1→Ak+1α这样的产生式删除左递归

第32页，共44页，2023年，2月20日，星期五习题假设文法G2=({S，A，B}，{a，b}，P，S)具有产生式{S→BA，A→a，A→abABa，B→b}。将其产生式转换格雷巴赫为范式，求其等价文法G2。第33页，共44页，2023年，2月20日，星期五下推自动机PDA

下推自动机它可形式地定义为7元组：M=（∑,Q,Γ,δ,q0,Z0,F），其中Q、∑、q0及F和有限自动机中的定义相同。Γ是有穷下推字母表，δ是从Q×(∑U{λ})×Γ到Q×Γ*的有穷子集的映射，Z0在Γ中，是下推表的初始符。第34页，共44页，2023年，2月20日，星期五下推自动机的一般表示（带运动方向）输入带只读头有穷状态集Q下推自动机的一般表示读写头下推表机器开始运行时状态是q0堆栈上只有Z0输入带上包含来自∑+的串x，从左到右逐个地扫描串x的每个符号。δ映射规定下一个状态，以及规定Γ*中哪个串能代替堆栈顶上的单字符。

如果机器从q0和堆栈顶上Z0开始，扫描全部x后停在F的一个状态上，则称串x被PDA接受了。第35页，共44页，2023年，2月20日，星期五下推自动机识别的语言L(M)={x|x在Σ+中，从状态q0及堆栈顶的Z0开始，扫描全部x后M停在F的一个状态上}。Lλ(M)={x|x在Σ+中，M从q0及Z0开始，扫描全部x后M停在空栈上}。

第36页，共44页，2023年，2月20日，星期五下推自动机举例用空堆栈接受这些句子的PDA是个不确定的自动机M=（{a,b,c,d}，{q0}，{S,A,B,C,D},δ,q0,S,Φ），其中δ映射定义如下：δ(q0,c,S)={(q0,DAB),(q0,C)}，δ(q0,d,C)={(q0,λ)}δ(q0,a,D)={(q0,λ)}δ(q0,b,B)={(q0,λ)}δ(q0,a,A)={(q0,DAB),(q0,C)}识别的语言:{x|x=candbn，n≥0}

第37页，共44页，2023年，2月20日，星期五上下文无关文法→下推自动机G=(N,Σ,P,S)是一个上下文无关文法。构造使L(G)=L(Ap)的下推自动机。我们定义M=({q0},Σ,N∪Σ,δ,q0,S,Φ)，按下述方式从产生式得到δ映射：

（1）如果A→α在P中，则δ（q0,λ,A）包含(q0,α)；（2）对每个在Σ中的终结符a，有δ（q0,a,a）={(q0,λ)}

第38页，共44页，2023年，2月20日，星期五习题G=({S,A}，{a,b,c,d}，P，S)，其中产生式为：

{S→cA,A→aAb,A→d}。 请给出下推自动机

第39页，共44页，2023年，2月20日，星期五习题格雷巴赫范式文法是G1=({A,S,B},{a,b,c,d},P,S),其产生式为：S→cA，A→aAB，A→d，B→b

构造下推自动机M第40页，共44页，2023年，2月20日，星期五确定的下推自动机DPDA是一个七元组Ap=（∑，Q，Γ，δ，q0，Z0，F）