Tiểu luận kết thúc môn học: Logic mờ

v¨n ph¹m mµ c¸c quy t¾c cã d¹ng tæng qu¸t rw, c>0 trong ®ã r vµ w lµ c¸c x©u trong (TÈN)*. V¨n ph¹m lo¹i 1 (c¶m ng÷ c¶nh): Lµ v¨n ph¹m mµ c¸c quy t¾c cã d¹ng r1Ar2r1wr2, c>0 trong ®ã r1, r2 vµ w lµ c¸c x©u trong (TÈN)*, AÎN vµ w¹A. Quy t¾c SA còng thuéc v¨n ph¹m lo¹i nµy. V¨n ph¹m lo¹i 2 (phi ng÷ c¶nh): Lµ v¨n ph¹m mµ c¸c quy t¾c cã d¹ng Aw, c>0, AÎN vµ wÎ(TÈN)* w¹A, vµ SA. V¨n ph¹m lo¹i 3 (chÝnh quy): Lµ v¨n ph¹m mµ c¸c quy t¾c cã d¹ng AaB hoÆc Aa, c>0, trong ®ã aÎT, A, BÎN. Quy t¾c SA còng thuéc v¨n ph¹m lo¹i nµy. Ta cã thÓ chØ ra r»ng v¨n ph¹m c¶m ng÷ c¶nh lµ ®Ö quy vµ v× vËy v¨n ph¹m phi ng÷ c¶nh vµ v¨n ph¹m chÝnh quy còng ®Ö quy. §Þnh lý 2.1 NÕu G=(N,T,P,S) lµ v¨n ph¹m c¶m ng÷ c¶nh mê th× G lµ ®Ö quy. Chøng minh: Tr­íc hÕt ta chØ ra r»ng ®èi víi mét lo¹i v¨n ph¹m bÊt kú, cËn trªn nhá nhÊt trong (7) cã thÓ ®­îc lÊy trªn mét tËp con cña tËp hîp tÊt c¶ d·y suy dÉn tõ S ®Õn x, ®ã lµ tËp con cña tÊt c¶ nh÷ng d·y suy dÉn kh«ng lÆp (lµ d·y mµ trong ®ã kh«ng cã ri (i=1..m) xuÊt hiÖn h¬n mét lÇn) Gi¶ sö r»ng trong d·y suy dÉn C= S r1r2 ... rmx, ri lµ gièng rj, j>i. §Æt C’ lµ d·y kÕt qu¶ tõ viÖc thay thÕ d·y con ri ... rjrj+1 trong C bëi rjrj+1. Râ rµng, nÕu C lµ mét d·y suy dÉn tõ S ®Õn x th× C’ còng lµ mét d·y suy dÉn tõ S ®Õn x. Tuy nhiªn Ù{c1,...,ci,ci+1,...,cj+1,...,cm+1}£Ù{c1,...,ci,cj+1,...,cm+1} v× vËy C cã thÓ bÞ xãa mµ kh«ng ¶nh h­ëng ®Õn cËn trªn nhá nhÊt trong (7). Nh­ vËy ta cã thÓ thay thÕ ®Þnh nghÜa (7) cña mG(x) b»ng mG(x) = Ú Ù{(m(S,r1), m(r1,r2),...,m(rm,x)} (9) trong ®ã cËn trªn nhá nhÊt lÊy trªn tÊt c¶ d·y suy dÉn kh«ng lÆp tõ S vµo x B©y giê ta chØ ra r»ng ®èi víi nh÷ng v¨n ph¹m c¶m ng÷ c¶nh, tËp hîp cËn trªn nhá nhÊt ®­îc lÊy trong (9) bÞ giíi h¹n vµo ®é dµi l0 cña nh÷ng d·y suy dÉn, trong ®ã l0 phô thuéc vµo vµ sè l­îng c¸c ký hiÖu trong (TÈN). NÕu G lµ v¨n ph¹m c¶m ng÷ c¶nh th× v× ®Æc tÝnh kh«ng thu hÑp ®­îc cña c¸c quy trong P nªn nã kÐo theo: nÕu j>i (10) §Æt =k. V× cã tèi ®a k’ x©u ph©n biÖt trong (TÈN)* cã ®é dµi l vµ v× d·y suy dÉn lµ kh«ng lÆp nªn tõ (10) ta cã tæng ®é dµi cña d·y ®­îc giíi h¹n bëi l0= 1+k+...+k. TiÕp theo ta ®­a ra mét ph­¬ng ph¸p sinh ra tÊt c¶ d·y suy dÉn h÷u h¹n tõ S ®Õn x cã ®é dµi £l0. Ta b¾t ®Çu víi S vµ dïng P sinh ra tËp Q1 cña tÊt c¶ c¸c x©u trong (TÈN)* cã ®é dµi £ mµ cã thÓ sinh tõ S trong mét b­íc. Sau ®ã ta x©y dùng Q2, tËp hîp tÊt c¶ c¸c chuçi trong (TÈN)* cã ®é dµi £ mµ cã thÓ sinh tõ S trong hai b­íc. L­u ý, Q2 ®ång nhÊt víi tËp tÊt c¶ c¸c x©u trong (TÈN)* víi ®é dµi £ mµ ®­îc sinh trùc tiÕp tõ c¸c x©u trong Q1. TiÕp tôc víi qu¸ tr×nh nµy, ta x©y dùng liªn tiÕp Q3, Q4, ..., Qk cho ®Õn khi k=l0 hoÆc Qk=Æ. V× Qi (i=1...k) lµ tËp h÷u h¹n, ta cã thÓ t×m trong mét sè h÷u h¹n cña c¸c tËp tÊt c¶ c¸c d·y suy dÉn kh«ng lÆp tõ S ®Õn x víi ®é dµi £ l0 vµ v× vËy ®Ó tÝnh to¸n mG(x) b»ng sö dông (9). Sau ®ã thiÕt lËp mét thuËt to¸n ®Ó tÝnh to¸n mG(x). V× vËy G lµ ®Ö quy. 3. V¨n ph¹m phi ng÷ c¶nh mê NhiÒu kÕt qu¶ c¬ së trong lý thuyÕt ng«n ng÷ h×nh thøc cã thÓ dÔ dµng ®­îc më réng thµnh ng«n ng÷ mê. PhÇn nµy ta ®­a ra mét më réng nh­ vËy trong tr­êng hîp nh÷ng d¹ng chuÈn t¾c cña Chomsky vµ Greibach ®èi víi nh÷ng ng«n ng÷ phi ng÷ c¶nh. Tr­íc hÕt, ta xÐt d¹ng chuÈn t¾c Chomsky ®èi víi ng«n ng÷ phi ng÷ c¶nh mê. BÊt kú ng«n ng÷ phi ng÷ c¶nh ®­îc sinh ra bëi mét v¨n ph¹m trong ®ã c¸c quy t¾c cã d¹ng ABC hoÆc Aa, víi A,B,C lµ ký hiÖu kh«ng kÕt thóc vµ a lµ ký hiÖu kÕt thóc. D¹ng nµy ®­îc gäi lµ d¹ng chuÈn t¾c Chomsky. Cho G lµ mét v¨n ph¹m phi ng÷ c¶nh mê. V¨n ph¹m nµy t­¬ng ®­¬ng víi mét v¨n ph¹m G’ trong ®ã tÊt c¶ quy t¾c cã d¹ng A BC, A a, víi c>0 vµ A,B,C lµ ký hiÖu kh«ng kÕt thóc vµ a lµ ký hiÖu kÕt thóc. Ta x©y dùng G’ theo ba giai ®o¹n: Thø nhÊt, ta x©y dùng mét v¨n ph¹m G1 t­¬ng ®­¬ng víi G trong ®ã kh«ng cã quy t¾c d¹ng A B, A,BÎN Gi¶ sö r»ng trong G ta cã quy t¾c d¹ng A B mµ dÉn ®Õn d·y suy dÉn d¹ng: A B1 B2 ...Bm B r víi rÏN, khi ®ã ta thay thÕ tÊt c¶ c¸c quy t¾c d¹ng: A B1, B1B2,..., Bm B trong G b»ng c¸c quy t¾c ®¬n d¹ng Ar trong ®ã c = m(AÞB) Ù m(B,r) (11) trong ®ã m(AÞB) = Ú {m(A1,B1) Ù ... Ù m(Am,B)} (12) víi cËn trªn nhá nhÊt ®­îc lÊy trªn tÊt c¶ d·y suy dÉn kh«ng lÆp tõ A ®Õn B. Suy ra v¨n ph¹m kÕt qu¶ G1 t­¬ng ®­¬ng víi G. Thø hai, ta x©y dùng mét v¨n ph¹m G2 t­¬ng ®­¬ng víi G1 trong ®ã kh«ng cã quy t¾c d¹ng AB1 B2...Bm, c>0 m>2, trong ®ã mét hoÆc nhiÒu B lµ ký hiÖu kÕt thóc. Nh­ vËy gi¶ sö r»ng Bi lµ mét ký hiÖu kÕt thóc a. Th× Bi trong B1 B2...Bm ®­îc thay bëi mét ký hiÖu kh«ng kÕt thóc míi Ci mµ kh«ng xuÊt hiÖn trong vÕ ph¶i cña bÊt kú quy t¾c nµo. Sau ®ã ta ®Æt m(A, B1 B2...Bi ...,Bm)= m(A, B1 B2...Ci ...,Bm) (13) Ta thªm vµo tËp quy t¾c cña G quy t¾c Cia. Thùc hiÖn ®iÒu nµy ®èi víi tÊt c¶ ký hiÖu kÕt thóc trong B1 B2...Bm trong tÊt c¶ quy t¾c d¹ng AB1 B2...Bm. Nh­ vËy ta thu ®­îc mét v¨n ph¹m G2 trong ®ã tÊt c¶ quy t¾c lµ cã d¹ng Aa hoÆc AB1 B2...Bm , m>2 víi tÊt c¶ B lµ ký hiÖu kh«ng kÕt thóc. Râ rµng G2 t­¬ng ®­¬ng víi G1. Thø ba, ta x©y dùng mét v¨n ph¹m G3 t­¬ng ®­¬ng víi G2 trong ®ã tÊt c¶ quy t¾c cã d¹ng Aa hoÆc ABC, A,B,CÎN, aÎT. XÐt mét quy t¾c trong G2 d¹ng AB1 B2...Bm, c>0 m>2. Ta thay thÕ tÊt c¶ quy t¾c nµy bëi quy t¾c AB1D1 D1B2D2 ... Dm-2Bm-1Bm trong ®ã c¸c D lµ nh÷ng ký hiÖu kh«ng kÕt thóc míi mµ kh«ng xuÊt hiÖn trong vÕ ph¶i cña cña bÊt kú quy t¾c nµo trong G2. Thùc hiÖn nh­ vËy ®èi víi tÊt c¶ quy t¾c trong G2 cã d¹ng AB1 B2...Bm, ta thu ®­îc mét v¨n ph¹m G3 t­¬ng ®­¬ng víi G2. V× vËy G3 trong d¹ng chuÈn t¾c Chomsky lµ t­¬ng ®­¬ng víi G. VÝ dô 3.1 XÐt v¨n ph¹m mê d­íi ®©y, trong ®ã T={a,b} vµ N={A,B,S} vµ c¸c quy t¾c nh­ sau SbA Bb SaB AbSA Aa BaSB §Ó t×m ra mét v¨n ph¹m t­¬ng ®­¬ng trong d¹ng chuÈn t¾c Chomsky, ta thùc hiÖn nh­ sau: Thø nhÊt, ta thay SbA bëi SC1A, C1 b. thay SaB bëi SC2B, C2a. thay AbSA bëi AC3SA, C3 b vµ thay BaSB bëi BC4SB, C4a Thø hai, ta thay AC3SA bëi AC3D1, D1 SA, vµ thay BC4SB bëi BC4D2, D2 SB. VËy c¸c quy t¾c trong d¹ng chuÈn t¾c Chomsky t­¬ng ®­¬ng nh­ sau: SC1A AC3D1 C1 b D1 SA SC2B C3 b C2a BC4D2 Aa D2 SB Bb C4a Sau ®©y ta xÐt d¹ng chuÈn t¾c Greibach. Cho G lµ v¨n ph¹m phi ng÷ c¶nh mê bÊt kú. G t­¬ng ®­¬ng víi mét v¨n ph¹m mê GG trong ®ã tÊt c¶ c¸c quy t¾c cã d¹ng Aar, víi A lµ mét ký hiÖu kh«ng kÕt thóc, a lµ mét ký hiÖu kÕt thóc vµ r lµ mét x©u trong N*. V¨n ph¹m mê GG lµ trong d¹ng chuÈn Greibach. §Ó x©y dùng GG ta ph¶i sö dông hai bæ ®Ò d­íi ®©y: Bæ ®Ò 3.2 Cho G lµ mét v¨n ph¹m phi ng÷ c¶nh mê. §Æt Ar1Br2 lµ mét quy t¾c trong P, víi A,BÎN, vµ r1, r2Î(TÈN)*. §Æt B w1,..., B wk lµ tËp tÊt c¶ c¸c quy t¾c víi B thuéc vÕ tr¸i (B-production). §Æt G1 lµ v¨n ph¹m kÕt qu¶ tõ sù thay thÕ cña mçi quy t¾c cã d¹ng Ar1Br2 bëi quy t¾c Ar1w1r2,..., Ar1wrr2 trong ®ã m(A, r1wir2) = m(A, r1wr2) Ù m(B,wi) i=1..k. (15) Khi ®ã G1 t­¬ng ®­¬ng víi G. Bæ ®Ò 3.3 Cho G lµ mét v¨n ph¹m phi ng÷ c¶nh mê. §Æt AAri (i=1..k) lµ nh÷ng quy t¾c trong ®ã A lµ ký kiÖu bªn tr¸i nhÊt ë vÕ ph¶i (A-production). §Æt Awj, lµ nh÷ng quy t¾c cßn l¹i, víi ri, wjÎ(TÈN)*, (i,j=1..k). Gäi G2 lµ v¨n ph¹m kÕt qu¶ tõ viÖc thay thÕ AAri trong G b»ng c¸c quy t¾c: AwjZ (j=1..m) (16) Zri ZriZ (i=1..k) (17) Trong ®ã: m(Z,wjZ) = m(A,wj) m(Z,ri) = m(A,Ari) m(Z,riZ) = m( A,Ari) i=1..k (18) Khi ®ã G2 t­¬ng ®­¬ng víi G Víi viÖc sö dông nh÷ng bæ ®Ò nµy, ta ®­a ra d¹ng chuÈn t¾c Greibach ®èi víi G. Tr­íc hÕt, ta ®Æt G vµo d¹ng chuÈn Chomsky. §Æt A1,...,Am lµ c¸c ký hiÖu kh«ng kÕt thóc. Sau ®ã, ta söa nh÷ng quy t¾c d¹ng Ai Ajs, sÎ(TÈN)*, thùc hiÖn nh­ vËy ®èi víi tÊt c¶ quy t¾c, j³i. §iÒu nµy ®­îc thùc hiÖn nh­ sau: Gi¶ sö r»ng nã ®· ®­îc thùc hiÖn ®èi víi i £k, ®ã lµ, nÕu Ai Ajs (19) lµ mét quy t¾c víi i £k, th× j>i. §Ó më réng thµnh Ak+1-production, gi¶ sö r»ng Ak+1Ajs lµ quy t¾c bÊt kú víi j<k+1. Sö dông bæ ®Ò 3.2 vµ phÐp thÕ ®èi víi Aj vÕ ph¶i cña mçi Aj-production, ta thu ®­îc bëi sù lÆp l¹i phÐp thÕ c¸c quy t¾c d¹ng Ak+1Als l³ k+1 (20) Trong (20), nh÷ng quy t¾c trong ®ã l b»ng k+1 ®­îc thay bëi viÖc sö dông bæ ®Ò 3.3. KÕt qu¶ nµy thuéc mét ký hiÖu kh«ng kÕt thóc míi Zk+1. Sau ®ã b»ng c¸ch lÆp l¹i qu¸ tr×nh nµy, tÊt c¶ quy t¾c ®­îc ®Æt vµo d¹ng AkAls l ³ k sÎ(NÈ{Z1,...,Zn})* (21) Akas aÎT (22) Zks (23) víi ®é thuéc ®· cho bëi mÖnh ®Ò 3.2 vµ 3.3 Víi (21) vµ (22), ký hiÖu bªn tr¸i nhÊt cña vÕ ph¶i cña bÊt kú quy t¾c ®èi víi Am ph¶i lµ mét ký hiÖu kÕt thóc. T­¬ng tù, ®èi víi Am-1, ký hiÖu bªn tr¸i nhÊt cña vÕ ph¶i b¾t buéc lµ Am hoÆc ký hiÖu kÕt thóc. Sö dông bæ ®Ò 3.2 thay thÕ ®èi víi Am, ta thu ®­îc c¸c quy t¾c mµ vÕ ph¶i cña nã b¾t ®Çu víi ký hiÖu kÕt thóc. LÆp l¹i qu¸ tr×nh nµy ®èi víi Am-2,...,A1, c¸c quy t¾c Ai (i=1..m), ®­îc ®Æt vµo d¹ng mµ vÕ ph¶i cña chóng b¾t ®Çu lµ c¸c ký hiÖu kÕt thóc. T¹i giai ®o¹n nµy, chØ nh÷ng quy t¾c trong (23) cã thÓ kh«ng lµ trong d¹ng mong muèn. Suy ra ký hiÖu bªn tr¸i nhÊt trong trong (23) cã thÓ hoÆc mét ký hiÖu kÕt thóc hoÆc mét trong nh÷ng Ai (i=1..m). NÕu tr­êng hîp thø hai tháa m·n, ¸p dông bæ ®Ò 3.2 vµo mçi Zi quy t¾c sinh ra c¸c quy t¾c cña d¹ng mong muèn. §iÒu nµy hoµn thµnh viÖc x©y dùng. VÝ dô 3.4 Ta chuyÓn vÒ d¹ng chuÈn t¾c Greibach v¨n ph¹m mê G d­íi ®©y. Cho T={a,b}, N={A1,A2,A3}, vµ cho c¸c quy t¾c lµ trong d¹ng chuÈn t¾c Chomsky A1 A2A3 A3 A1A2 A2 A3A1 A3 a A2 b B­íc 1: VÕ ph¶i cña c¸c quy t¾c ®èi víi A1 vµ A2 b¾t ®Çu víi ký hiÖu kÕt thóc hoÆc nh÷ng biÕn cã chØ sè cao h¬n. V× vËy ta b¾t ®Çu víi quy t¾c A3A1A2 vµ thÕ A2A3 cho A1. Chó ý, A1 A2A3 chØ lµ quy t¾c víi A1 ë bªn tr¸i. Nh÷ng quy t¾c kÕt qu¶ nh­ sau: A1 A2A3 A2 b A3 b A2 A3A1 A3 A2A3A2 Chó ý, A3 A2A3A2, 0.2=0.8 Ù 0.2. VÕ ph¶i cña quy t¾c A3A2A3A2 b¾t ®Çu víi mét biÕn ®­îc ®¸nh sè thÊp h¬n. V× vËy ta thÕ A3A1 hoÆc b vµo sù xuÊt hiÖn ®Çu tiªn cña A2 Nh÷ng quy t¾c míi ®­îc cho d­íi ®©y A1 A2A3 A2 b A3 bA3A2 A2 A3A1 A3 A3A1A3A2 A3 a TiÕp theo, ta ¸p dông bæ ®Ò 3.3 vµo quy t¾c A1A3A1A3A2, A3bA3A2 vµ A3 a. §­a vµo Z3 vµ thay quy t¾c A3A3A1A3A2 bëi A3bA3A2Z3, A3aZ3, Z3 A1A3A2 vµ Z3 A1A3A2Z3. KÕt qu¶ nh­ sau: A1 A2A3 A2 b A3 a Z3 A1A3A2Z3 A2 A3A1 A3 bA3A2 A3aZ3 Z3 A1A3A2 A3 bA3A2Z3 B­íc 2: B©y giê tÊt c¶ quy t¾c víi A3 ë bªn tr¸i cã vÕ ph¶i b¾t ®Çu víi ký hiÖu kÕt thóc. Nh÷ng quy t¾c nµy ®­îc dïng ®Ó thay thÕ A3 trong quy t¾c A2A3A1 vµ sau ®ã quy t¾c víi A2 ë bªn tr¸i ®­îc dïng ®Ó thay thÕ A2 trong quy t¾c A1A2A3. KÕt qu¶ thu ®­îc nh­ sau: A3 bA3A2 A3 a A2 bA3A2A1 A2 aA1 A2 b A1 bA3A2Z3A1A3 A1 bA3 Z3 A1A3A2 A3 bA3A2Z3 A3aZ3 A2 bA3A2Z3A1 A2aZ3A1 A1bA3A2A1A3 A1aA1A3 A1 A2A3 Z3 A1A3A2Z3 Chó ý, trong A2bA3A2A1, 0.2 = 0.7 Ù 0.2. Trong A1aA1A3, 0.5=0.5 Ù 0.8. §é thuéc cña nh÷ng quy t¾c kh¸c ®­îc x¸c ®Þnh t­¬ng tù. B­íc 3: Hai quy t¾c Z3 A1A3A2 vµ Z3 A1A3A2Z3, ®­îc biÕn ®æi thµnh d¹ng mong muèn b»ng c¸ch thÕ vÕ ph¶i cña mçi trong n¨m quy t¾c víi A1 n»m bªn tr¸i ®èi víi sù xuÊt hiÖn ®Çu tiªn cña A1. V× vËy Z3 A1A3A2 ®­îc thay thÕ bëi: Z3 bA3A3A2 Z3 aA1 A3 A3A2 Z3 aZ3A1A3 A3A2 Z3 bA3A2 A1A3 A3A2 Z3 bA3A2Z3A1A3 A3A2 Nh÷ng quy t¾c kh¸c ®èi víi Z3 ®­îc biÕn ®æi trong mét c¸ch t­¬ng tù. TËp quy t¾c cuèi cïng thu ®­îc: A3 bA3A2 A3 a A2 bA3A2A1 A2aA1 A2 a A1 bA3A2Z3A1A3 A1aZ3 A1A3 Z3 bA3A3A2 Z3 bA3A2 A1A3 A3A2 Z3 aA1 A3 A3A2 Z3 bA3A2Z3A1A3 A3A2 Z3 aZ3A1A3 A3A2 A3 bA3A2Z3 A3aZ3 A2 bA3A2Z3A1 A2aZ3A1 A1bA3A2A1A3 A1aA1A3 A1 bA3 Z3 bA3A3A2Z3 Z3 bA3A2A1 A3A3A2Z3 Z3 aA1A3A3A2Z3 Z3 bA3A2 Z3A1A3A3A2Z3 Z3 a Z3A1A3A3A2Z3 4. v¨n ph¹m max-product phi ng÷ c¶nh §Þnh nghÜa 4.1 Mét v¨n ph¹m max-product phi ng÷ c¶nh (CMG) lµ mét bé bèn G=(T,N,P,h) sao cho tháa m·n nh÷ng ®iÒu kiÖn d­íi ®©y: (1)- T vµ N lµ nh÷ng tËp rêi nhau, h÷u h¹n vµ kh«ng rçng. (2)- P lµ mét tËp hîp h÷u h¹n c¸c quy t¾c mê mµ mçi quy t¾c cã d¹ng Ax,. trong ®ã AÎN, xÎ(TÈN)*, vµ pÎR³0 (3)- h lµ mét hµm tõ N vµo R³0. H¬n n÷a, nÕu ®èi víi mäi (Ax) Î P, hÎ[0,1] vµ h lµ mét hµm tõ N vµo [0,1], th× G ®­îc gäi lµ mét CMG chÆt. Trong ®Þnh nghÜa 4.1, nh÷ng phÇn tö cña T ®­îc gäi lµ ký hiÖu kÕt thóc, nh÷ng phÇn tö cña N ®­îc gäi lµ ký hiÖu kh«ng kÕt thóc, h(A) lµ ®é thuéc mµ A lµ ký hiÖu b¾t ®Çu cña G, vµ Ax cã nghÜa lµ ®é thuéc lµ p mµ A sÏ ®­îc thay bëi x. Cho G=(T,N,P,h) lµ mét CMG. Khi ®ã ta viÕt xÃp y(mod w), trong ®ã w=(r1,k1) (r2,k2)... (rn,kn), x,yÎ(TÈN)*, ri=(Aixi)ÎP, kiÎN (i=1..n) vµ p=p1p2...pn nÕu vµ chØ nÕu tån t¹i ziÎ(TÈN)* (i=0..n) sao cho z0=x, zn=y, vµ ®èi víi mçi i =1,2,...,n, zi thu ®­îc tõ zi-1 b»ng c¸ch thay thÕ sù xuÊt hiÖn thø ki cña Ai trong zi-1 bëi xi. C¸ch viÕt kh¸c: xÃ0 y(mod w) NÕu ®èi víi mäi i=1,2,..,n, ki=1 vµ zi-1=uAiv, trong ®ã uÎT*, th× ta viÕt: xÃpL y(mod w). C¸ch viÕt kh¸c: xÃ0L y(mod w) Râ rµng, p ®­îc x¸c ®Þnh duy nhÊt bëi x,yÎ(TÈN)* vµ wÎ(P´N)*. §iÒu nµy cho phÐp ta ®Þnh nghÜa, ®èi víi mçi wÎ(P´N)*, hµm lw vµ lLw tõ (TÈN)*´(TÈN)* vµo R³0 sao cho lw(x,y)=p nÕu vµ chØ nÕu xÞp y(mod w) vµ lLw(x,y)=p nÕu vµ chØ nÕu xÃpL y(mod w) Cho G=(T,N,P,h) lµ mét CMG. Cho W=P´N. §Þnh nghÜa lG: T*R³0 vµ lLG: T* R³0 víi "xÎT* lG(x) = Ù wÎW*ÚAÎNh(A) lw(A,x) vµ lLG(x) = Ù wÎW*ÚAÎNh(A) lLw(A,x) §Þnh nghÜa 4.3 Mét ng«n ng÷ mê l trªn S lµ mét hµm tõ S* vµo R³0. Mét ng«n ng÷ mê h÷u h¹n lµ mét hµm tõ S* vµo R³0. Cho G lµ CMG. Khi ®ã lG lµ ng«n ng÷ mê ®­îc sinh ra bëi G vµ lLG lµ ng«n ng÷ mê ®­îc sinh ra bëi G chØ sö dông suy dÉn tr¸i nhÊt §Þnh lý 4.4 Cho G lµ mét CMG. Khi ®ã lG=lLG Chøng minh: §Æt G=(T,N,P,h). Nã lµ ®ñ ®Ó chØ ra r»ng ®èi víi tÊt c¶ AÎN, xÎT* vµ pÎ R³0, nÕu AÃp x(mod w) ®èi víi wÎ(P´N)* th× AÃpL x(mod w’) ®èi víi w’Î(P´{1})* §iÒu nµy cã thÓ ®­îc hoµn thµnh bëi ph­¬ng ph¸p quy n¹p trªn §Þnh nghÜa 4.5 Cho l lµ mét ng«n ng÷ mê h÷u h¹n trªn T. l ®­îc gäi lµ mét ng«n ng÷ mê phi ng÷ c¶nh h÷u h¹n (CFFL) nÕu l=lG ®èi víi CMG G. MÖnh ®Ò 4.6 Cho l lµ mét CFFL trªn T. Khi ®ã l=lG ®èi víi CMG G=(T,N,P,h) sao cho tháa m·n c¸c tÝnh chÊt d­íi ®©y: (1)-Tån t¹i A0ÎN sao cho h(A0)=1 vµ (Ax) ÎP hµm ý A0 kh«ng xuÊt hiÖn trong x. (2) §èi víi mäi AÎN vµ xÎ(TÈN)*, (Ax) ÎP vµ (Ax) ÎP hµm ý p1=p2 >0 (3)- §èi víi mäi AÎN, tån t¹i u,vÎT* vµ wÎ(P´N)* sao cho lw(A0,uAv)>0 (4)- §èi víi mäi AÎN, tån t¹i u,vÎT* vµ wÎ(P´N)* sao cho lw(A,x)>0 Mét CMG tháa m·n ®iÒu kiÖn (1) ®Õn (4) cña mÖnh ®Ò 4.6 ®­îc gäi lµ ®­îc thu gän. MÖnh ®Ò 4.8 Cho G=(T,N,P,h) lµ mét CMG thu gän. Khi ®ã lG lµ h÷u h¹n nÕu vµ chØ nÕu ®èi víi mäi AÎN vµ wÎ(P´N)* th× lw(A,A)£1 Bæ ®Ò 4.9 Cho l lµ mét CFFL h÷u h¹n. Khi ®ã l=lG ®èi víi nh÷ng CMG thu gän G=(T,N,P,A) trong ®ã P kh«ng chøa bÊt kú quy t¾c mê cã d¹ng AA vµ víi AÎN\{A0}. Chøng minh: §Æt l=lG, trong ®ã G0=(T,N,P0,A0) lµ mét CMG. §èi víi mäi quy t¾c mê Ax0A1x1A2...xnAn trong P0, víi n³0, mäi AiÎN vµ x=x0x1...xnÎ(TÈN)+, ®Æt Ax lµ mét quy t¾c mê sao cho p’=pÕni=1q(Ai)>0. Khi ®ã, ®èi víi mçi BÎN, q(B)=ÙwÎW*lW(B,A), víi W=P0´N. §Æt G=(T,N,P,A0) lµ CMG trong ®ã P lµ tËp c¸c quy t¾c mê thu ®­îc trong c¸ch m« t¶ ë trªn céng víi quy t¾c mê A0A, víi p=lG(A). Râ rµng (A0A)ÎP hµm ý A=A0. H¬n n÷a, nã cã thÓ ®­îc chØ ra r»ng l=lG. NÕu G kh«ng lµ mét CMG thu gän, nã cã thÓ dÔ dµng ®­îc ®­a vµo d¹ng thu gän mµ vÉn gi÷ thuéc tÝnh mong muèn. §Þnh lý 4.10 l lµ mét CFFL h÷u h¹n nÕu vµ chØ nÕu l=lG ®èi víi nh÷ng CMG thu gän G=(T,N,P,A0), trong ®ã P kh«ng chøa bÊt kú quy t¾c mê cã d¹ng AB víi A,BÎN vµ AA víi AÎN\{A0} Chøng minh: Gi¶ sö r»ng l lµ mét CFFL h÷u h¹n. V× bæ ®Ò 4.9, l=lG ®èi víi nh÷ng CMG rót gän G=(T,N,P0,A0), trong ®ã AAÎP0 hµm ý A=A0. Cho x lµ hµm tõ (TÈN)*´(TÈN)* vµo R³0 sao cho ®èi víi mäi s,tÎ(TÈN)* x(s,t)= §Æt xn, n=0,1,2..., lµ hµm tõ (TÈN)*´(TÈN)* vµo R³0 ®­îc ®Þnh nghÜa mét c¸ch ®Ö quy nh­ sau x0(s,t)= xn+1(s,t)= §Æt x’ Lµ hµm tõ (TÈN)*´(TÈN)* vµo R³0 sao cho ®èi víi mäi s,tÎ(TÈN)* x’(s,t)= §Æt G=(T,N,P,A0) lµ CMG, trong ®ã P lµ tËp tÊt c¶ quy t¾c mê st trong ®ã x’(s,t)=p>0. Suy ra G cã nh÷ng tÝnh chÊt mong muèn. Cho xÎT*. §èi víi mäi wÎ(P´N)+ vµ e>0 tån t¹i w0Î(P0´N)+ sao cho lw(A,x)>lw0(A,x)-e. H¬n n÷a ®èi víi mäi w0Î(P0´N)+ tån t¹i wÎ(P´N)+ sao cho lw0(A,x)£ lw(A,x). Nh­ vËy l=lG. MÖnh ®Ò ®¶o d­íi ®©y xuÊt ph¸t tõ ®iÒu ®ã. lG(x)=Ù{Ú{h(A)lw(A,x) | AÎN} | wÎ(P´N)*, £} §Þnh lý 4.11 (D¹ng chuÈn t¾c chomsky): l lµ mét CFFL h÷u h¹n nÕu vµ chØ nÕu l=lG ®èi víi c¸c CMG rót gän G=(T,N,P,A0), trong ®ã P chØ chøa nh÷ng quy t¾c mê d¹ng A0A vµ Aa vµ ABC víi A,B,CÎN vµ aÎT §Þnh lý 4.12 (D¹ng chuÈn t¾c Greibach): l lµ mét CFFL h÷u h¹n nÕu vµ chØ nÕu l=lG ®èi víi c¸c CMG rót gän G=(T,N,P,A0), trong ®ã P chØ chøa nh÷ng quy t¾c mê cã d¹ng A0A vµ Aaz víi AÎN vµ aÎT vµ zÎN* 2 Nãi chung, ®Þnh lý 4.11 vµ 4.12 kh«ng cßn ®óng nÕu l kh«ng h÷u h¹n, trõ khi ta më réng ®Þnh nghÜa cña nh÷ng quy t¾c mê gåm Ax víi p= 5. Ng«n ng÷ phi ng÷ c¶nh mê Trong phÇn nµy, ta nghiªn cøu tËp c¸c ng«n ng÷ ®­îc sinh bëi v¨n ph¹m max-product phi ng÷ c¶nh. Cho l lµ mét ng«n ng÷ mê trªn T vµ rÎR³0. §¨t L(l,r,>) biÓu thÞ tËp {xÎT* | l(x)>r}, L(l,r,³) biÓu thÞ tËp {xÎT* | l(x) ³r}, vµ L(l,r,=) biÓu thÞ tËp {xÎT* | l(x)=r} §Æt G=(T,N,P,A0) lµ mét CMG. Khi ®ã xÎL(l,r,>) nÕu vµ chØ nÕu tån t¹i wÎ(P0´N)* sao cho AÃp x(mod w) vµ p>r. Mét v¨n ph¹m lµ mét bé bèn G=(T,N,P,A0) trong ®ã T lµ ký hiÖu kÕt thóc vµ N lµ ký hiÖu kh«ng kÕt thóc, sao cho TÇN=Æ, P lµ mét tËp h÷u h¹n c¸c quy t¾c, vµ A0ÎN lµ ký hiÖu b¾t ®Çu. Suy dÉn theo G, ng«n ng÷ L(G) ®­îc sinh ra bëi G, vµ nh÷ng lo¹i v¨n ph¹m kh¸c nhau trong ph©n cÊp Chomsky ®­îc ®Þnh nghÜa trong c¸ch th«ng th­êng. §Þnh lý 5.1 L lµ mét ng«n ng÷ phi ng÷ c¶nh (CFL) nÕu vµ chØ nÕu L=L(l,r,>) ®èi víi nh÷ng CFFL l Chøng minh: Gi¶ sö l=lG, trong ®ã G=(T,N,P,A0) lµ mét CMG. §Æt G’=(T,N,P’A0) lµ mét v¨n ph¹m phi ng÷ c¶nh, trong ®ã P’={st | (st)ÎP vµ p>0}. Khi ®ã nã kÐo theo L=L(G’). DÔ dµng chøng minh ®­îc chiÒu ng­îc l¹i. §Þnh nghÜa 5.2 §èi víi mäi aÎT, cho Ta lµ mét tËp kh¸c rçng h÷u h¹n vµ Y:Ta*P(Ta*). Gi¶ sö r»ng Y(A)={A} vµ Y(ax)=Y(a)Y(x) ®èi víi mäi aÎT vµ mäi xÎT*. Th× Y ®­îc gäi lµ mét phÐp thÕ. NÕu LÍT*, ®Æt Y(L)=ÚxÎLY(x) §Þnh nghÜa 5.3 Mét bé chuyÓn ®æi lµ mét bé s¸u M=(X,Q,Y,H,q0,F) víi X, Q vµ Y lµ nh÷ng tËp kh¸c rçng h÷u h¹n, H lµ mét tËp h÷u h¹n Q´X*´Y*´Q, q0ÎQ lµ ph¸t biÓu ban ®Çu, FÍQ lµ tËp c¸c ph¸t biÓu chÊp nhËn. Cho M=(X,Q,Y,H,q0,F) lµ mét bé chuyÓn ®æi. §èi víi mçi xÎX*, ®Æt M(x)={yÎY* | $ x1,x2,...,xkÎX* vµ y1,y2,...,ykÎY* vµ q1,q2,...,qkÎQ sao cho x=x1x2...xk, y=y1y2...yk, qkÎF vµ (qi-1,xi,yi,qi)ÎH ®èi víi mäi i =1..k}. §èi víi mçi LÍX*, ®Æt M(L)=ÈxÎLM(x). NÕu L lµ mét CFL vµ M lµ bé chuyÓn ®æi, th× M(L) lµ mét CFL. NÕu L lµ mét CFL vµ Y lµ mét phÐp thÕ sao cho Y(a) lµ mét CFL ®èi víi tÊt c¶ a th× Y(L) còng lµ mét CFL. §Þnh lý 5.4 L lµ mét CFL nÕu vµ chØ nÕu L=L(lG,r,>) ®èi víi mét sè CMG chÆt G vµ r ÎR³0 Chøng minh: §Æt L= L(lG,r,>), trong ®ã G=(T,N,P,A0) lµ mét CMG chÆt vµ r ÎR³0 . Kh«ng mÊt tÝnh tæng qu¸t, ta gi¶ sö N=N1ÈN2, trong ®ã (1)- N1ÇN2 = Æ (2)- A0ÎN1 (3)- NÕu (Ax)ÎP th× AÎN1 (4)- NÕu (Ax)ÎP vµ p<1 th× AÎN2 §Æt P1 lµ tËp hîp cña tÊt c¶ quy t¾c mê trong P cã d¹ng Ax, vµ ®Æt P2=P\P1. §èi víi tÊt c¶ r=AxÎP2, ®Æt Mr=(X,Q,Y,H,q0,{q1}) lµ mét bé chuyÓn ®æi, trong ®ã X=TÈN2, Q={q0,q1}, Y=TÈN, vµ H={(q,u,u,q) | qÎQ, uÎTÈN2 }È{(q0,A,x,q1)}. Chó ý r»ng nÕu L0 Í(TÈN2)*, th× Mr(L0) thu ®­îc tõ L b»ng c¸ch bá qua tÊt c¶ nh÷ng tõ trong L0 kh«ng chøa bÊt kú xuÊt hiÖn cña A, vµ sau ®ã thay thÕ ®óng mét xuÊt hiÖn cña A bëi x trong nh÷ng tõ cßn l¹i cña L0. §èi víi tÊt c¶ AÎN1, ®Æt L(A)=(lGA,0,>), víi GA=(TÈN2,N1,P1, A) Râ rµng, L(A) lµ mét CFL ®èi víi tÊt c¶ AÎN1. §Æt Y lµ mét phÐp thÕ sao cho Y(A)=L(A) nÕu AÎN1 vµ y(A)={a} nÕu aÎTÈN2. §èi víi tÊt c¶ L1, L2Í(TÈN2)* vµ kÎN, ®Þnh nghÜa L1L2 nÕu vµ chØ nÕu tån t¹i L0’,L1’,...,Lk’Í(TÈN2)* sao cho L1=L0’, L2=Lk’ vµ Li-1Li ®èi víi i=1,2...,k. §Þnh nghÜa L1Ãk L2 nÕu vµ chØ nÕu L3Í(TÈN2)* sao cho L1Ãk L3 vµ L2=L3ÇT*. Râ rµng nÕu L1 lµ mét CFL vµ L1Ãk L2 ®èi víi k th× L2 còng lµ mét CFL. V× r>0 nªn tån t¹i nÎN sao cho xÎL hµm ý xÎL2 ®èi víi c¸c L2ÍT*, trong ®ã y(A0)Ãk L2 vµ k£n. §Æt G={L2 Í T* | y(A0) à k L2 ®èi víi k £ n vµ L2ÇL ¹ Æ}. Suy ra L2ÎG hµm ý L2ÍL. Do ®ã L=ÈL2ÎGL2. V× vËy, L lµ mét CFL. DÔ dµng chøng minh ®­îc ®iÒu ng­îc l¹i. (§PCM) §Þnh lý 5.5 Cho G=(T,N,P,A0) lµ mét CMG, trong ®ã tån t¹i c) lµ h÷u h¹n ®èi víi tÊt c¶ r ÎR³0 Chøng minh: Râ rµng, lG lµ mét CFFL h÷u h¹n. Nh­ vËy, theo ®Þnh lý 4.12, lG = lG1 ®èi víi CMG G1 mµ trong d¹ng chuÈn t¾c Greibach. §Æt n lµ sè nguyªn lín nhÊt sao cho cn > r. Khi ®ã xÎL(lG1,r,>) hµm ý £ n. Nh­ vËy L(lG,r,>)= L(lG1,r,>) lµ h÷u h¹n (§PCM) Chó ý, §Þnh lý 5.4 vµ ®Þnh lý 5.5 cßn ®óng nÕu > ®­îc thay bëi ³ §Þnh lý 5.6 Cho l lµ mét CFFL. Khi ®ã L(l,¥,=) lµ mét CFL. Chøng minh: §Æt l=lG, trong ®ã G=(T,N,P,A0) lµ mét CMG. B»ng nhËn xÐt sau ®Þnh lý 4.11 vµ 4.12, ta cã thÓ gi¶ sö r»ng G lµ trong d¹ng chuÈn t¾c Greibach víi ®iÒu kiÖn lµ ta cho nh÷ng quy t¾c mê cã d¹ng st, víi p=¥. §èi víi tÊt c¶ aÎT, ®Æt a’ mét ký hiÖu míi vµ ®Æt T’={a’| aÎT}. §èi víi tÊt c¶ xÎ(TÈN)* ®Æt x’Î(T’ÈN)*, trong ®ã x’ thu ®­îc tõ x b»ng c¸ch thay thÕ tÊt c¶ aÎT trong x bëi a’. §Æt G=(TÈT’, N, P0,A0) lµ v¨n ph¹m phi ng÷ c¶nh, trong ®ã P0={Ax | AxÎP vµ p<¥}È{Ax’ | AxÎP vµ p=¥}. §Æt M=(X,Q,Y,H,q0,{q1}) lµ mét bé chuyÓn ®æi trong ®ã X=TÈT’, Q={q0,q1}, Y=T, vµ H={(q,u,u,q) | uÎT, qÎQ}È{(q,a’,a,q1) | aÎT, qÎQ} §èi víi tÊt c¶ L0ÍTÈT’)*, M(L0) thu ®­îc tõ L0 b»ng c¸ch bá tÊt c¶ nh÷ng tõ trong L0 mµ kh«ng chøa a’ÎT, vµ sau ®ã thay thÕ tÊt c¶ a’ÎT’ bëi a t­¬ng øng aÎT trong nh÷ng tõ cßn l¹i. V× G lµ mét d¹ng chuÈn t¾c Greibach nªn xÎL(l,¥,=) nÕu vµ chØ nÕu x ®­îc sinh ra tõ A b»ng c¸ch sö dông Ýt nhÊt mét quy t¾c mê cã d¹ng (Ax)ÎP víi p=¥. Nh­ vËy L=M(L(G0)). V× vËy L lµ mét CFL. (§PCM) Cho rÎR³0. §Æt Lr={L(l,r,>) | l lµ mét CFFL} vµ L=Lr. §Æt C lµ hä cña tÊt c¶ CFL vµ R lµ hä cña tÊt c¶ ng«n ng÷ chÝnh quy. §Þnh lý 5.7 L0=C. ViÖc chøng minh ®­îc suy ra tõ ®Þnh lý 5.1. §Þnh lý 5.8 Cho rÎR³0. Khi ®ã CÍLr. Chøng minh: §Æt LÎC. Khi ®ã L=L(G) ®èi víi v¨n ph¹m phi ng÷ c¶nh G=(T,N,P,A0). §Æt p=1+r vµ G’=(T,N,P’,A0) lµ mét CMG, trong ®ã P’={Ax | (Ax)ÎP}. Suy ra L=L(lG,r,>). Do ®ã LÎLr. V× vËy CÍLr (§PCM) §Þnh lý 5.9 Cho rÎR vµ r>0. Khi ®ã L=Lr Chøng minh: §Æt LÎL. Khi ®ã L=L(lG1,r,>) ®èi víi CMG G1=(T,N,P, h1) vµ r1³ 0. Theo ®Þnh lý 5.7 vµ 5.8, nã lµ ®ñ ®Ó xem xÐt tr­êng hîp víi r1>0. §Æt G=(T,N,P,h) trong ®ã h(A)=r/r1 h1(A) ®èi víi tÊt c¶ AÎN. Râ rµng L=L(lG,r,>). Do ®ã LÎLr . V× vËy LÍ Lr . V× Lr Í L nªn L= Lr (§PCM) §Þnh lý 5.10 LÎL nÕu vµ chØ nÕu L=L(l,r,>) ®èi víi CFFL l h÷u h¹n vµ rÎR³0. Chøng minh: §Æt LÎL. Theo ®Þnh lý 5.9 L=L(lG,1/2,>) ®èi víi CMG G=(T,N1,P1,A1). Tõ theo ®Þnh lý 4.11 vµ 4.12, ta cã thÓ gi¶ sö r»ng G trong d¹ng chuÈn t¾c Greibach víi ®iÒu kiÖn lµ ta chÊp nhËn nh÷ng quy t¾c mê cã d¹ng Ax, víi p=¥. Theo ®Þnh lý 5.6 L(lG,¥=)=L(G2) ®èi víi ng«n ng÷ phi ng÷ c¶nh G2=(T,N2,P2,A2). Gi¶ sö r»ng G2 còng lµ d¹ng chuÈn t¾c Greibach vµ N1ÇN2 =Æ. §Æt A0ÏTÈN1ÈN2. §Æt G=(T,N,P,A0) lµ mét CMG, trong ®ã N=N1ÈN2È{A0}, vµ P gåm tÊt c¶ quy t¾c mê cã d¹ng sau: Ax, trong ®ã (Ax) Î P1 vµ p<¥ A0x, trong ®ã (Ax) Î P1 vµ p<¥ Ax trong ®ã (Ax) ÎP2 A0x trong ®ã (Ax) ÎP2 Râ rµng, G lµ trong d¹ng chuÈn t¾c Greibach. V× vËy theo ®Þnh lý 4.12, lG lµ h÷u h¹n. Suy ra L=L(lG,1/2,>). DÔ dµng chøng minh ®iÒu ng­îc l¹i. §Þnh lý 5.11 C lµ mét hä con riªng biÖt cña L. Chøng minh: Cho L={anbncm | n³m³1}. Ta cã LÏC. B©y giê ®Æt G=({a,b,c},{A0,A1,A2},P,A0) lµ mét CMG trong ®ã P gåm cã nh÷ng quy t¾c mê A0 A1A2, A1 aA1b, A1 ab, A2 A2, A2 c. Suy ra L=L(lG,b,>). Nh­ vËy LÏL Ta viÕt sÃp t nÕu sÃp t(mod w) ®èi víi mét sè w. Bæ ®Ò 5.12 §èi víi tÊt c¶ L trong ®ã L=L(lG,b,>) ®èi víi mét sè CMG G vµ rÎR³0, tån t¹i nÏN sao cho mäi tõ xÏL víi >n cã d¹ng s1s2s3s4s5, víi s2¹A vµ hoÆc s1s2ks3s4ks5ÎL ®èi víi mäi kÎN hoÆc s1s3s5ÎL. Chøng minh: Theo ®Þnh lý 4.12, 5.9 vµ 5.10, L=L(lG,b,>), trong ®ã G=(T,N,P,A0) lµ mét CMG trong d¹ng chuÈn t¾c Greibach. §Æt =m, nÕu x=s1s2s3s4s5ÎL vµ >m, suy ra cã mét AÎN sao cho A0Ãp1s1At1 Ãp2s1s2At2t1Ãp3s1s2s3s4s5=x, trong ®ã siÎT*, tiÎN*, s2¹A, AÃp4s3, t2Ãp5s4, t1Ãp6s5, p4p5p6=p3, vµ p1p2p3>1. DÔ dµng kiÓm tra l¹i r»ng (1) nÕu p2p5³1 th× s1s2ks3s4ks5ÎL "kÎN vµ (2) nÕu p2p5<1 th× s1s3s5ÎL. (§PCM) §Þnh lý 5.13 {anbncn | n³1}ÏL . Chøng minh: Gi¶ sö r»ng L={anbncn | n³1}ÎL. Theo ®Þnh lý 4.12, 5.9 vµ 5.10, L=L(lG,1,>), trong ®ã G=(T,N,P,A) lµ mét CMG trong d¹ng chuÈn t¾c Greibach. §Æt =m vµ ®Æt x= s1s2s3s4s5s6s7 ÎL, trong ®ã >m2. Khi ®ã tån t¹i AÎN sao cho: A0s1At1 s1s2At2t1 s1s2s3At3t2t1s1s2s3s4s5s6s7. Víi siÎT*, tiÎN*, s2s3¹e, AÃp5s3, t3Ãp6s5, t1Ãp7s7, p5p6p7p8=p4, vµ p1p2p3p4>1. Tõ bæ ®Ò 5.12, ta thÊy r»ng kh«ng ph¶i p2p7³1 mµ còng kh«ng ph¶i p3p6³1. Tuy nhiªn, nÕu p2p7<1 vµ p3p6<1 th× theo bæ ®Ò 5.12, s1s2s4s6s7 vµ s1s3s5s6s7 lµ thuéc L. §iÒu nµy lµ kh«ng thÓ x¶y ra. Nh­ vËy LÏL. (§PCM) §Þnh lý 5.14 Tån t¹i mét ng«n ng÷ c¶m ng÷ c¶nh mµ kh«ng thuéc L. Sö dông ®Þnh lý 5.13 vµ 5.11 ta chøng minh ®­îc ®Þnh lý nµy 6. C©y vµ gi¶ sè h¹ng Cho N lµ tËp hîp c¸c sè tù nhiªn vµ N* lµ tËp hîp cña tÊt c¶ c¸c x©u trªn N bao gåm c¶ x©u rçng D. Mét tËp con ®ãng h÷u h¹n U cña N* ®­îc gäi lµ mét c©y ph¹m vi (tree domain) h÷u h¹n nÕu nh÷ng ®iÒu kiÖn sau ®­îc tháa m·n: (1) wÎU vµ w=uv hµm ý uÎU trong ®ã u,v,w ÎN*; (2) wnÎU vµ m£n hµm ý wmÎU, trong ®ã wÎN*, m,n,ÎN. Cho U lµ mét c©y ph¹m vi h÷u h¹n. Th× tËp con ={wÎU | w.1ÏU} ®­îc gäi lµ nót l¸. Mét cÆp (N,T) cña nh÷ng b¶ng ch÷ h÷u h¹n N vµ T, trong ®ã NÇT=Æ ®­îc gäi lµ mét b¶ng ch÷ ®­îc s¨p xÕp tõng phÇn. Mét c©y t trªn mét b¶ng ch÷ ®­îc s¾p xÕp tõng phÇn (N;T) lµ mét hµm tõ mét ph¹m vi c©y h÷u h¹n U vµo NÈT, ®­îc viÕt t: U(N;T), sao cho: t(w)ÎN ®èi víi wÎU\ t(w)ÎT ®èi víi wÎ TÊt nhiªn, mét c©y h÷u h¹n t: U(N;T), cã thÓ ®­îc biÓu diÔn bëi mét tËp h÷u h¹n c¸c cÆp (w,t(w)), nghÜa lµ {(w,t(w)) | wÎU} g f b a b a f 1 11 a 111 112 g 12 121 122 f 2 21 b 22 Nh÷ng c©y trªn (N;T) cã thÓ ®­îc biÓu diÔn b»ng ®å thÞ b»ng c¸ch x©y dùng mét c©y gèc (trong ®ã mçi nót kÕ tiÕp ®­îc ®¸nh sè thø tù) biÓu diÔn ph¹m vi cña ¸nh x¹, vµ nh·n cña nh÷ng nót víi nh÷ng phÇn tö cña NÈT biÓu diÔn gi¸ trÞ cña hµm. Trong h×nh d­íi ®©y cã hai vÝ dô, mét ¸nh x¹, c©y bªn tr¸i cã miÒn U={, 1,2,11,12} vµ gi¸ trÞ t¹i 11 lµ a. Còng chó ý r»ng ={2,11,12} A B 1 11 a 12 b a 2 Sù ®Þnh nghÜa cña mét c©y vµ sù biÓu diÔn b»ng h×nh vÏ t­¬ng øng cung cÊp mét c¬ së tèt cho trùc gi¸c ®Ó xem xÐt hÖ thèng c©y thao t¸c. Tuy nhiªn, sù ph¸t triÓn cña lý thuyÕt sÏ ®¬n gi¶n h¬n nÕu sù biÓu diÔn tuyÕn tÝnh quen thuéc cña nh÷ng c©y nh­ vËy ®­îc xem xÐt. V× vËy, ta ®Þnh nghÜa tËp DP(N;T) cña gi¶ sè h¹ng trªn NÈT nh­ tËp con nhá nhÊt cña [NÈTÈ{(,)}]* tháa m·n nh÷ng ®iÒu kiÖn d­íi ®©y: (1) T Ì DP(N;T) (2) NÕu n>0 vµ AÎN vµ t1,t2,...,tnÎDP(N;T) th× A(t1,t2,...,tn )ÎDP(N;T). (chó ý: dÊu ngoÆc ®¬n kh«ng ph¶i ký hiÖu cña NÈT) Ta xÐt nh÷ng c©y vµ gi¶ sè h¹ng lµ sù h×nh thøc hãa t­¬ng ®­¬ng. Víi vÝ dô trªn, c¸c c©y t­¬ng øng víi gi¶ sè h¹ng d­íi ®©y: A(B(a b)a), f(g(f(ab) g(ab) f(ab)) Sù t­¬ng ®­¬ng nµy cã thÓ ®­îc thùc hiÖn nh­ d­íi ®©y: (1)-NÕu mét gi¶ sè h¹ng tPÎDP(N;T) lµ nguyªn tè, nghÜa lµ tP=aÎT th× c©y t t­¬ng øng cã ph¹m vi {} vµ t{}=a. (2)-NÕu tP=A(tP1, tP2,..., tPm) th× t cã ph¹m vi Èi£m{iw | wÎph¹m vi (ti)}È{}, t()=A, vµ ®èi víi w=iw’ trong ph¹m vi cña t, t(w)=ti(w’). Ta biÓu thÞ tËp c¸c c©y trªn (N;T) b»ng DP(N;T), c¸c phÇn tö cña nã bëi t, vµ c¸c gi¶ sè h¹ng t­¬ng øng víi mét c©y t bëi p(t) hoÆc tP. Mét tËp T mê cña c¸c c©y ®­îc ®Þnh nghÜa bëi mét hµm thuéc mT: DP(N;T) [0,1]. TËp tÊt c¶ c¸c tËp mê cña c¸c c©y ®­îc biÓu thÞ bëi F(DP(N;T)) 7. Nh÷ng hÖ thèng sinh ng«n ng÷ mê §Þnh nghÜa 7.1 Mét hÖ thèng sinh ng«n ng÷ phi ng÷ c¶nh mê (F-CFDS) lµ bé n¨m S=(N0,N,T,P,l0) sao cho nh÷ng ®iÒu kiÖn d­íi ®©y ®­îc tháa m·n: (1)- N0 lµ mét tËp h÷u h¹n c¸c ký hiÖu mµ phÇn tö cña nã ®­îc gäi lµ ký hiÖu nót kh«ng kÕt thóc. (2)- N lµ mét tËp h÷u h¹n c¸c ký hiÖu mµ phÇn tö cña nã ®­îc gäi lµ ký hiÖu nót. (3)- T lµ mét tËp h÷u h¹n c¸c ký hiÖu mµ phÇn tö cña nã ®­îc gäi lµ ký hiÖu l¸. (4)-P lµ tËp h÷u h¹n c¸c quy t¾c viÕt l¹i mê cã d¹ng m(l,t)=c mµ cã thÓ biÓu diÔn lt, tÎ; cÎ[0,1] hoÆc t­¬ng ®­¬ng víi l p(t); p(t) lµ mét gi¶ sè h¹ng t­¬ng øng míi mét c©y t. (5)- l0ÎN0 lµ mét nót ký hiÖu kh«ng kÕt thóc khëi ®éng. §Þnh nghÜa quan hÖ mê trªn tËp cña c©y nh­ d­íi ®©y: §èi víi tÊt c¶ a,bÎ a b nÕu vµ chØ nÕu: p(a)=xly p(b)=xp(t)y lt thuéc P, trong ®ã x,yÎ[NÈN0ÈTÈ{(,)}]*, lÎN0 vµ tÎ. H¬n n÷a, ®Þnh nghÜa bao ®ãng b¾c cÇu cña quan hÖ mê nh­ sau: aa ®èi víi mäi aÎ a b nÕu vµ chØ nÕu c=ÚcÎ{c’Ùc’’ | ag, gb} §Þnh nghÜa 7.2 TËp mê D(S)={(t;c) | l0 cÎD(N;T)} ®­îc gäi lµ mét ng«n ng÷ phi ng÷ c¶nh mê (F-CFDL) ®­îc sinh ra bëi F-CFDS, S VÝ dô 7.3 Gi¶ sö N0={l,x,h}, N={A}, T={a} vµ P ®­îc cho nh­ sau: A a l l l a A x h l A x a x xa A h a h ha Khi ®ã F-CFDS, S=(N0,N,T,P,l) sinh ra CFDS, D(S)={(t;0.7) | p(t)=A( A(aa) , n³0}È{(t;0.6) | p(t)=(A(aa), n³ 1} VÝ dô, nh­ mét suy dÉn, ta cã: A A h A a A x a A A h A x a A x h l A A h A a A a a A A a A a A a a hoÆc mét c¸ch t­¬ng ®­¬ng: l A(xh) A(A(xa)h) A(A(A(xa)a)h) (A(A(A(aa)a)h) A(A(A(aa)a)a). 8. D¹ng chuÈn t¾c cña F-CFDS §é s©u cña c©y t víi ph¹m vi Ut ®­îc ®Þnh nghÜa bëi d(t)=Ú{ | wÎUt} trong ®ã lµ ®é dµi cña w. BËc cña F-CFDS ®­îc ®Þnh nghÜa lµ gi¸ trÞ lín nhÊt cña c¸c ®é s©u cña c©y xuÊt hiÖn trong vÕ ph¶i cña quy t¾c. Hai F-CFDS ®­îc gäi lµ t­¬ng ®­¬ng nÕu chóng sinh ta cïng mét ng«n ng÷ mê. Trong phÇn nµy, ta chØ ra r»ng ®èi víi bÊt kú F-CFDS cã mét F-CFDS t­¬ng ®­¬ng cã bËc 1 nghÜa lµ c¸i mµ quy t¾c cña nã cã d¹ng: A x1 x2 ... xk l a hoÆc l (k³1) trong ®ã l, xiÎN0 (i=1,...,k), AÎN, vµ aÎT. Bæ ®Ò 8.1 Cho S=(N0,N,T,P,l0) lµ mét F-CFDS cã bËc n (n³2). Khi ®ã tån t¹i mét F-CFDS t­¬ng ®­¬ng cã bËc n-1 Chøng minh Ta x¸c ®Þnh mét F-CFDS míi, S’=(N0’,N,T,P’,l0) tõ F-CFDS ®· cho. P’ ®­îc ®Þnh nghÜa nh­ sau: §èi víi mçi quy t¾c lt trong P, (1)-NÕu d(t)<n th× lt lµ thuéc P’ (2)-NÕu d(t)=n vµ p(t)=X(p(t1)...p(tk)), th× A x1 x2 ... xk l vµ xi ti ®èi víi tÊt c¶ i sao cho p(ti)ÏN0 lµ thuéc P’, trong ®ã xi lµ mét ký hiÖu nót kh«ng kÕt thóc míi riªng biÖt nÕu p(ti)ÏN0 vµ xi =p(ti) nÕu p(ti)ÎN0. Râ rµng, N0’ lµ mét hîp cña N0 vµ tËp tÊt c¶ c¸c ký hiÖu nót kh«ng kÕt thóc míi ®­îc ®­a ra bëi viÖc ¸p dông nh÷ng quy t¾c (2) ë trªn. Gi¶ sö a b trong S. Khi ®ã p(a)=xly, p(b)=xp(t)y vµ lt thuéc P. NÕu d(t)<n th× sù x©y dùng ë trªn cho thÊy ab trong S’ v× lt còng ®­îc chøa trong P’. NÕu d(t)=n, ta cã b»ng sù x©y dùng ë trªn mµ p(a)=xly xX(x1...xk)y xX(p(t1)...p(tk))y=p(b). §¶o l¹i, nÕu xly xX(x1...xk)y trong S’ th× xi ti; i=1,...,k ph¶i ®­îc ¸p dông v× c¸c ký hiÖu kh«ng kÕt thóc xi chØ cã thÓ ®­îc viÕt l¹i bëi chóng. Nh­ vËy xly xX(x1...xk)y xX(p(t1)...p(tk))y. §èi víi suy dÉn nµy ta cã: xly xp(t)y trong S. Do ®ã D(S)=D(S’). Tõ thñ tôc x©y dùng cña S’, râ rµng r»ng S’ cã bËc n-1 (§PCM). Bæ ®Ò 8.2 §èi víi bÊt kú F-CFDS, tån t¹i mét F-CFDS t­¬ng ®­¬ng S’ cã bËc b»ng 1. Chøng minh: B»ng c¸ch lÆp l¹i viÖc ¸p dông bæ ®Ò 8.1, ta chøng minh ®­îc bæ ®Ò nµy. §Þnh lý 8.3 §èi víi bÊt kú F-CFDS tån t¹i mét F-CFDS t­¬ng ®­¬ng mµ nh÷ng quy t¾c cña nã cã d¹ng A x1 x2 ... xk (1) l a hoÆc (2) l (k³1) Trong ®ã l, xi i=1,2,...,k lµ nh÷ng ký hiÖu nót kh«ng kÕt thóc, a lµ mét ký hiÖu l¸, vµ A lµ mét ký hiÖu nót kÕt thóc. Chøng minh §Æt S lµ mét F-CFDS. Theo bæ ®Ò 8.2, tån t¹i mét F-CFDS t­¬ng ®­¬ng mµ nh÷ng quy t¾c cña nã lµ cã d¹ng d­íi ®©y: A x1 x2 ... xk (1) l a hoÆc (2) l xi ÎTÈN0 Nh­ vËy, nÕu ta thay thÕ quy t¾c cña d¹ng (2) bëi quy t¾c A x1 x2 ... xk l trong ®ã xi=Xi nÕu XiÎN0 vµ xi lµ mét ký hiÖu míi nÕu XiÎT, vµ nh÷ng quy t¾c xi Xi ®èi víi tÊt c¶ XiÎT th× ta thu ®­îc F-CFDS mong muèn. (§PCM) Mét F-CFDS mµ nh÷ng quy t¾c cña nã cã d¹ng (1) hoÆc (2) cña ®Þnh lý 8.3 ®­îc gäi lµ chuÈn t¾c. VÝ dô 8.4 XÐt tËp hîp c¸c quy t¾c d­íi ®©y B x A l b A l B x a l x A a b A b a l x §iÒu nµy cho thÊy mét F-CFDS cã bËc 2. D¹ng chuÈn t¾c ®èi víi F-CFDS ®­îc cho bëi nh÷ng quy t¾c d­íi ®©y: B x l2 A l1 l l l1 l1a A l l4 B l3 x x l3 l4b B l5 l6 x l5a l6b A l7 l8 l l7b l8a 9. TËp c¸c c©y suy dÉn cña v¨n ph¹m phi ng÷ c¶nh mê Trong phÇn nµy ta ®Þnh nghÜa tËp hîp nh÷ng c©y suy dÉn cña v¨n ph¹m phi ng÷ c¶nh mê nh­ nh÷ng tËp mê cña c¸c c©y vµ biÓu thÞ chóng lµ F-CFDS §Þnh nghÜa 9.1 Mét v¨n ph¹m phi ng÷ c¶nh mê (F-CFG) lµ mét bé bèn G=(N,T,P,S) trong ®ã (1)-N lµ mét tËp ký hiÖu kh«ng kÕt thóc. (2)-T lµ mét tËp ký hiÖu kÕt thóc. (3)-P lµ tËp nh÷ng quy t¾c mê. (4)-S lµ mét ký hiÖu kh«ng kÕt thóc khëi ®éng. §èi víi mét suy dÉn w0(=S) w1w2... wm(=w) trong mét v¨n ph¹m phi ng÷ c¶nh mê G, ta ®Þnh nghÜa mét c©y suy dÉn cã ®é thuéc nh­ sau: (1)-§èi víi w0 (=S), (aw0;1)=({A,S)};1) (2)-Gi¶ sö (;c) ®­îc cho ®èi víi mét sè i vµ wi-1 wi ®­îc nhËn ra bëi A Y1Y2...Yk (YiÎNÈT) víi wi-1= xAy vµ wi=xY1Y2...Yky. (Gi¶ sö ký hiÖu A ®­îc thay thÕ bëi Y1Y2...Yk t­¬ng øng víi mét nót l¸ u trong ). Khi ®ã (awi;c’) ®­îc cho bëi = È {(u.i,Yi) | 1£i£k, (u,A)ÎaxAy, uÎ} Trong ®ã lµ tËp nót l¸ cña vµ víi c’=cÙci. §Æt DG lµ mét tËp mê cña nh÷ng c©y trªn (N;T) ®­îc ®Þnh nghÜa nh­ trªn cho tÊt c¶ nh÷ng suy dÉn cã thÓ cña mét v¨n ph¹m phi ng÷ c¶nh mê G. Khi ®ã DG ®­îc gäi lµ mét tËp mê cña nh÷ng c©y suy dÉn mê cña G. §Þnh lý 9.2 §èi víi mét F-CFG cho tr­íc, G=(N,T,PG,S), tån t¹i mét F-CFDS, S=(N0,NS,TS,l0) mµ sinh ra tËp mê DG cña c©y suy dÉn mê cña G. Chøng minh §Æt N0={lX | XÎN}, NS=N, TS=T vµ l0=lS. X¸c ®Þnh PS nh­ sau: NÕu X Y1Y2...Yk thuéc P th× X lY1 lY2 ... lYk lX thu ®­îc thuéc PS nÕu Yi = aÎT, th× lYi=a. V× sù thu ®­îc (,c’) tõ (,c) trong ®Þnh nghÜa cña DG t­¬ng ®­¬ng víi viÖc ¸p dông c¸c quy t¾c A lY1 lY2 ... lYk lA trong F-CFDS, nã kÐo theo DG=D(S) (§PCM) VÝ dô 9.3 XÐt F-CFG ®­îc cho bëi nh÷ng quy t¾c d­íi ®©y: S AB, A AB, BBA, Aa, Ab,Bb §èi víi F-CFG nµy, x©y dùng mét F-CFDS ®­îc x¸c ®Þnh bëi nh÷ng quy t¾c d­íi ®©y: A lA lA S lA lB lS lA A a B lB lA lB lA B b A b lA lB §èi víi suy dÉn cña F-CFG SABABAaBAabAabb C©y suy dÉn cña nã ®­îc sinh ra bëi F-CFDS nh­ sau: S lA B lB lA S a B lB lA S lA lB lS S a B b b S a B b lA §¶o l¹i cña ®Þnh lý 9.2. Ta chøng minh r»ng ®èi víi bÊt kú F-CFDS, tån t¹i mét F-CFG, G, t­¬ng ®­¬ng víi S trong nghÜa cña ®Þnh lý 9.5 d­íi ®©y. Cho h: [NÈTÈ{(,)}]* T lµ mét ®ång cÊu ®­îc ®Þnh nghÜa bëi h(a)=a ®èi víi a thuéc T vµ h(X)= ®èi víi XÏT . Bæ ®Ò 9.4 Cho S lµ mét F-CFDS, khi ®ã tËp mê p(D(S)) cña gi¶ sè h¹ng cña D(S) lµ mét ng«n ng÷ phi ng÷ c¶nh mê. Chøng minh Cho S=(N0,N,T,P,l0) lµ mét F-CFDS. X©y dùng mét F-CFG, G=(NG,TG,PG,SG) nh­ sau: §Æt NG=N0, TG = NÈTÈ{(,)}, SG=l0 vµ x¸c ®Þnh PG nh­ sau: NÕu lt thuéc P th× lp(t) thuéc PG. Tõ viÖc x©y dùng ë trªn, suy ra L(G)=p(D(S)) (§PCM) §Þnh lý 9.5 §èi víi bÊt kú F-CFDS,S, h(p(D(S))) lµ mét ng«n ng÷ phi ng÷ c¶nh mê trªn T. Chøng minh ViÖc chøng minh ®­îc kÐo theo tõ bæ ®Ò 9.4 vµ râ rµng mét ¶nh ®ång cÊu cña mét ng«n ng÷ phi ng÷ c¶nh mê còng lµ mét ng«n ng÷ phi ng÷ c¶nh mê §Þnh lý 9.6 Mäi F-CFDL lµ mét phÐp chiÕu cña mét tËp mê c¸c c©y suy dÉn cña mét F-CFG. Chøng minh §Æt S=(N0,N,T,P,l0) lµ mét F-CFDS chuÈn t¾c. XÐt F-CFG, G=(NG,TG,PG,SG), trong ®ã NG=N0´(NÈT), TG={(¦,a) | aÎT} vµ ¦ lµ mét ký hiÖu míi kh«ng thuéc N0, SG={(l0,X) | XÎNÈT} vµ PG ®­îc ®Þnh nghÜa nh­ sau: X x1 x2 ... xk [1] NÕu l thuéc P th× thuéc PG trong ®ã XiÎNÈT [2] NÕu l a thuéc P th× quy t¾c thuéc PG. Suy ra: nÕu (t;c) lµ mét c©y suy dÉn mê cña v¨n ph¹m nµy th× (p(t);c), mét phÐp chiÕu cña (t;c), lµ mét c©y mê ®­îc sinh ra bëi F-CFDS, S, trong ®ã p(t) ®­îc ®Þnh nghÜa trong ®iÒu kiÖn gi¶ sè h¹ng, nh­ sau: (1)- p[]=a (2)- p[]= VÝ dô 9.7 XÐt F-CFDS ®­îc cho bëi nh÷ng quy t¾c sau: A l l l l a §èi víi F-CFDS, ®Þnh nghÜa mét F-CFG bëi nh÷ng quy t¾c sau: §èi víi vÝ dô, suy dÉn mê cã mét c©y suy dÉn A A a a a vµ ®é thuéc cña nã lµ 0.8. PhÐp chiÕu cña c©y nµy ®­îc ®Þnh nghÜa trong sù chøng minh cña ®Þnh lý 9.6 lµ: (chøa trong F-CFDL ®­îc sinh ra bëi F-CFDS ®· cho) 10. ¤t¤mat C©y mê Trong phÇn 8, ta giíi thiÖu mét hÖ thèng sinh ng«n ng÷ mê mµ ®­îc dïng trong phÇn 9 ®Ó biÓu thÞ tËp mê cña c©y suy dÉn cña mét v¨n ph¹m phi ng÷ c¶nh mê. Trong phÇn nµy, ta ®Þnh nghÜa mét «tomat c©y mê nh­ mét bé ®o¸n nhËn cña mét ng«n ng÷ mê. §Þnh nghÜa 10.1 ¤tomat c©y mê (F-TA) lµ bé n¨m A=(S,N,T,a,F) trong ®ã: (1)-S lµ mét tËp h÷u h¹n nh÷ng ký hiÖu tr¹ng th¸i. (2)-N lµ tËp h÷u h¹n c¸c ký hiÖu nót kÕt thóc. (3)-T lµ tËp h÷u h¹n c¸c ký hiÖu l¸, trong ®ã NÇT=Æ X s1 s2 ... sk (4)-a: (NÈT) {¦ | S´S [0,1]}, trong ®ã S lµ mét tËp con h÷u h¹n cña S* chøa x©u rçng L. §èi víi XÎN, a(X)=aX lµ mét hµm tõ (S\{L})´S vµo [0,1]. Nã ®­îc gäi lµ mét hµm chuyÓn ®æi trùc tiÕp mê. §èi víi aÎT, a(a)=aa lµ mét hµm tõ {L}´S vµo [0,1]. aa ®Þnh nghÜa mét tËp con mê trªn S mµ ®­îc g¸n vµo nót cña a. aX(s1s2...sk,s)=c nghÜa lµ khi mét nót cña X cã k con víi c¸c tr¹ng th¸i s1,s2,...,sk, tr¹ng th¸i s ®­îc g¸n vµo nót cã bËc c. §iÒu nµy cã thÓ biÓu diÔn b»ng ®å thÞ nh­ sau c (5)-F lµ mét tËp con ph©n biÖt cña S gäi lµ tËp trong th¸i cuèi cïng. §èi víi mét c©y tÎD(N;T), ®Þnh nghÜa mét hµm chuyÓn ®æi mê at: {¦ | ¦: S*´S[0,1]} [0,1] nh­ sau: Cho t lµ X(t1t2...tk) lµ nh÷ng sè h¹ng cña gi¶ sè h¹ng. Khi ®ã ®èi víi ¦=(s1s2...sk,s), at(s1s2...sk,s) =(s1s2...sk,s) =ÚÎSÙ{ax(...,s),i=1,...,k (s1s2...sn,s1),...,(s1s2...sn,sk)} NÕu t=a ÎT, th× at=aa. Sö dông at, ta cã thÓ g¸n mét tËp con mê cña S vµo nót gèc cña c©y t. ¸nh x¹ at còng cã thÓ ®Þnh nghÜa mét tËp c¸c c©y mê, nghÜa lµ mét tËp mê trªn D(N;T), víi D(A)={(t;c) | c= ÚaÎ F{at(L,s)}} mµ ®­îc gäi lµ mét tËp mê cña nh÷ng c©y ®­îc nhËn d¹ng bëi mét «t«mat c©y mê A. VÝ dô 10.2 Cho S={sl,sx,sh}, N={A},T={a}, vµ F={sh}. §Þnh nghÜa a nh­ sau: a(a) sl sx sh L 0.8 0.7 1.0 a(A) sl sx sh sl 1.0 0 0 sx 0 1.0 0 sh 0 0 1.0 sl sl 0.2 0.8 0 sh sh 0 0 1.0 A A a a a a a §èi víi F-TA, A=(S,N,T,a,F), D(A) chøa c©y t d­íi ®©y a2(A) a1(A) a(a) a(a) a(a) a(a) a(a) víi ®é thuéc lµ 0.7. Qu¸ tr×nh tÝnh to¸n cña at(L,sh) cã thÓ ®­îc biÓu diÔn nh­ sau: Trong ®ã: a(a)=[0.8sl ,0.7sx ,1.0sh] nghÜa lµ: aa(sl)=0.8, aa(sx)=0.7, aa(sh)=1.0, a1(A)= [0sl ,0sx ,0.7sh] vµ a2(A)= [0sl ,0sx ,0.7sh] A a a a a a A sl a a a a 0.8 0.7 Nh­ vËy ta cã: at(L,sh)=0.7. at(L,sh) còng cã thÓ ®­îc x¸c ®Þnh bëi liÖt kª tÊt c¶ nh÷ng sù thu gän mê tõ t vµo sh ch¼ng h¹n nh­ d­íi ®©y A sl sx sl a a A sl sx a a a 0.8 0.7 1.0 1.0 A sl sx sl sx a A sl sx sl sx sh A sl sx sh 1.0 §Þnh lý 10.3 BÊt kú F-CFDL cã thÓ ®­îc nhËn ra bëi mét F-TA Chøng minh: Theo ®Þnh lý 8.3, ta cã thÓ gi¶ sö r»ng ®èi víi bÊt kú F-CFDL cho tr­íc D, tån t¹i mét F-CFDS chuÈn t¾c, S=(N0,N,T,P,l0) víi D(S)=D. Tõ F-CFDS, S, ta x©y dùng mét F-TA, A=(S,N,T,a,F) nh­ sau: §Æt S={sl | lÎN0), F={}. Khi ®ã a ®­îc x¸c ®Þnh nh­ sau: (1)-NÕu lX(l1l2...lk) thuéc P th× a(X)( ...,)=c (2)- NÕu l a thuéc P th× a(a)(L, )=c Râ rµng, tËp S trong ®Þnh nghÜa 10.1 lµ {... | l X(l1l2...lk) thuéc P } È{L}. Tõ sù x©y dùng trªn cña A dÉn ®Õn D(A)=D(s) (§PCM) §Þnh lý 10.4 BÊt kú tËp mê cña nh÷ng c©y cã thÓ ®o¸n nhËn bëi mét F-TA lµ mét F-CFDL. Chøng minh §¶o l¹i cña viÖc x©y dùng trong viÖc chøng minh cña ®Þnh lý 10.3 ®· chøng minh ®­îc ®Þnh lý nµy. HÖ qu¶ 10.5 Mét tËp mê cña c©y suy dÉn cña bÊt kú F-CFG lµ mét tËp mê cña nh÷ng c©y cã thÓ ®­¬c ®o¸n nhËn bëi mét F-TA. Chøng minh HÖ qu¶ ®­îc suy ra tõ kÕt qu¶ cña ®Þnh lý 9.2, 10.3 vµ 10.4 (§PCM) Suy ra, ®èi víi mét F-TA, nh÷ng kÕt qu¶ t­¬ng ®­¬ng víi bæ ®Ò 9.4, ®Þnh lý 9.5 vµ 9.6 còng tháa m·n. 11. Bé chuyÓn ®æi c©y mê Tr­íc ®©y, ta ®· giíi thiÖu mét F-CFDS nh­ mét bé sinh cña mét tËp mê cña c¸c c©y vµ mét F-TA nh­ mét bé ®o¸n nhËn. Nh÷ng hÖ thèng c©y thao t¸c mê nµy ®· ®­îc dïng ®Ó biÓu thÞ mét tËp mê cña c¸c c©y suy dÉn cña mét v¨n ph¹m phi ng÷ c¶nh mê. Trong phÇn nµy ta giíi thiÖu mét tËp bé chuyÓn ®æi c©y mê mµ cã thÓ ®Þnh nghÜa mét hµm mê tõ mét tËp cña nh÷ng c©y ®Õn mét tËp kh¸c. HÖ thèng c©y thao t¸c thø ba nµy cã thÓ ®­îc dïng ®Ó m« t¶ nghÜa mê cña ng«n ng÷ phi ng÷ c¶nh. Cho (N1,T1) vµ (N2,T2) lµ b¶ng ch÷ s¾p xÕp tõng phÇn h÷u h¹n. Mét tËp bé chuyÓn ®æi c©y mê tõ ®Õn lµ mét tËp con mê F cña ´ mµ ®é thuéc cña mét phÇn tö (t1,t2) cña ´ ®­îc biÓu thÞ bëi: mF( t1,t2) = cÎ[0,1] Ta còng biÓu thÞ nã bëi mét bé ba ( t1,t2,c) vµ khi ®ã tËp con mê F ®­îc xem lµ mét tËp cña c¸c bé ba nh­ vËy. Ph¹m vi cña mét bé chuyÓn ®æi c©y mê F lµ {t1 | ®èi víi mét sè t2 vµ mét sè c>0, (t1,t2,c) lµ thuéc F}={t1 | ®èi víi mét sè t2 ,mF( t1,t2)>0} mµ ®­îc biÓu thÞ bëi dom F. MiÒn (range) cña mét bé chuyÓn ®æi c©y mê F lµ {t2 | ®èi víi mét sè t1 vµ mét sè c>0, ( t1,t2,c) lµ thuéc F}={t2 | ®èi víi mét sè t1 ,mF(t1,t2)>0} mµ ®­îc biÓu thÞ bëi range F. Ta còng ®Þnh nghÜa hai ng«n ng÷ mê c¬ së, Ng«n ng÷ thø nhÊt ®­îc ®Þnh nghÜa lµ mét tËp con mê cña u¦dF cña mµ ®é thuéc cña mét phÇn tö t1 cña ®­îc cho bëi: mu¦dF (t1)= Ú {c | mF( t1,t2)=c, t2Î} Ng«n ng÷ thø hai lµ cña ph¹m vi mµ mét tËp con mê u¦rF cña . Hµm thuéc ®­îc cho bëi: mu¦rF (t2) = Ú {c | mF( t1,t2)=c, t1Î} §Þnh nghÜa 11.1 Mét bé chuyÓn ®æi c©y mê (F-STT) lµ mét bé b¶y: M=(N0,N1,T1,N2,T2,R,l0) sao cho nh÷ng ®iÒu kiÖn d­íi ®©y ®­îc tháa m·n: (1)-N0 lµ mét tËp h÷u h¹n nh÷ng ký hiÖu mµ phµn tö cña nã ®­îc gäi lµ ký hiÖu nót kh«ng kÕt thóc. (2)-N1,N2 lµ tËp h÷u h¹n nh÷ng ký hiÖu gäi lµ ký hiÖu nót. (3)-T1,T2 lµ tËp h÷u h¹n nh÷ng ký hiÖu gäi lµ ký hiÖu l¸. (4)-R: N0´´[0,1]; nÕu m(l,t1,t2)=c, th× ta viÕt l(t1,t2), trong ®ã t1,t2 chøa cïng nh÷ng ký hiÖu kh«ng kÕt thóc trong cïng thø tù. Ta gäi R lµ mét quy t¾c biÕn ®æi mê. (5)-l0 lµ ký hiÖu nót kh«ng kÕt thóc khëi ®éng. Mét d¹ng cña M lµ mét cÆp (t1,t2), trong ®ã t1 thuéc vµ t2 thuéc . NÕu (1) l(t1,t2) lµ mét quy t¾c chuyÓn ®æi mê, (2) (a1,a2) vµ (b1,b2) lµ nh÷ng d¹ng sao cho p(a1)=x1ly1, p(a2)=x2ly2, p(b1)=x1p(t1)y1, p(b1)=x1p(t1)y1, p(b2)=x2p(t2)y2, vµ (3) nÕu l lµ ký hiÖu nót thø k kh«ng kÕt thóc trong p(a1) th× l cña p(a2)=x2ly2 còng lµ nót thø k trong nã vµ ta viÕt: (a1,a2) (b1,b2). Ta còng ®Þnh nghÜa quan hÖ nh­ sau: (a1,a2) (a1,a2) vµ nÕu (a1,a2) (b1,b2) vµ (b1,b2) (g1g2), th× (a1,a2) (g1g2), trong ®ã: c={c1Ùc2} Bé chuyÓn ®æi c©y mê ®­îc ®Þnh nghÜa bëi M, ®­îc viÕt lµ F(M) {(t1,t2,c) | (l,l) (t1,t2)δ}, tøc lµ F(M) lµ mét tËp con mê cña ´ trong ®ã ®é thuéc cña mét phÇn tö (t1,t2) cña ´ ®­îc cho bëi mF(M) (t1,t2)=c hoÆc (l,l) (t1,t2) VÝ dô 11.2 XÐt tËp nh÷ng quy t¾c sau: + l l A l l + l ( , ) ~ l N ~ l l ( , ) · l l P l l · l ( , ) l (a , x ) Tõ nh÷ng quy t¾c nµy ta cã mét bé chuyÓn ®æi c©y mê mµ nh÷ng phÇn tö cña nã cã thÓ ®­îc x¸c ®Þnh nh­ sau: + l l A l l + (l,l) ( , ) + l ~ l A l + N ~ l ( , ) + l ~ · l l A l + N ~ P l l · ( , ) A a + N ~ P a a · + x ~ · x x ( , ) §Þnh lý 11.3 §èi víi bÊt kú F-STT, u¦dF(M) vµ u¦rF(M) lµ nh÷ng F-CFDL. Chøng minh Tõ mét F-STT cho tr­íc, M=(N0,N1,T1,N2,T2,l0), ta x©y dùng mét F-CFDS, S=(N0,N1,T1,P,l0), b»ng c¸ch ®Þnh nghÜa P nh­ sau: NÕu l(t1,t2) lµ thuéc R th× P chøa lt1. Chó ý, (l0,l0)(t1,t2) nÕu vµ chØ nÕu l0t1, suy ra ¦dF(M)=D(S). PhÇn cßn l¹i cña ®Þnh lý ®­îc chøng minh t­¬ng tù. (§PCM) §Þnh lý 11.4 §èi víi bÊt kú F-STT, domF(M) vµ range F(M) ®Òu lµ ng«n ng÷ phi ng÷ c¶nh. Chøng minh: LËp luËn t­¬ng tù nh­ ®· dïng trong chøng minh ®Þnh lý 11.3, ta chøng minh ®­îc ®Þnh lý nµy. 12. ý nghÜa mê cña ng«n ng÷ phi ng÷ c¶nh. ViÖc chØ râ mét tËp quy t¾c ng÷ nghÜa mµ cã thÓ phôc vô nh­ mét thuËt to¸n ®Ó tÝnh to¸n ý nghÜa cña mét sè h¹ng ®a hîp (composite) tõ tri thøc cña ý nghÜa cña nh÷ng thµnh phÇn cña nã lµ mét vÊn ®Ò trung t©m cña ng÷ nghÜa. Tuy nhiªn, ng«n ng÷ tù nhiªn lµ qu¸ phøc t¹p vµ nh÷ng quy t¾c kh«ng cã d¹ng râ rµng. V× vËy ta b¾t ®Çu víi mét vµi tr­êng hîp ®¬n gi¶n liªn quan gåm nh÷ng ®o¹n ng«n ng÷ tù nhiªn hoÆc nh©n t¹o. Zadeh ®· ®Ò nghÞ tiÕp cËn vÊn ®Ò liªn quan ng÷ nghÜa b»ng c¸ch ®­a ra mét thuyÕt ®Þnh l­îng cña ng÷ nghÜa: NghÜa cña mét sè h¹ng ®­îc ®Þnh nghÜa lµ mét tËp con mê cña mét tËp phæ dông cña discourse. Ph­¬ng ph¸p g¸n nghÜa vµo mét sè h¹ng ®a hîp ®­îc xem xÐt lµ mét ph­¬ng ph¸p h­íng có ph¸p. Mét tËp con mê ®­îc g¸n vµo mét sè h¹ng ®a hîp ®­îc xem lµ mét ¶nh cña mét sè hµm ®a hîp cña tËp con mõ trªn tËp phæ dông cña discours. Khi ®ã dÔ dµng ®Þnh nghÜa mét ph¹m vi ng÷ nghÜa nh­ lµ tËp phæ dông cña discours vµ hµm ®a t¹p. Mét cÊu tróc có ph¸p trong mét biÓu thøc biÓu diÔn mét hµm còng cã thÓ ®­îc ®o¸n nhËn ë ®©y. §ã lµ, ta xÐt khi ph¹m vi ng÷ nghÜa chØ lµ tËp cña tËp tÊt c¶ c¸c hµm cã thÓ biÓu diÔn bëi viÖc sö dông mét sè quy t¾c có ph¸p vµ ta xem xÐt r»ng viÖc g¸n ý nghÜa vµo mét sè h¹ng ®a t¹p nh­ g¸n mét c©y có ph¸p biÓu diÔn cña mét hµm t­¬ng ®­¬ng víi nã. Nh­ vËy ta dÉn ®Õn viÖc ¸p dông bé chuyÓn ®æi c©y mê vµo viÖc m« t¶ nghÜa mê cña ng«n ng÷ phi ng÷ c¶nh. §iÒu nµy ®­îc minh häa trong vÝ dô d­íi ®©y: S lA VÝ dô 12.1 Ta x©y dùng mét bé chuyÓn ®æi c©y mê cho vÝ dô cña ®­îc m« t¶ trong [261,260] nh­ sau: (1) lS ( , lA ) A lA (2) lA ( , lB ) B lC (3) lB ( , lC ) S lS lA or fv lS lA (4) lS ( , ) A lA lB and fL lS lA (5) lA ( , ) B not lC f~ lC (6) lB ( , ) O very lC fV lC (7) lO ( , ) Y very lY fV lY (8) lY ( , ) C lO (9) lC ( , lO ) C lY (10) lC ( , lY ) C lS (11) lC ( , lS ) O old (12) lC ( , lold ) Y young (13) lC ( , lyoung ) §Æt ¦Ú, ¦Ù vµ ¦~ lµ tËp mê c¸c phÐp to¸n hîp, giao vµ lÊy phÇn bï vµ ®Æt ¦v lµ hµm tËp trung ®­îc ®Þnh nghÜa nh­ sau: NÕu ¦v(A)=B th× hµm thuéc mB(x) cña B ®­îc cho bëi mB(x)=m2A(x). H¬n n÷a, gi¶ sö r»ng ¦old vµ ¦young lµ hµm h»ng mµ nh÷ng gi¸ trÞ cña nã lµ nh÷ng tËp con mê cña tËp hîp K={k | k=1,2,...,100} vµ nã ®­îc biÓu thÞ bëi hµm thuéc d­íi ®©y: (old,k) = vµ (young,k) = trong ®ã kÎK. B©y giê ta xÐt mét sè h¹ng ®a t¹p x=old or young and not very old. §èi víi sè h¹ng x, sù chuyÓn ®æi ®­îc cho bëi (A) vµ (B) fÙ fÚ f~ · fv fold fyoung fold S S A and A B · · C · · S · · or B · · C · · O · · A · · old A · B · C · Y young · · B not C O O old very (A) (lSlS) ( , ) mµ ®­îc ®o¸n nhËn b»ng c¸ch ¸p dông c¸c quy t¾c theo thø tù: (1), (5), (2), (3), (11), (4), (1), (2), (3), (9), (12), (2), (3), (10), (13), (6), (9), (7) vµ (12) fÙ fÚ f~ · fv fold fyoung fold S S A or A B · · C · · and C O · · A · · old B · C · Y · young · · B not B O O old very (B) (lSlS) ( , ) mµ ®­îc ®o¸n nhËn b»ng c¸ch ¸p dông nh÷ng quy t¾c (4), (1), (2), (3), (9), (12), (5), (2), (3), (10), (13), (6), (9), (7) vµ (12). V× vËy sè h¹ng ®a t¹p x=old or young and not very old cã hai nghÜa ¦Ù(¦Ú(¦old,¦young),¦~(¦v(¦(old))))=[m(old) Ú m(young)] Ù [1-m2(old)] víi ®é thuéc lµ 0.6 vµ ¦Ù(¦old,¦Ù(¦young,¦~(¦v(¦old))))=m(old) Ú [m(young) Ù [1-m2(old)]] víi ®é thuéc lµ 0.8 Tõ vÝ dô trªn ta thÊy r»ng mét bé chuyÓn ®æi c©y mê cã thÓ lµ mét m« h×nh hîp lý ®Ó m« t¶ nghÜa mê cña mét ng«n ng÷ phi ng÷ c¶nh ë cÊp ®é cÊu tróc có ph¸p trong nghÜa mµ nã cã thÓ mê hãa liªn kÕt mçi c©y suy dÉn cña ng«n ng÷ mê víi mét sù biÓu diÔn c©y cña qu¸ tr×nh tÝnh to¸n cña nghÜa mê cña nã. C. kÕt luËn TiÓu luËn “Ng«n ng÷ vµ v¨n ph¹m mê” ®· tr×nh bµy ®­îc mét sè néi dung nh­: Ng«n ng÷ mê, trong ®ã ®· ®Ò cËp ®Õn c¸c phÐp hîp, phÐp giao vµ phÐp nèi trªn hai ng«n ng÷ mê, më réng kh¸i niÖm d·y suy dÉn b»ng c¸ch thªm kh¸i niÖm ®é thuéc. C¸c lo¹i v¨n ph¹m, trong ®ã ®· më réng bèn lo¹i v¨n ph¹m th«ng th­êng. TiÓu luËn ®· ®i s©u t×m hiÓu v¨n ph¹m phi ng÷ c¶nh mê trong d¹ng chuÈn t¾c Chomsky vµ Greibach; v¨n ph¹m max-product phi ng÷ c¶nh; ng«n ng÷ phi ng÷ c¶nh mê. So víi ng«n ng÷ vµ v¨n ph¹m sinh ng«n ng÷ th«ng th­êng, ë ®©y tiÓu luËn ®· tr×nh bµy thªm mét sè phÇn nh­ c©y vµ gi¶ sè h¹ng, nh÷ng hÖ thèng sinh ng«n ng÷ mê; d¹ng chuÈn t¾c cña F-CFDS; tËp c¸c c©y suy dÉn cña v¨n ph¹m phi ng÷ c¶nh mê; ¤t«mat c©y mê; Bé chuyÓn ®æi c©y mê. Tµi liÖu tham kh¶o [1] Fuzzy Language and Grammar [2] Bµi gi¶ng-Logic Mê-NguyÔn Gia §Þnh [3] NhËp m«n trÝ tuÖ tÝnh to¸n-NguyÔn Hoµng Ph­¬ng, Lª Linh Phong, Nadipuram R.Prasad- NXB KHKT-2002 Môc lôc Néi dung Trang Më ®Çu ......................................................................................................................................................... 1 Néi dung ..................................................................................................................................................... 2 1-Ng«n ng÷ mê...................................................................................................................................... 2 2-C¸c lo¹i v¨n ph¹m........................................................................................................................... 3 3-V¨n ph¹m phi ng÷ c¶nh mê.................................................................................................... 4 4-V¨n ph¹m Max-Product phi ng÷ c¶nh........................................................................... 11 5-Ng«n ng÷ phi ng÷ c¶nh mê..................................................................................................... 14 6-C©y vµ gi¶ sè h¹ng......................................................................................................................... 18 7-Nh÷ng hÖ thèng sinh ng«n ng÷ mê.................................................................................. 20 8-D¹ng chuÈn t¾c cña F-CFDS.................................................................................................. 22 9-TËp c¸c c©y suy dÉn cña v¨n ph¹m phi ng÷ c¶nh mê....................................... 24 10-¤t«mat c©y mê............................................................................................................................... 28 11-Bé chuyÓn ®æi c©y mê.............................................................................................................. 31 12-ý nghÜa mê cña ng«n ng÷ phi ng÷ c¶nh.................................................................... 34 KÕt luËn......................................................................................................................................................... 38 Tµi liÖu tham kh¶o................................................................................................................................ 39