模式识别讲义第二章.ppt

《模式识别讲义第二章.ppt》由会员分享，可在线阅读，更多相关《模式识别讲义第二章.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、模式识别讲义第二章现在学习的是第1页，共44页短语结构文法短语结构文法文法可以形式地定义为一个四元组G=(VN,VT,P,S)，其中：VN是非终结符或变量的有穷集合，VT是终结符或常数的有穷集合，P是产生式或重写规则的有穷集合，S在VN中，是起始符。VN VT=、V是集合VN VT，P由形式为的重写规则组成，其中是在V*VN V*中，是在V*中 现在学习的是第2页，共44页文法类型无约束文法：一个文法如果它的产生式的形式不受任何限制（除了串重写规则是有穷集合这个一般规定以外）则它就是无约束的。上下文有关文法上下文无关文法正则文法：产生式的形式是AaB或Aa，其中A和B在N中，以及a在中。现在学

2、习的是第3页，共44页上下文有关文法上下文有关文法的产生式的形式是A，其中和在V*中，在V*中，和A在VN中。术语“上下文有关”指的是仅当非终结符A出现在子串和的上下文之中时，才能被重写为这个事实。与其等价的定义是：对任何产生式，在中的符号的总数（非终结符和终结符）必须不少于在中的总数，也就是说，|。现在学习的是第4页，共44页上下文无关文法上下文无关文法的产生式的形式是A，其中A在VN中，在V+中。术语“上下文无关”是从这样的一个事实产生的：非终结符A可被重写为串，而与A出现在什么样的上下文中无关。现在学习的是第5页，共44页有限自动机一个（不确定的）有限自动机是一个五元组A=（，Q，q0，

3、F）规定的系统。其中 Q是状态的有穷集；是有穷输入字母表；是从Q到2Q的映射，是Q的全体子集的集合 q0在Q中，是起始态；F是终止或接受态，是Q的一个子集。现在学习的是第6页，共44页有限自动机的一般表示 起始态总是q0，由+来的输入串x放在带上，从带的最左边单元开始一个符号挨者一个符号对带进行扫描。从q0开始，扫描整个x串并遵循一个状态序列，最后停在F中的一个状态上，我们就说串x被接受了或者说被识别了 （带运动方向带运动方向）输入带输入带只读头有有穷穷状状态态集集 QQ有限自动机的一般表示有限自动机的一般表示现在学习的是第7页，共44页有限自动机举例有限自动机A=（，Q，q0，F），其中：Q

4、=q0，q1 =a，b F=q1，而定义为：（q0，a）=q0，（q0，b）=q1，（q1，a）=（q1，b）=。模式基元模式基元L L 电感电感C C 电容电容 a终结符终结符R R电阻电阻 b1.模式基元和终结符模式基元和终结符q0bq1a2.有限自动机的状态转移图有限自动机的状态转移图现在学习的是第8页，共44页有限自动机的确定化 不完全规定的自动机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)之中。

5、现在学习的是第9页，共44页习 题已知有限自动机如图：请将其确定化。q0bq1a有限自动机的状态转移图有限自动机的状态转移图现在学习的是第10页，共44页习题解答qAqBq0qbb 确定的有限自动机aababa现在学习的是第11页，共44页正则文法有限自动机正则文法G=(N,P,，X0)，求对应有限自动机Af=(,Q,q0,F)的方法如下：假设非终结符N=X0,X1,X2,Xn组成，X0是起始符，那么，状态集Q=q0,q1,qn,qn+1组成。qi和Xi相对应，0in，qn+1是个符加态。集合F就是qn+1。而输入符号集和G中的终结符集相同。映射规则定义，即:对于每个i和j，0in，0jn，如

