模式识别讲义第二章.ppt

《模式识别讲义第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、句法模式识别与形式语言短语结构文法正规语言与有限自动机等价的上下文无关文法2型语言与下推自动机短语结构文法文法可以形式地定义为一个四元组G=(VN,VT,P,S)，其中：VN是非终结符或变量的有穷集合，VT是终结符或常数的有穷集合，P是产生式或重写规则的有穷集合，S在VN中，是起始符。VN∩VT=Φ、V是集合VN∪VT，P由形式为α→β的重写规则组成，其中α是在V*VNV*中，β是在V*中文法类型无约束文法：一个文法如果它的产生式的形式不受任何限制（除了串重写规则是有穷集合这个一般规定以外）则它就是无约束的。上下文有关文法上

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

3、α

4、≤

5、β

6、。上下文无关文法上下文无关文法的产生式的形式是A→α，其中A在VN中，α在V+中。术语“上下文无关”是从这样的一个事实产

7、生的：非终结符A可被重写为串α，而与A出现在什么样的上下文中无关。有限自动机一个（不确定的）有限自动机是一个五元组A=（Σ，Q，δ，q0，F）规定的系统。其中Q是状态的有穷集；Σ是有穷输入字母表；δ是从Q×Σ到2Q的映射，是Q的全体子集的集合q0在Q中，是起始态；F是终止或接受态，是Q的一个子集。有限自动机的一般表示起始态总是q0，由∑+来的输入串x放在带上，从带的最左边单元开始一个符号挨者一个符号对带进行扫描。从q0开始，扫描整个x串并遵循一个状态序列，最后停在F中的一个状态上，我们就说串x被接受了或者说被识别了（带运动方

8、向）输入带只读头有穷状态集Q有限自动机的一般表示有限自动机举例有限自动机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.有限自动机的状态转移图有限自动机的确定化不完全规定的自动机A=({a,b},{q0,q1},δ,q0,{q1}),构造确定的自动机A’=(∑’,Q’,δ’,q0’,F’)其中：Q’=2Q。起始态q0’={

9、q0}，终止态集为F’={q’

10、q’在2Q中，q’至少包含F的一个状态}。δ’:δ’(q’，a)={p

11、p在Q中，对于子集q’中的某状态q来说p在δ(q，a)之中}。习题已知有限自动机如图：请将其确定化。q0bq1a有限自动机的状态转移图习题解答qAqBq0qφbb确定的有限自动机aababa正则文法→有限自动机正则文法G=(N,∑,P,，X0)，求对应有限自动机Af=(∑,Q,δ,q0,F)的方法如下：假设非终结符N={X0,X1,X2,……,Xn}组成，X0是起始符，那么，状态集Q={q0,q1…,qn,qn+1}组成。

12、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。习题给定正则文法G=({S},{a,b},P,S)，其产生式为S→aSS→b。构造一个能识别L(G)的有限自动机Af=(∑,Q,δ,q0,F)有限自动机→正则文法一个有限自动机Af=(Q,∑,δ,q0,F)，则我们可以规定出一个正则文法G=(N,∑,P,X0)，

13、为此，令N和状态集Q对应，起始非终结符X0和q0对应，而G的产生式可用下述方法得到：1、如果qj在δ(qi,a)中，就有产生式Xi→aXj2、如果F中的一个状态在δ(qi,a)内，就有产生式Xi→a习题已给有限自动机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有限自动机q

14、2等价的上下文无关文法如果L(G1)=L(G2)那么，文法G1和G2是等价的。等价变换：1、无循环的文法2、没有无用符号或产生式的文法3、具有标准形产生式的文法一个循环是一个形式为的导出，其中A是在N中。如果对任何非终结符A都不存在的导出式，则这个文法就是无循环的。当且仅当存在以下这样一组