模式識別習題參考教材第6and7章講解

1、第 5章 句法模式識別習題解答 6.1 用鏈碼法描述 5 9 五個數(shù)字。 解：用弗利曼鏈碼表示，基元如解圖 6.1 所示： 解圖 6.1 弗利曼鏈碼基元 數(shù)字 59的折線化和量化結(jié)果如解圖 6.2 所示： 各數(shù)字的鏈碼表示分別為： 5”的鏈碼表示為 x 444660076543； 6”的鏈碼表示為 x 4456667012344 ； 7”的鏈碼表示為 x 00066666； 8”的鏈碼表示為 x 34570765432101； 9”的鏈碼表示為 x 5432107666544。 6.2 定義所需基本基元，用 PDL 法描述印刷體英文大寫斜體字母 H”、“K”和 Z” 解：設(shè)基元為： a b c

2、 d e 用 PDL 法得到“ H”的鏈描述為 xH (d (d (c (d ( d) ； “K”的鏈描述為 xK (d (d a b) ； “Z”的鏈描述為 xZ (g c) c)。 6.3 設(shè)有文法 G (VN ,VT , P,S)，VN ，VT 和 P 分別為 VN S, A, B，VT a,b P：S aB， S bA， A a， A aS A bAA ， B b ， B bS ， B aBB 寫出三個屬于 L(G )的句子。 解：S aB ab S aB abS abbA abba S aB abS abaB abab S bA ba S bA baS baaB baab S bA

3、baS babA baba 以上句子 ab， abba，abab，ba， baab， baba均屬于 L(G) 。 6.4 設(shè)有文法 G (VN,VT, P, S) ，其中 VN S, A, B,C ，VT 0,1 ，P 的各 生成式為 S 0A ， S 1B ， S 1C A 0A ， A 1B， A 1 B 0， B 0B， C 0C， C 1 問 x 00100是否屬于語言 L(G)？ 解：由 S 0A 00A 001B 0010B 00100 可知 x 00100屬于語言 L(G) 。 6.5 寫出能產(chǎn)生圖示樹的擴展樹文法，設(shè)基元 a，b 分別為“”和“” ，它 所描述的模式是什么？

4、解： 1. 寫出生成樹的擴展樹文法生成式集： A1 $ 1 A2 a A3 a A2 A4 A3 A4b A5 b A6 A9 A5 (6) A6a A7a A8a A7A8 A9b A10b A11a A12 a A10 A11 A12 2. 檢查非終止符的等價性。 A7和 查得 A2 A7 A11 。刪除 A7 和 A11 及其后代生成式，其余生成式中的 A11 用 A2代替，合并后得到 A1 $ 1 A2 A4 A2 a A3a A3 A4b A5 b 5 A6 A9 A5 (6) A6a A9 b A10 b A2 A10 A2 3. 建立起始產(chǎn)生式。將中的 A1用 S代替得到： S$

5、 A2A4 設(shè)推斷的擴展樹文法為 Gt (V, r,P, S) ，由以上推斷得： V VN VT ， VN S, A2, A3, A4, A5, A6, A9, A10 ，VT $,a, b r($) 2 ， r(a) 1, 0 r(b) 2,1 P 的各生成式為 S $ A2 A4 A2 a A3a A3 A4b A5 b 5 A6 A9 A5 (6) A6a A9 b A10 b A2 A10 A2 當基元 a，b 分別為 ”和“ 時， 它所描述的模式如解圖 6.3 所示： 解圖 6.3 描述的模式 6.6 已知 L(G) 的正樣本集 R 01,100,111,0010 ，試推斷出余碼文法

6、 Gc。 解：設(shè)余碼文法為 Gc (VN,VT,P, S)。 (1) 由R 得Gc的終止符集 VT 0,1。 (2) 求 R 的全部余碼，組成非終止符集 VN。 R 的全部余碼為 D R 01,100,111,0010， D0R 1, 010 ， D1R 00, 11 D01R ，D10R 0 ， D11R 1 ， D00R 10 D100R ， D111R ， D001R 0 ， D0010R 等號右邊相同的合并，非空余碼標以符號組成非終止符集 VN ： S D R 01,100, 111, 0010 ，U 1 D0R 1, 010 ，U2 D1R 00, 11 U3 D10R 0，U4 D

7、11R 1 ，U5 D00R 10 所以VN S,U1,U2,U3,U4,U5。 (3) 建立生成式集 P。 由 D0S 1, 010 U 1 ，有生成式 S 0U1 ； 由D0U1 10 U 5 ，有生成式 U1 0U5； 由 D0U2 0 U 3 ，有生成式 U 2 0U3； 由 D0U 3，有生成式 U 3 0 ； 由 D1S 00,11 U 2 ，有生成式 S 1U 2； 由 D1U 1 ，有生成式 U 1 1； 由D1U2 1 U 4，有生成式 U2 1U4； 由D1U4 ，有生成式 U4 1； 由 D1U 5 0 U 3，有生成式 U 5 1U3； 所以余碼文法 Gc (VN,VT

8、,P, S)為 VN S,U1,U2,U3,U4,U5 ，VT 0,1 P： S 0U1，U1 0U5 ，U2 0U3，U3 0 S 1U2，U1 1，U2 1U 4，U4 1，U 5 1U 3 6.7 設(shè)文法G (VN,VT,P,S)，其中VN S, A,B，VT 0,1，P的各生成式 為 S 1， S B1 ， S B B 1A，B B1A， A 0， A A0 設(shè)待識別鏈 x 1000，試用填充樹圖法的頂下法分析 x 是否屬于 L(G)? 解：(1) 從 S開始考察 P 中的、式： 若選，則結(jié)果為 x=1，排除； (a) 若選，導出的 選式，如解圖 x 末位必為 1 ， 6.4(a)所示

9、。 B B 1 A A (b) (c) 與題不符，排除； B B 1 A A A A 0 (d) S B B 1 A A0 A0 A 0 0 (e) 解圖 6.4 填充樹圖過程 (2) 填充目標為 B ，考察、均可填充，先試，如解圖 6.4(b)所示。若不行， 再返回用式。 (3) 此時填充目標為 A ，考察、。若選，導出的 x 為 2 位，與題不符，排 除。選式，如解圖 6.4(c)所示。 (4) 類似地，得到圖 6.4 所示各步結(jié)果，樹葉為 1000。 故 x 屬于 L(G) 。 6.8 設(shè)上下文無關(guān)文法 G (VN,VT,P,S)，VN S,C ，VT 0,1，P中生成 式的喬姆斯基范式

10、為 S CC ， S CS ， S 1 ， C SC ， C CS ， C 0 用 CYK 分析法分析鏈 x 01001 是否為該文法的合法句子。 解：待識別鏈為 5 位，構(gòu)造 5 行 5 列的三角形分析表，如解圖 6.5 所示 t15 t14 t24 t13 t23 t33 t12 t22 t32 t42 t11 t21 t31 t41 t51 解 圖 6.5 分析表 求表中元素 tij 的值： (1) 令 j 1，求 ti1，1 i 5。 各子鏈為 0，1，0，0，1。 對于 a1 0 ， t11 C ； 對于 a2 1， t21 S ； 對于 a3 0 ， t31 C ； 對于 a4 0

11、 ， t41 C 。 對于 a5 1， t41 S 。 (2) 令 j 2，求 ti2，1 i 4 。各子鏈為 01，10，00，01。 對于 a1a2 01，因有 S CS和C CS，C 0，S 1，故t12 C, S； 對于 a2a3 10 ，有 C SC， S 1， C 0，故 t 22 C 。 對于 a3a4 00，有 S CC，C 0，C 0，故 t32 S。 對于a4a5 01，有S CS和C CS，C 0，S 1，故t42 C, S； (3) 令 j 3，求 ti3 ，1 i 3。各子鏈為 010，100，001。 對于 a1a2a3 010 ，因有 S CC ， * C 0，C

12、 10；和C SC， S 01， C 0 。故 t13 C, S 。 類似地有 t23 S，t33 C,S，t14 C,S，t24 C,S，t15 C, S 。填表結(jié)果 如解圖 6.6 所示。 C,S C,S C,S C,S S C,S C,S C S C,S C S C C S 解圖 6.6 CYK 分析表填表結(jié)果 因為 S在 t15 中，所以 x L(G) 6.9 已知正則文法 G (VN,VT,P, S)，其中VN S, B ，VT a, b ，P的各生 成式為 S aB ， B aB ， B bS ， B a 構(gòu)成對應(yīng)的有限態(tài)自動機，畫出自動機的狀態(tài)轉(zhuǎn)換圖。 解：設(shè)有限態(tài)自動機 A (

13、 ,Q, ,q0,F )，由 A與 G的對應(yīng)關(guān)系得 VT a,b Q VN F S, B,F q0 S ：由 S aB ，有 (S, a) B ； 由 B aB ， B a 有 (B, a) B, F ； 由 B bS，有 (B, b) S。 故有限態(tài)自動機 A ( ,Q, ,q0,F )為 a,b ， Q S, B, F ， q0 S 8 6.10 已知有限態(tài)自動機 A ( ,Q, ,q0,F )，其中 0,1，Q q0,q1,q2,q3 ，F(xiàn) q3 解：設(shè)正則文法為 G (VN,VT,P,S)，由 G與A的對應(yīng)關(guān)系得： VN Q q0, q1,q2,q3 ； VT0,1 ； S q0 ；

14、根據(jù)狀態(tài)轉(zhuǎn)換圖有： P：因 (q0, 0) q2 ，有 q0 0q2； 因 (q0,1) q1，有 q0 1q1； 因 (q1,0) q3，有 q1 0q3；而 q3 F，故q1 0； 因 (q1,1) q0 ，有 q1 1q0 ； 因 (q2,0) q0，有 q2 0q0； 因 (q2,1) q3 ，有 q2 1q3；而 q3 F，故 q2 1； 因 (q3, 0) q1 ，有 q3 0q1； 因 (q3,1) q2 ，有 q3 1q2 。 由此得正則文法 G (VN,VT, P,S)為 VN Q q0,q1,q2,q3，VT0,1 ，S q0 P： q0 0q2 ，q0 1q1，q1 0

15、， q1 1q0 q2 0q0 ， q2 1 ， q3 0q1 ， q3 1q2 6.11 已知上下文無關(guān)文法 G (VN ,VT, P,S) ，其中 VN S, A ，VT a, b,c, d P 的各生成式為 S cA ， A aAb ， A d 寫出文法 G 的格雷巴赫范式，構(gòu)成相應(yīng)的下推自動機。 解：文法 G (VN ,VT , P,S) 的格雷巴赫范式為： VN S, A,B ，VT a,b,c,d P： S cA ， A aAB ， A d ， B b 設(shè)相應(yīng)的下推自動機為 Ap ( ,Q, , , q0, Z0, F ) ，其中 VT a,b,c, d ， Q q0 VN S,

16、A, B ， Z0 S ， F 轉(zhuǎn)換規(guī)則 ： 因 P 中有 S cA，故 (q0,c, S) (q0, A) 因 P 中有 A aAB，故 (q0,a, A) (q0, AB ) 因 P 中有 A d ，故 (q0, d, A) (q0, ) 因 P 中有 B b，故 (q0 ,b, B) (q0, ) 即下推自動機 Ap ( , Q, , ,q0 ,Z0,F ) 為： a,b, c, d ，Q q0 ， S, A,B ， Z0 S， F P： (q0 , c, S) (q0, A ) ， (q0, a, A) (q0, AB ) (q0, d, A) (q0, )， (q0, b,B) (q

17、0, ) 10 第 6 章 模糊模式識別法習題解答 7.1 試分別說明近似性、 隨機性和含混性與模糊性在概念上的相同處與不同處。 解： (1) 近似性與模糊性的異同 共同點：描述上的不精確性。 區(qū)別：不精確性的根源和表現(xiàn)形式不同。 a) 近似性：問題本身有精確解，描述時的不精確性源于認識條件的局限性 和認識過程發(fā)展的不充分性。 b) 模糊性：問題本身無精確解，描述的不精確性來源于對象自身固有的性 態(tài)上的不確定性。 (2) 隨機性與模糊性的異同 共同點：不確定性。 區(qū)別：模糊性和隨機性所表現(xiàn)出的不確定性的性質(zhì)不同。 a) 模糊性：表現(xiàn)在質(zhì)的不確定性。是由于概念外延的模糊性而呈現(xiàn)出的不 確定性。

18、b) 隨機性：是外在的不確定性。是由于條件不充分，導致條件與事件之間 不能出現(xiàn)確定的因果關(guān)系，事物本身的性態(tài) (性質(zhì)、狀態(tài)、特征等 )和類屬是確定 的。 c) 排中律：即事件的發(fā)生和不發(fā)生必居且僅居其一，不存在第三種現(xiàn)象。 隨機性遵守排中律，模糊性不遵守，它存在著多種，甚至無數(shù)種中間現(xiàn)象。 (3) 含混性與模糊性的異同 共同點：不確定性。 區(qū)別： a) 含混性：由信息不充分(二義性)引起，一個含混的命題即是模糊的， 又是二義的。一個命題是否帶有含混性與其應(yīng)用對象或上下文有關(guān)。 b) 模糊性：是質(zhì)的不確定性。 7.2 已知論域 X 0,1,2,3，A 和B為 X中的模糊集合，分別為 A 0.2,