6、果XiaXj在P中，则(qi，a)包括qj；如果Xia在P中，则(qi，a)包括qn+1。现在学习的是第12页，共44页习 题给定正则文法G=(S,a,b,P,S)，其产生式为SaS Sb。构造一个能识别L(G)的有限自动机Af=(,Q,q0,F)现在学习的是第13页，共44页有限自动机正则文法一个有限自动机Af=(Q,q0,F)，则我们可以规定出一个正则文法G=(N,P,X0)，为此，令N和状态集Q对应，起始非终结符X0和q0对应，而G的产生式可用下述方法得到：1、如果qj在(qi,a)中，就有产生式XiaXj2、如果F中的一个状态在(qi,a)内，就有产生式Xia现在学习的是第14页，共4

7、4页习 题已给有限自动机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页等价的上下文无关文法 如果如果 L(G1)=L(G2)那么，文法那么，文法G1和和G2是等价的。是等价的。等价变换：等价变换：1 1、无循环的文法无循环的文法 2、没没有有无无用用符符号号或或产产生生式式的的文文法法 3 3、具有标准形产生式的文法具有标准形产生式的文法 现在学习

8、的是第16页，共44页一个循环是一个形式为一个循环是一个形式为 的导出，其中的导出，其中A A是在是在NN中。如果对任何非终结符中。如果对任何非终结符A A都不存在都不存在 的导出式，则这个文法就是无循环的。当的导出式，则这个文法就是无循环的。当且仅当存在以下这样一组只包含单个非终且仅当存在以下这样一组只包含单个非终结符的产生式：结符的产生式：A AB B1 1，B B1 1B B2 2，B Bn-n-1 1B Bn n，B Bn nA A，n n00时，才能出现循环。这时，才能出现循环。这样，如果把所有形式为样，如果把所有形式为A AB B的产生式都去掉的产生式都去掉，循环就会被删除。，循环

9、就会被删除。无循环的文法无循环的文法 AA+AA+现在学习的是第17页，共44页无循环的文法无循环的文法变换（变换（1）对对某某个个具具体体的的非非终终结结符符A，按按下下述述递递归归规规则则定定义非终结符集义非终结符集K（A）：(i)K0(A)=A(ii)K1(A)=K0(A)B|AB是是P中中的的一一个个产产生生式式(iii)Ki+1(A)=Ki(A)C|对对Ki(A)中中的的某某个个B来来说说，BC是在是在P中的一个产生式中的一个产生式，i=1,2,3从从Ki(A)构构成成Ki+1(A)，如如果果不不增增加加任任何何新新的的非非终结符，我们有终结符，我们有K(A)=Ki(A)=Ki+1(

10、A)现在学习的是第18页，共44页在对在对NN中的每个非终结符中的每个非终结符A A确定了集合确定了集合K K(A A)以后，我们用定义等价文法以后，我们用定义等价文法G G2 2=(N,p =(N,p ,S),S)的方法删除所有的形式为的方法删除所有的形式为A AB B的产生式的产生式（从而删除了任何循环）。可根据下述要求来（从而删除了任何循环）。可根据下述要求来确定等价文法确定等价文法G G2 2的产生式：对非终结符的产生式：对非终结符A A和和B B来说，如果来说，如果B B是在是在K K(A A)中，并且在中，并且在P P中存在中存在一个产生式一个产生式 B B，其中，其中不是单个的非

11、终不是单个的非终结符，那么就把产生式结符，那么就把产生式A A 放在放在 p p 中中。无循环的文法无循环的文法变换（变换（2）现在学习的是第19页，共44页习 题已知：文法G1=(S，A，B，a，b，P，S)，有产生式 SaSA，SA，ABAb，AB，BaS，Bb 求其等价文法G2，使其不含循环。现在学习的是第20页，共44页非终结符A是无用的条件是：（i）不存在满足导出式 的终结符串x；或（ii）不存在满足导出式 的句形A。如果A是无用的，那么可以把所有的形式为A(对任何的)的产生式，或所有形式为BA（对任何的非结符B）的产生式删除，而不影响L(G1)。没有无用符号或产生式的文法没有无用符

12、号或产生式的文法 A=xG1*S=aAG1*现在学习的是第21页，共44页集合J(G1)包括，且仅包括那些至少能推导出一个终结符串的非终结符用以下的方法由Ji(G1)构成Ji+1(G1)，0i，（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页习 题已知文法G1=(S，A，B，a，b，P，S)，具

