Tiểu luận Vấn đề văn phạm và ngôn ngữ

A. më ®Çu Trong những năm gần đây, chúng ta đã chứng kiến sự phát triển mạnh mẽ trong các lĩnh vực nghiên cứu toán học liên quan đến máy tính và tin học. Những phát triển đa dạng của toán học đã trở thành nền tảng cho sự phát triển của máy tính và tin học. Ngược lại, các tiến bộ trong tin học đã dẫn đến sự phát triển rất mạnh mẽ một số ngành toán học. Vì vậy, toán học đóng vai trò trung tâm trong các cơ sở của tin học. Trong đó lý thuyết ngôn ngữ hình thức và ôtômat đóng một vai trò rất quan trọng. Ngôn ngữ hình thức được sử dụng trong việc xây dựng các ngôn ngữ lập trình và lý thuyết về các chương trình dịch. Ngôn ngữ hình thức thì rất chính xác trong khi các ngôn ngữ tự nhiên lại đa dạng và không chính xác. Để giảm khoảng cách giữa chúng người ta đưa tính chất mờ vào cấu trúc ngôn ngữ hình thức. Tiểu luận nhằm nghiên cứu một số vấn đề về văn phạm và ngôn ngữ mờ, đặc biệt là văn phạm và ngôn ngữ phi ngữ cảnh mờ, văn phạm max-product phi ngữ cảnh. Nghiên cứu một số tính chất của 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ờ và bộ chuyển đổi cây mờ. Thực ra, vấn đề văn phạm và ngôn ngữ được sinh bởi văn phạm là một lính vực đã được nghiên cứu sâu và ứng dụng mạnh mẽ, đặc biệt là vấn đề văn phạm và ngôn ngữ mờ. Tiểu luận không nhằm trình bày thêm những vấn đề mới mà chỉ là tóm tắt những kiến thức mà bản thân đã thu nhận được thông qua thời gian học tập ngắn và tham khảo một số tài liệu. Để hoàn thành được đề tài này, ngoài sự cố gắng nỗ lực của bản thân, chúng tôi được sự giúp đỡ nhiệt tình của PGS.TS Nguyễn Gia Định. Dù rất tâm đắc với vấn đề nghiên cứu và đam mê với môn học, nhưng với thời gian hạn chế và khối lượng kiến thức của bản thân còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những sai sót. Chúng tôi xin trân trọng cảm ơn sự giúp đỡ quý báu của Quý Thầy và mong muốn đón nhận từ Quý Thầy và các bạn sự góp ý bổ sung để giúp chúng tôi có cách nhìn đúng hơn về vấn đề cần nghiên cứu đồng thời mong được sự lượng thứ cho những sơ suất trong tiểu luận này. Xin trân trọng cảm ơn! B. Néi dung 1. Ng«n ng÷ mê Cho T biÓu thÞ mét tËp c¸c tr¹ng th¸i kÕt thóc vµ N biÓu thÞ mét tËp tr¹ng th¸i kh«ng kÕt thóc sao cho TÇN=Æ. Mét ng«n ng÷ mê lµ mét tËp con mê cña T*. Cho l1 vµ l2 lµ hai ng«n ng÷ mê trªn T. Hîp cña l1 vµ l2 lµ mét ng«n ng÷ mê ®­îc biÓu thÞ bëi l1Èl2 vµ ®­îc ®Þnh nghÜa bëi: (l1Èl2)(x) = l1(x)Úl2(x) "xÎT* (1) Giao cña l1 vµ l2 lµ mét ng«n ng÷ mê ®­îc biÓu thÞ bëi l1Çl2 vµ ®­îc ®Þnh nghÜa bëi: (l1Çl2)(x) = l1(x)Ùl2(x) "xÎT* (2) Nèi cña l1 vµ l2 lµ mét ng«n ng÷ mê ®­îc biÓu thÞ bëi l1l2, ®­îc ®Þnh nghÜa bëi (l1l2)(x) = Ú{l1(u)Ùl2(v) | x=uv, u,vÎT*} "xÎT* (3) Cho l lµ mét ng«n ng÷ mê trong T. Khi ®ã tËp con mê l¥ cña T* ®­îc ®Þnh nghÜa: l¥(x)=Ú{ln(x) | n=0,1,...} "xÎT* ®­îc gäi lµ bao ®ãng Kleene cña l. Mét v¨n ph¹m mê cã thÓ ®­îc xem nh­ mét tËp c¸c quy t¾c ®Ó sinh ra nh÷ng phÇn tö cña mét tËp con mê. Mét v¨n ph¹m mê, hoÆc ®¬n gi¶n mét v¨n ph¹m, lµ mét bé bèn G=(N,T,P,S), trong ®ã T lµ mét tËp c¸c tr¹ng th¸i kÕt thóc, N lµ mét tËp c¸c tr¹ng th¸i kh«ng kÕt thóc (TÇN=Æ), P lµ mét tËp c¸c quy t¾c mê vµ SÎN. Mét phÇn tö cña P lµ biÓu thøc cã d¹ng: m(r w)=c c>0 (4) trong ®ã r vµ w lµ nh÷ng x©u trong (TÈN)*, c lµ ®é thuéc. Ta cã thÓ viÕt gän m (r w)=c thµnh r w. Nh­ trong tr­êng hîp cña v¨n ph¹m kh«ng mê, biÓu thøc rw biÓu diÔn mét quy t¾c viÕt l¹i. V× vËy nÕu rw vµ s vµ t lµ x©u tïy ý trong (TÈN)* th× ta cã srtswt. swt ®­îc gäi lµ suy dÉn trùc tiÕp tõ srt.(5) NÕu r1,...,rm lµ c¸c x©u trong (TÈN)* vµ r1r2,..., rm-1rm víi c2,...,cm >0 th× r1 ®­îc gäi lµ sinh ra rm trong v¨n ph¹m G, hoÆc rm cã thÓ ®­îc sinh tõ r1 trong v¨n ph¹m G. §iÒu nµy ®­îc biÓu diÔn bëi r1 Þ rm. r1r2,..., rm-1rm lµ mét d·y phÐp suy dÉn tõ r1 ®Õn rm (6) Mét v¨n ph¹m mê G sinh ra mét ng«n ng÷ mê L(G) theo nghÜa: Mét x©u c¸c ký hiÖu kÕt thóc x ®­îc gäi lµ thuéc L(G) nÕu vµ chØ nÕu x ®­îc sinh tõ S. §é thuéc cña x trong L(G) lµ: mG(x)=Ú(m(S,r1)Ùm(r1,r2)Ù...Ùm(rm,x))(7) Trong ®ã cËn trªn nhá nhÊt ®­îc lÊy trªn tÊt c¶ d·y phÐp suy dÉn tõ S ®Õn x. Nh­ vËy (7) ®Þnh nghÜa L(G) nh­ mét tËp con mê cña (TÈN)*. NÕu L(G1)=L(G2) trong nghÜa cña tÝnh b»ng nhau cña tËp con mê th× v¨n ph¹m G1 vµ G2 ®­îc gäi lµ t­¬ng ®­¬ng. Ph­¬ng tr×nh (7) cã thÓ ®­îc gi¶i thÝch nh­ sau: mG(x) lµ ®é thuéc cña x trong ng«n ng÷ ®­îc sinh bëi v¨n ph¹m G. mG(x) lµ ®é lín cña d·y suy dÉn m¹nh nhÊt tõ S ®Õn x. Cho m(S,r1)=c1, m(r1,r2)=c2,..., m(rm,x)=cm+1, th× (7) cã thÓ ®­îc viÕt: mG(x) = Ú(c1 Ù c2 Ù ... Ù cm+1) (8) VÝ dô 1.1 Cho T={0,1}, N={A,B,S} vµ P ®­îc cho bëi: m(S,AB)=0.5 m(A,0)=0.5 m(S,A)=0.8 m(A,1)=0.6 m(S,B)=0.8 m(B,A)=0.4 m(AB,AB)=0.4 m(B,0)=0.2 XÐt x©u kÕt thóc x=0. Nh÷ng d·y suy dÉn cã thÓ ®èi víi x©u nµy lµ S A0 S B0 S BA0 Do ®ã: mG(0) = (0.8 Ù 0.5) Ú (0.8 Ù 0.2) Ú (0.8 Ù 0.4 Ù 0.5) = 0.5 T­¬ng tù, nh÷ng d·y suy dÉn cã thÓ ®èi víi chuçi x=01 lµ S AB0B0A01 S ABAA0A01 S ABBA0A01 S ABBAAA0A01 Do ®ã: mG(01) = (0.4 Ú 0.4 Ú 0.2 Ú 0.4 = 0.4 Cho G lµ mét v¨n ph¹m mê. Khi ®ã liÖu tån t¹i hay kh«ng mét thuËt to¸n ®Ó tÝnh to¸n mG(x) b»ng c¸ch sö dông ®Þnh nghÜa ph­¬ng tr×nh (7). G ®­îc gäi lµ ®Ö quy nÕu tån t¹i thuËt to¸n nh­ vËy. 2. C¸c lo¹i v¨n ph¹m T­¬ng tù víi ®Þnh nghÜa th­êng dïng cña nh÷ng v¨n ph¹m kh«ng mê, ta ®Þnh nghÜa bèn lo¹i v¨n ph¹m mê chñ yÕu d­íi ®©y: V¨n ph¹m lo¹i 0: Lµ 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