19、0 , 0.3,1 , 0.4,2, 0.5,3 11 B 0.5, 0 , 0.4,1 , 0.3, 2, 0, 3 1)求 A B，A B， A 和B ； 2)求 A B A 。 解：（ 1）由 A B x max A x , B x 有 A B= 0.5,0 , 0.4,1 , 0.4,2 , 0.5,3 由 A B x min A x, B x 有 A B0.2,0, 0.3,1 , 0.3,2, 0,3 A 0.8,0, 0.7,1 , 0.6, 2 , 0.5,3 B 0.5,0 , 0.6,1 , 0.7, 2 , 1,3 2) A B A 0.5,3 = 0.5,0, 0.4,

20、1 , 0.4,2, 0.8,0, 0.7,1 , 0.6,2, 0.5,3 0.5,0, 0.4,1 , 0.4,2, 0.5,3 7.3 已知兩個模糊集合 A 0.5,a , 0.8,b ， B 0.9,a , 0.2,b 試驗證截集的兩個性質(zhì)： 1) (A B) A B ；2) (A B) A B 解：( 1)驗證 (A B) A B 左邊： A B 0.5 0.9, a , 0.8 0.2,b 0.9,a , 0.8,b (A B)0.5 a,b 右邊： A0.5 a,b ，B0.5 a ，有 A0.5 B0.5 a,b 所以：左邊 = 右邊。 ( 2)驗證 (A B) A B 12