13、有产生式 SaBA，SbA，AaA，Ab，BaAB 消除G1中导不出终结符的无用的非终结符，求其等价文法G2。现在学习的是第23页，共44页消除不可到达的A从起始符S出发可达到的非终结符的集合记作R(S)。由Ri(S)构造Ri+1(S)0i,具体的方法如下：（i）R0(S)=S（ii）Ri+1(S)=Ri(S)A|A在N中，对Ri(S)中的某个B，存在一个产生式BA,i=0,1,2,，当Ri+1(S)=Ri(S)时，构造过程终止G1等价的文法是G2=(N ，P ，S)，其中，N=R(S)，P 只包括P的一部分产生式，在这部分产生式中，只有N中的元素才出现在其左边或右边 现在学习的是第24页，共

14、44页习 题假设文法G1=(S，A，B，C，a，b，P，S)，以及产生式 SaAA，AaAb，AaCA，Bb，BAa，Cb。消除G1中不可到达无用的非终结符，求其等价文法G2。现在学习的是第25页，共44页具有具有乔姆斯基范式乔姆斯基范式的文法的文法 用乔姆斯基范式表示的产生式或者是ABC形式（A，B，C在N中），或者是Aa的形式（A在N中，a在中），变换时产生式A12n替换为：AY1Y2n Y2nY2Y3n Yn-1,n Yn-1Yn 带下标的Y是非终结符。如果，i是非终结符，我们令Yi等于i；如果i是终结符，我们令Yi是一个新的非终结符，并引入产生式Yii。现在学习的是第26页，共44页习

15、 题假设文法G2=(S，A，B，a，b，P，S)具有产生式 SBA，Aa，AabABa，Bb。将其产生式转换为乔姆斯基范式，求其等价文法G2。现在学习的是第27页，共44页习题解答新非终结符集是 S,A,B,Y1，Y2345，Y2，Y345，Y45，Y5 乔姆斯基范式产生式是：SBA，Aa，Bb AY1Y2345 Y1 aY2345Y2Y345 Y2 bY345 AY45 Y45 BY5 Y5 a 现在学习的是第28页，共44页具有具有格雷巴赫范式范式的文法的文法如果文法的每个产生式都是Aa形式的，其中A是非终结符，a是终结符，是在N*中，那么这个文法是格雷巴赫（Greibach）范式的令重写

16、某一特定非终结符A的产生式的整个集合是A1，A2，An；那么，G1中的形式为BA的任何产生式可以用产生式集B1，B2，Bn代替 现在学习的是第29页，共44页如果一种文法，其中至少存在一个非终结符A，对于(N)*中的，能使 成立，那么称这个文法为右递归的。相似的，如果有一种文法，其中存在一个非终结符A，对(N)*中的，能使 成立，那么称这种文法为左递归的 递归定义A=A+A=A+现在学习的是第30页，共44页消除左递归把重写非终结符A的产生式集分为两个子集。第一个子集产生式的右面是以A本身开始的，如 AA1,AA2,AAn；第二个子集是那些右面不是从A开始的，如 A1,A2,Am。从这些产生式

17、导出的句形是在集合1,m 1,n*中（i）A1,A2,Am（ii）A1A,A2A,AmA，其中A是新的非终结符。（iii）A1，A2，An（iv）A1 A，A2 A，An A 现在学习的是第31页，共44页格雷巴赫范式变换范式变换假设G1已经是乔姆斯基范式 非终结符集记作A1，A2，Am，其中下标是任意分配的。调整产生式，以保证如果有AiAj，则ji。我们按i=1，2，m增加的次序进行调整。每个产生式都是Ak+1a形式，或者Ak+1A1形式，其中a在中，在N*中，以及lk+1 对每个Ak+1Ak+1这样的产生式删除左递归 现在学习的是第32页，共44页习 题假设文法G2=(S，A，B，a，b，

18、P，S)具有产生式 SBA，Aa，AabABa，Bb。将其产生式转换格雷巴赫为范式，求其等价文法G2。现在学习的是第33页，共44页下推自动机PDA 下推自动机它可形式地定义为7元组：M=（,Q,q0,Z0,F），其中Q、q0及F和有限自动机中的定义相同。是 有 穷 下 推 字 母 表，是 从Q(U)到Q*的有穷子集的映射，Z0在中，是下推表的初始符。现在学习的是第34页，共44页下推自动机的一般表示（带运动方向带运动方向）输入输入带带只读头有有穷穷状状态态集集 QQ下推自动机的一般表示下推自动机的一般表示读写头读写头下推表下推表机器开始运行时状态是q0堆栈上只有Z0输入带上包含来自+的串x，

