模式识别习题参考3-教材第6and7章

第5章 句法模式识别习题解答6.1 用链码法描述59五个数字。20134567解：用弗利曼链码表示，基元如解图6.1所示：解图6.1 弗利曼链码基元数字59的折线化和量化结果如解图6.2所示： 解图6.2 数字59的折线化和量化结果各数字的链码表示分别为：“5”的链码表示为；“6”的链码表示为；“7”的链码表示为；“8”的链码表示为；“9”的链码表示为。6.2 定义所需基本基元，用PDL法描述印刷体英文大写斜体字母“H”、“K”和“Z”。解：设基元为：bcade用PDL法得到“H”的链描述为；“K”的链描述为；“Z”的链描述为。6.3 设有文法，和P分别为， ，写出三个属于的句子。解：以上句子ab，abba，abab，ba，baab，baba均属于。6.4 设有文法，其中，P的各生成式为，问是否属于语言？解：由可知属于语言。6.5 写出能产生图示树的扩展树文法，设基元a，b分别为“”和“”，它所描述的模式是什么？ a$ababaaababA3A4A2解：1. 写出生成树的扩展树文法生成式集：A5A9A6(6)A7A8A12A10A112. 检查非终止符的等价性。查得。删除和及其后代生成式，其余生成式中的和用代替，合并后得到A9A6A5(6)A2A10A2A4A2A3A4A23. 建立起始产生式。将中的用S代替得到： 设推断的扩展树文法为，由以上推断得：，A9A6A5(6)A2A10A2A4A2A3P的各生成式为aabbbbaaaaa$ 当基元a，b分别为“”和“”时，它所描述的模式如解图6.3所示：解图6.3 描述的模式6.6 已知的正样本集，试推断出余码文法。解：设余码文法为。(1) 由得的终止符集。(2) 求的全部余码，组成非终止符集。的全部余码为， ， ，等号右边相同的合并，非空余码标以符号组成非终止符集：，所以。(3) 建立生成式集P。由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；所以余码文法为 ， P：， ，6.7 设文法，其中，P的各生成式为，设待识别链，试用填充树图法的顶下法分析x是否属于?解：(1) 从S开始考察P中的、式：若选，则结果为x=1，排除；若选，导出的x末位必为1，与题不符，排除；S1BA0A00AS1BA0A0AS1BA0AS1BASB(a) (b) (c) (d) (e) 选式，如解图6.4(a)所示。解图6.4 填充树图过程(2) 填充目标为B，考察、均可填充，先试，如解图6.4(b)所示。若不行，再返回用式。(3) 此时填充目标为A，考察、。若选，导出的x为 2位，与题不符，排除。选式，如解图6.4(c)所示。(4) 类似地，得到图6.4所示各步结果，树叶为1000。 故x属于。6.8 设上下文无关文法，P中生成式的乔姆斯基范式为，用CYK分析法分析链是否为该文法的合法句子。解：待识别链为5位，构造5行5列的三角形分析表，如解图6.5所示。解图6.5 分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24 求表中元素的值：(1) 令，求，。 各子链为0，1，0，0，1。 对于，； 对于，； 对于，； 对于，。 对于，。(2) 令，求，。各子链为01，10，00，01。对于，因有和，故；对于，有，故。对于，有，故。对于，有和，故；(3) 令，求，。各子链为010，100，001。对于，因有，；和，。故。类似地有，。填表结果如解图6.6所示。解图6.6 CYK分析表填表结果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S 因为S在中，所以。6.9 已知正则文法，其中，P的各生成式为，构成对应的有限态自动机，画出自动机的状态转换图。解：设有限态自动机，由A与G的对应关系得：由，有；由，有； 由，有。故有限态自动机为，：，abSBFaa状态转换图如解图6.7所示：解图 6.7 自动机的状态转换图6.10 已知有限态自动机，其中，A的状态转换图如图6.15所示，求A对应的正则文法G。图6.15 状态转换图11000011解：设正则文法为，由G与A的对应关系得：；根据状态转换图有：P：因，有； 因，有；因，有；而，故；因，有；因，有；因，有；而，故；因，有；因，有。由此得正则文法为，P：， ，6.11 已知上下文无关文法，其中，P的各生成式为，写出文法G的格雷巴赫范式，构成相应的下推自动机。解：文法的格雷巴赫范式为：， P：， 设相应的下推自动机为，其中，转换规则： 因P中有，故 因P中有，故 因P中有，故 因P中有，故即下推自动机为：，P：，第6章 模糊模式识别法习题解答7.1 试分别说明近似性、随机性和含混性与模糊性在概念上的相同处与不同处。解：(1) 近似性与模糊性的异同 共同点：描述上的不精确性。 区别：不精确性的根源和表现形式不同。a) 近似性：问题本身有精确解，描述时的不精确性源于认识条件的局限性和认识过程发展的不充分性。 b) 模糊性：问题本身无精确解，描述的不精确性来源于对象自身固有的性态上的不确定性。(2) 随机性与模糊性的异同 共同点：不确定性。 区别：模糊性和随机性所表现出的不确定性的性质不同。a) 模糊性：表现在质的不确定性。是由于概念外延的模糊性而呈现出的不确定性。b) 随机性：是外在的不确定性。是由于条件不充分，导致条件与事件之间不能出现确定的因果关系，事物本身的性态(性质、状态、特征等)和类属是确定的。 c) 排中律：即事件的发生和不发生必居且仅居其一，不存在第三种现象。随机性遵守排中律，模糊性不遵守，它存在着多种，甚至无数种中间现象。(3) 含混性与模糊性的异同 共同点：不确定性。 区别：a) 含混性：由信息不充分（二义性）引起，一个含混的命题即是模糊的，又是二义的。一个命题是否带有含混性与其应用对象或上下文有关。b) 模糊性：是质的不确定性。7.2 已知论域，和为X中的模糊集合，分别为 （1）求，和；（2）求。解：（1）由有=由有由有（2）=7.3 已知两个模糊集合， 试验证截集的两个性质：1）；2）。解：（1）验证左边： 右边：，有所以：左边 = 右边。（2）验证左边： 右边：，有所以：左边 = 右边。7.4 判断模糊矩阵是否是传递模糊矩阵。解：由计算结果可见不成立，故R不是传递模糊矩阵。7.5 证明7.5节定理1：对阶模糊等价矩阵R，当且仅当时，都是等价的布尔矩阵。证明：设，（1）证明自反性，即证明由可导出。结论显然成立。（2）证明对称性，即证明由可导出。采用反证法：设由可导出，则 对，由必有，与题设矛盾，得证。（3）证明传递性（），即证明由 可导出。布尔矩阵中元素只有0和1，故考虑两种情况。a) 当时，因为“1”是布尔矩阵中的最大值，故不等式必然成立。b) 当时，有，即：由，有不失一般性，设为较小者，则仍成立，即传递性成立。满足自反性、对称性、传递性，是等价的布尔矩阵。7.6 证明7.5节定理2：若，则所分出的每一类必是所分出的某一类的子类。证明：亦即：由可导出，所以所分出的每一类必是所分出的某一类的子类。7.7 设论域，在X中有模糊集合求格贴近度。解： 7.8 设论域为，和是论域X上的两个模糊集，X上每个元素隶属于和的隶属度分别表示为下式为采用内积、外积函数表示的一种贴近度其中，分别为模糊集中隶属度的最大值和最小值，求贴近度。解：7.9已知三个模糊集合分别为 (1) 用海明距离和海明贴近度判别，哪个与最相近；(2) 用格贴近度判别，哪个与最相近。解：(1) 用海明距离判断 与最相近。 利用海明贴近度判断 与最相近。(2) 用格贴近度判断 与最相近。7.10 已知模糊关系矩阵判断R是模糊相似矩阵还是模糊等价矩阵，并用截矩阵法按不同水平聚类，给出动态聚类图。解：设论域为。 判断R是模糊相似矩阵还是模糊等价矩阵。模糊矩阵R显然具有自反性和对称性，下面验证是否具有传递性：其中，类似地得：有 可以看出，R不满足的传递性要求，故是模糊相似矩阵。 用截矩阵法进行聚类。根据逐步平方的方法，可得到模糊等价矩阵，设为：依次取的截矩阵聚类：此等价布尔矩阵将模式分为5类：，。，此时分为4类：，。，此时分为3类：，。，此时分为2类：，。，此时归为1类。动态聚类图如解图7.1所示：解图7.1 动态聚类图7.11 设论域为，已知模糊相似矩阵为按最大树法进行聚类，求，时的聚类结果。解： 构造最大树。依次逐列画出R中元素的元素集，至全部元素都已出现，标出权重，得最大树