21、左邊： A B0.5 0.9, a , 0.8 0.2,b 0.5,a , 0.2,b (A B)0.3 a 右邊： A0.3 a,b ， B0.3 a ，有 A0.3 B0.3 a 所以：左邊 = 右邊。 1 0.3 0.1 0.2 7.4 判斷模糊矩陣 R 0.2 1 0.3 0.1 是否是傳遞模糊矩陣。 0.3 0.2 1 0.2 0.1 0.3 0.3 1 1 0.3 0.1 0.2 1 0.3 0.1 0.2 解： 0.2 1 0.3 0.1 0.2 1 0.3 0.1 RR 0.3 0.2 1 0.2 0.3 0.2 1 0.2 0.1 0.3 0.3 1 0.1 0.3 0.3

22、1 1 0.2 0.1 0.1 0.3 0.3 0.1 0.3 0.1 0.3 0.1 0.2 0.2 0.1 0.1 0.2 0.2 0.2 0.3 0.1 1 0.3 0.3 0.2 0.3 1 0.3 0.2 0.3 0.3 1 0.2 0.3 0.3 0.3 1 由計算結(jié)果可見 R R R不成立，故 R 不是傳遞模糊矩陣。 7.5 證明 7.5節(jié)定理 1：對n n階模糊等價矩陣 R，當且僅當0, 1 時，R 都是等價的布爾矩陣。 證明：設(shè) R rij ， R rij （ 1）證明自反性，即證明由 rii 1可導出 rii 1。 0 1, 結(jié)論顯然成立。 （2）證明對稱性，即證明由 ri