19、从左到右逐个地扫描串x的每个符号。映射规定下一个状态，以及规定*中哪个串能代替堆栈顶上的单字符。如果机器从q0和堆栈顶上Z0开始，扫描全部x后停在F的一个状态上，则称串x被PDA接受了。现在学习的是第35页，共44页下推自动机识别的语言L(M)=x|x在+中，从状态q0及堆栈顶的Z0开始，扫描全部x 后M停在F的一个状态上。L(M)=x|x在+中，M从q0及Z0开始，扫描全部x 后M停在空栈上。现在学习的是第36页，共44页下推自动机举例用空堆栈接受这些句子的PDA是个不确定的自动机M=（a,b,c,d，q0，S,A,B,C,D,q0,S,），其中映射定义如下：(q0,c,S)=(q0,DAB

20、),(q0,C)，(q0,d,C)=(q0,)(q0,a,D)=(q0,)(q0,b,B)=(q0,)(q0,a,A)=(q0,DAB),(q0,C)识别的语言:x|x=candbn，n0 现在学习的是第37页，共44页上下文无关文法下推自动机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页习 题G=(S,A，a,b,c,d，P，S)，其中产生式为：ScA,Aa

21、Ab,Ad。请给出下推自动机 现在学习的是第39页，共44页习 题格雷巴赫范式文法是G1=(A,S,B,a,b,c,d,P,S),其产生式为：ScA，AaAB，Ad，Bb构造下推自动机M现在学习的是第40页，共44页确定的下推自动机DPDA是一个七元组Ap=（，Q，q0，Z0，F），其中Q，Z0的意义和以前相同。对于Q中的全部q，中的全部a，以及中的全部Z来说，映射遵守如下约束1、（q0,a,Z）至多包含一个元素；2、（q0,Z）至多包含一个元素；3、如果（q0,Z）非空，则对中的全部a来说，（q0,a,Z）为空 现在学习的是第41页，共44页图灵机定义一个图灵机T可表达成一个六元式：T=（，

22、Q，,，q0，F）其中 Q:状态有穷集，:带上符号有穷集，其中有一个是空白符号B，为的一个不包括B的子集，是输入符号有穷集，q0Q为起始状态，F Q是终止状态集，是Q到Q(一B)L,R的一个映射。现在学习的是第42页，共44页图灵机说明图灵机的一个格局可以用三元式（q，,i）表示，其中qQ，(一B)*，即带上非空白部分,i是从T的读写头到左端的距离。设（q，A1A2An,i）是T的一个格局，lin l，如果（q，Ai）=（p，X，R），1in，则T的运行即指定为T的基本移动，可以表示为 即,T在输入带的第i个方格上写入符号X，并向右移动一个方格。如果（q，Ai）=（p，X，L），2in，则 现在学习的是第43页，共44页线性界限自动机一个线性界限自动机M可表达成一个六元式：M=（，Q，,，q0，F）Q是状态有穷集，是带上符号有穷集，是输入符号有穷集，q0Q是起始状态，F Q是终止状态集，是从Q到子集QL，R的一个映射。包含两个特殊符号，用和表示，它们分别是输入链的左端和右端的结束标志，其作用是防止读写头离开带上输入链出现的部分。现在学习的是第44页，共44页