23、j r ji可導出 rij rji。 采用反證法：設(shè)由 rij r ji 可導出 rij r ji ，則 對 0, 1 ，由 rij rji 必有 rij rji ，與題設(shè)矛盾，得證。 13 nn （3）證明傳遞性（ R R R ），即證明由 rikrij rjk 可導出 rikrij rjk 。 布爾矩陣中元素只有 0和 1，故考慮兩種情況。 n a） 當 rik 1時，因為“1”是布爾矩陣中的最大值，故不等式 rikrij rjk 必然 成立。 b） 當 rik 0 時，有 rik，即： n 由 rik j 1 rij r jk ，有 n rikj 1 rij rjkmax rij rjk

24、, j 1, ,n rij rjk , j 1, ,n 不失一般性，設(shè) rij 為較小者，則 rijrij 0 rij rjk 0 j 1rij r jk 0 j1 rikn rij r jk 仍成立，即傳遞性成立。 R滿足自反性、對稱性、傳遞性， R是等價的布爾矩陣。 7.6 證明 7.5節(jié)定理 2：若 01，則 R 所分出的每一類必是 R 所分出的 某一類的子類。 證明： rij 1 rijrijrij 1 亦即：由 rij 1 可導出 rij 1，所以 R 所分出的每一類必是 R 所分出的某一類 的子類。 7.7 設(shè)論域 X x1, x2, x3 ，在 X 中有模糊集合 A 0.6, x

25、1 , 0.8, x2 , 1.0, x3 B 0.4, x1 , 0.6, x2 , 0.8, x3 14 求格貼近度 。 解： A B x X A xi B xi (0.6 0.4) (0.8 0.6) (1.0 0.8) 0.4 0.6 0.8 0.8 A Bx X A xiB x (0.60.4)(0.80.6) (1.0 0.8)0.6 0.81.00.6 A,B1 AB 1A B 1 0.81 0.60.6 2 2 7.8 設(shè)論域為 X x1, x2, x3, x4 ，A和B是論域 X 上的兩個模糊集， X 上 每個元素隸屬于 A和 B 的隸屬度分別表示為 A 0.5 x1 , 0

26、.7 x2 , 0.4 x3 , 0.3 x4 B 0.7 x1 , 0.8 x2 , 0.7 x3 , 0.5 x4 下式為采用內(nèi)積、外積函數(shù)表示的一種貼近度 A, B 1 (A A) (A B A B) 其中 A ， A分別為模糊集 A中隸屬度的最大值和最小值， 求貼近度 A,B 。 解： A B A xiB xi x X (0.5 0.7) (0.7 0.8) (0.4 0.7) (0.3 0.5) 0.5 0.7 0.4 0.3 0.7 A B x X A xiB xi (0.5 0.7) (0.7 0.8) (0.4 0.7) (0.3 0.5) 0.7 0.8 0.7 0.5 0.

27、5 A, B 1 (A A) (A B A B) 1 (0.7 0.3) (0.7 0.5) 0.8 7.9 已知三個模糊集合分別為 15 A0.2, x1 ,0.4,x2 ,0.5, x3 ,0.1, x4 B10.6, x2 ,0.3, x3 ,0.1, x4 B20.2, x1 ,0.3, x2 ,0.5, x3 (1) 用海明距離和海明貼近度判別 B1 ， B2哪個與 A最相近； (2) 用格貼近度判別 B1，B2 哪個與 A最相近。 解： (1) 用海明距離判斷 dH(A, B1) A(xi)B1(xi) 0.2 0 i 1 0.4 0.6 0.5 0.3 0.1 0.1 0.6 d

28、H(A, B2)A(xi)B2(xi) i1 0.2 0.2 0.4 0.3 0.5 0.5 0.1 0 0.2 dH(A, B2) dH(A,B1) B2 與 A 最相近。 14 利用海明貼近度判斷 ,B11 4 i 1 A xiB1 xi 1 1 (0.2 0.2 0.2 0) 0.85 14 4 , B21A xiB2 xi 4 i 1 1 1 (0 0.1 0 0.1) 0.95 4 B2H A, B1 B2 與 A 最相近。 (2) 用格貼近度 A, B 1 A B 1 A B 判斷 2 16 A B1 xiB1 x (0.2 0) (0.4 0.6) (0.5 0.3) (0.1

29、0.1) A xiB1 x 0 0.4 0.3 0.1 0.4 A B1 x X (0.2 0) (0.4 0.6) (0.5 0.3) (0.1 0.1) 0.2 0.6 0.5 0.1 0.1 A, B11 AB11 A B11 0.4 1 0.10.65 12 1 12 A B2 x X A xiB2 xi (0.20.2)(0.40.3) (0.50.5) (0.1 0) 0.2 0.3 0.5 0 0.5 A B2 x X A xiB2 xi (0.2 0.2) (0.4 0.3) (0.5 0.5) (0.1 0) 0.2 0.4 0.5 0.1 0.1 A, B21 AB21 A

30、 B210.5 1 0.1 0.7 22 2 22 A, B2A, B1 B2 與 A 最相近。 7.10 已知模糊關(guān)系矩陣 1 0.1 0.1 1 R 0.8 0.1 0.5 0.2 0.3 0.4 0.8 0.5 0.3 0.1 0.2 0.4 1 0.3 0.1 0.3 1 0.6 0.1 0.6 1 17 判斷 R 是模糊相似矩陣還是模糊等價矩陣， 并用截矩陣法按不同 水平聚 類，給出動態(tài)聚類圖。 解：設(shè)論域為 X x1, x2, x3, x4 x5 。 判斷 R 是模糊相似矩陣還是模糊等價矩陣。 模糊矩陣 R 顯然具有自反性和對稱性，下面驗證是否具有傳遞性： 1 0.1 0.8 0.

31、5 0.3 1 0.1 0.8 0.5 0.3 0.1 1 0.1 0.2 0.4 0.1 1 0.1 0.2 0.4 RR 0.8 0.1 1 0.3 0.1 0.8 0.1 1 0.3 0.1 0.5 0.2 0.3 1 0.6 0.5 0.2 0.3 1 0.6 0.3 0.4 0.1 0.6 1 0.3 0.4 0.1 0.6 1 其中， r11 1 1 0.1 0.1 0.8 0.8 0.5 0.5 0.3 0.3 1 0.1 0.8 0.5 0.3 1 r12 1 0.1 0.1 1 0.8 0.1 0.5 0.2 0.3 0.4 0.10.10.10.20.30.3 類似地得： r130.80.10.80.30.10.8 r140.50.10.30.50.10.5 r150.30.10.10.50.30.5 r210.10.10.10.20.30.3 r22 0.1 1 0.1 0.2 0.4 1 r230.10.10.10.20.10.2 r240.10.20.10.20.40.4 r250.10.40.10.20.40.4 1 0.3 0.8 0.5 0.5 0.3 1