Tóm tắt Luận án Các lớp mã liên quan đến mã luân phiên - Ngô Thị Hiền

, 2011), xêmina Bộ môn Toán tin, Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội và xêmina Cơ sở Toán học của Tin học, Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Chương 1 KIẾN THỨC Cơ SỞ Chương này trình bày ngắn gọn các khái niệm, kí hiệu và kết quả cơ bản sẽ được sử dụng trong luận án. Các khái niệm, kí hiệu cơ bản về tập họp, ngôn ngữ hình thức và lý thuyết ôtômát được xem như đã biết. Từ, ngôn ngữ và mã Cho A là một bảng chữ, nghĩa là một tập họp hữu hạn không rỗng các kí hiệu được gọi là các chữ. Một từ trên bảng chữ A là một dãy hữu hạn các phần tử thuộc A. Tập tất cả các từ hữu hạn trên A kí hiệu là A*. Từ rỗng kí hiệu là £ và A+ = A*\ {ổ}, số tất cả các xuất hiện của các chữ trong từ u được gọi là độ dài của u, kí hiệu là |ư|. Mỗi tập con của A* là một ngôn ngữ trên A. Một ngôn ngữ là chính quy nếu nó nhận được từ các ngôn ngữ hữu hạn phần tử và ngôn ngữ trống bằng cách áp dụng hữu hạn lần các phép giao, họp, hiệu, ghép nối và lặp. Nói một cách khác, lóp các ngôn ngữ chính quy là lóp ngôn ngữ nhỏ nhất trên A chứa tất cả các ngôn ngữ hữu hạn và đóng đối với các phép giao, họp, hiệu, ghép nối và lặp. Định nghĩa 1.1. Cho A là một bảng chữ hữu hạn. Một ngôn ngữ X trên A là mã nếu với mọi n,m > 1 và X1,... ,xn, yi,..., ym E X, thỏa mãn • • • xn = yỴy2 ...ymAAn = m và Xi = yi với i = 1,..., n. Mã X là tối đại trên A nếu X không chứa thực sự trong một mã nào khác trên A. Với mỗi lóp mã c trên A, một mã X E c là tối đại trong c (không nhất thiết là mã tối đại) nếu nó không chứa thực sự trong một mã nào khác của c. Từ u là một khúc (khúc đầu, khúc đuôi) của từ V nếu tồn tại các từ X, y sao cho V = xuy (v = uy, V = xu). Một khúc (khúc đầu, khúc đuôi) u là thực sự nếu xy Ạ £ (y Ạ £, X Ạ ổ). Từ u được gọi là từ con của từ V nếu tồn tại n > 1 sao cho u = Ui... un, V = XQUỵXi... unxn với U1,..., un, XQ,... ,xn E A*. Nếu XQ ... xn ^ £ thì u được gọi là từ con thực sự của V. Tập tất cả các khúc đầu thực sự của từ w được kí hiệu là Pref(w). Kí hiệu Pref(X) là tập tất cả các khúc đầu thực sự của các từ trong X c A*. Các kí hiệu Suff(w) và Suff(X) được định nghĩa một cách tưong tự. Từ đảo ngược của từ w = (21(22... an, với (21,0,2,... ,an là các chữ, là từ W = anan-i... (21. Tưong tự, với X c A*, ta kí hiệu X = {x I X E X}. Định nghĩa 1.2. Cho X là một tập con khác rỗng của A+. X được gọi là mã prefix (suffix') nếu không có từ nào trong X là khúc đầu (khúc đuôi) thực sự của một từ khác trong X, và X là mã bifix nếu nó vừa là mã prefix, vừa là mã suffix; X được gọi là mã infix (mã p-infix, mã s-infix) nếu không có từ nào trong X là khúc của một khúc (khúc đầu, khúc đuôi) thực sự của một từ khác trong X; X được gọi là hypercode nếu không có từ nào trong X là từ con thực sự của một từ khác trong nó. Cho X, Y c A*, tích của X và Y là tập XY = {xy I X E x,y E Y}. Tích được gọi là không nhập nhằng nếu với mỗi z E XY, tồn tại duy nhất một cặp (x,y) E X xY sao cho z = xy. Ta cũng sử dụng các kí hiệu X° = H, xn+1 = xnx (n>ừ). Cho w E A*, ta định nghĩa w ỵx = (u E A* I wu E X}, Xw 1 = (u E A* I uw E X}. Các kí hiệu này được mở rộng cho các tập: X~rY = |J X^Y, XY-1 = |J Xy-\ xtX yẼY Mã luân phiên Trừ khi định nghĩa lại, giả sử rằng 0 Ạ X, Y C A+ với X p Y = 0. Ta nói 2/12/2 ... un, n > 2, là một phân tích luân phiên trên (X, Y) nếu Uị E X thì Uị+1 E Y và Uị E Y thì Uị+1 E X với mọi i = 1, 2,... , n — 1. Hai phân tích luân phiên ^1^2 .. .un và U12>2.. .vm trên (X, Y) được gọi là cùng kiểu trái (cùng kiểu phải) nếu chúng cùng bắt đầu (kết thúc) bởi các từ thuộc cùng một tập X hoặc y, cụ thể là U1,V1 E X hoặc U1,V1 E Y (un,vm E X hoặc un,vm E Y). Hai phân tích luân phiên trên (X,Y) được gọi là cùng kiểu nếu chúng vừa cùng kiểu trái, vừa cùng kiểu phải. Định nghĩa 1.3. Cặp (X, Y) được gọi là mã luân phiên (mã luân phiên trái, mã luân phiên phải) trên A nếu không có từ nào trong A+ có hai phân tích luân phiên cùng kiểu (cùng kiểu trái, cùng kiểu phải) khác nhau trên (X, y), và (X,Y) được gọi là mã luân phiên chặt trên A nếu mọi từ trong A+ có không quá một cách phân tích luân phiên trên (X, y). Các lóp mã luân phiên, mã luân phiên trái, mã luân phiên phải và mã luân phiên chặt được kí hiệu tưong ứng là Ca, Cia, CrA và CSA- Mã định biên Cho B = {0,1} và Ab = {(l,a,r) I a E A u {ổ}, l,r E B}. Tập tất cả các từ trên Ab được kí hiệu là (Ab)* hay đon giản là A*B, Ab = {(l,w,r) I w E A\ l,r e B}u {ớ, e}, là một vị nhóm với phép tích ghép (hay phép tích) được định nghĩa như sau: J (G, Wiw2,r2), if n = z2, ZỵZ2 = < ' . lớ, ngược lại; Zỵỡ = ỠZ1 = 0, Zỵe = ezi = zp, với £1, Z‘2 E A*b, Z\ = (C, W1, n), z2 = (Z2, w2, r2) và e, 0 tưong ứng là phần tử đon vị và phần tử zero. Mỗi phần tử (Z, w, r) E A*B được gọi là từ định biên (B-từ) trên Ab hay trên A. Từ đảo ngược của B-từ z = (1,0102... 0,n,r), với ữi, ữ2,... ,an là các chữ và z, r E B, là B-từ Z = (r, anan-i.. .01,1). Khái niệm này được mở rộng cho tập con của tập các B-từ, z = {z I z E z}. Đe đon giản, ta sử dụng các kí hiệu sau: AB = AB \ {#, c £b}, £b = {(l, £,r) \l,r E B}-, -4J = {(0, w, r) \ w E A\ r E B} {0, e}, Aj = AJ \ {0, e, (0, £, r)}; -4Ĩ = {(1, W<r) \w E A*, r e B}u {e, eị, AỊ = A$\ {ỡ, e, (1, s, r)}; AJ = {(0,w,l) I WE A*}u{ớ,e}, At = At\{ớ,e,((U,l)}; At = {(1, w, 0) I w E A*} u {0, e}, AỊ = At \ {0, e, (1, E, 0)}. Mỗi tập con của A*B được gọi là một ngôn ngữ định biên (B-ngôn ngữ) trên A. Với mỗi từ z = (ỉ, w, r) E A*B, ta kí hiệu Pl(z) = l là biên trái của z và Pr(z) = r là biên phải của z. Ta cũng sử dụng kí hiệu \z\ là độ dài của z, Quy ước, |ớ| = +oo và |e| = 0. Ta định nghĩa phép chiếu Proj : A*B —> X* u {0}, với 0 A* là phần tử zero của vị nhóm A* u {0}, là hàm được xác định bởi Proj(e) = ổ, Proj(ớ) = 0 và Proj(7, w,r) = w. Hai B-từ s và t được gọi là tương đương chặt (tương đương trái, tương đương phải, tương đương), kí hiệu là s «5 t (s t, s t, s^i), nếu Proj(s) = Proj(t) (Proj(s) = Proj(t) và Pl(s) = Pr(t), Proj(s) = Proj(t) và Pr(s) = pR(t), s ttLt và s ttRt). Cho z là một tập con khác rỗng của AB. Ta nói rằng 2:1^2 ... zn với n > 1 và Z\, Z2 ..., zn E z, là một phân tích của B-từ (B-phân tích hay phân tích nếu không sợ nhầm lẫn) trên z. Hai phân tích s = S1S2 ... sn và t = Í1Í2 • • -tm trên z được gọi là tương đương chặt (tương đương trái, tương đương phải, tương đương) nếu s «5 t (s t, s t, s t), với Si, tj E z, i = 1,..., n và j = 1,..., m. Định nghĩa 1.4. Một B-ngôn ngữ z được gọi là mã định biên (B-mã) trên A nếu mọi B-từ trong AB có nhiều nhất một B-phân tích trên z, và z là một B-mã chặt (B-mã trái, B-mã phải) trên A nếu không có từ nào trong AB có hai phân tích tưong đưong chặt (tưong đưong trái, tưong đưong phải) khác nhau trên z. Các lóp B-mã, B-mã trái, B-mã phải và B-mã chặt được kí hiệu tưong ứng là CB, CiB, CrB and CsB. Chương 2 VỀ MÃ LUÂN PHIÊN Mã luân phiên, một sự mở rộng của mã truyền thống, được giới thiệu và xét bởi P.T. Huy và V.T. Nam năm 2004. Trong chưong này, chúng ta xét một số lóp mã con mới của mã luân phiên. Một số tính chất đặc trưng và một trật tự của mã luân phiên với các lóp mã con của nó sẽ được xem xét. Các thuật toán kiểm định các lóp mã mới cũng được đề xuất. Chưong này được viết trên cơ sở các kết quả trong [Hl]. Một số lớp con của mã luân phiên Mục này giới thiệu bốn lóp mã con mới của mã luân phiên. Định nghĩa 2.1. Cặp (X, y) được gọi là mã luân phiên hai phía trên A nếu nó vừa là mã luân phiên trái, vừa là mã luân phiên phải. Ví dụ 2.1. Cho X = {aab, baa} và Y = {ữữ} trên A = {ữ, b}. Khi đó (X, y) vừa là mã luân phiên trái, vừa là mã luân phiên phải, do đó nó là mã luân phiên hai phía. Tuy nhiên, (X, y) không là mã luân phiên chặt. Định lý 2.1. (X, y) là mã luân phiên hai phía khi và chỉ khi ba điều kiện sau được thỏa mẫn: (X, y) 6 Ca; (xy)+x-1 n (xy)+ = 0; y-1(xy)+ n (xy)+ = 0. Ba điều kiện (i), (ii) và (Ui) là độc lập. Hai phân tích luân phiên U1U2 ... un và V1V2 ... vm trên (X, y) là khác kiểu nếu chúng cùng bắt đầu và cùng kết thúc với các từ thuộc các tập khác nhau, cụ thể Ui E X, V1 E Y hoặc Ui E Y,VI E X và un E X, vm E Y hoặc un E Y, vm E X. Cặp (X, y) được gọi là có dạng chuẩn nếu không có từ nào trong A+ có hai phân tích luân phiên khác kiểu khác nhau trên (X, y). Định nghĩa 2.2. Cặp (X, y) được gọi là mã luân phiên chuẩn (mã luân phiên chuẩn tráp mã luân phiên chuẩn phải) trên A nếu nó là mã luân phiên (mã luân phiên trái, mã luân phiên phải) có dạng chuẩn. Các lóp mã luân phiên hai phía, mã luân phiên chuẩn trái (phải) và mã luân phiên chuẩn được kí hiệu tưong ứng là CtA, CinA, CrnA và CnA- Ví dụ 2.2. Cho X = {bna I n > 1}, y = {a,aba} trên A = {ữ,ò}. Khi đó (X, y) là mã luân phiên chuẩn nhưng không là mã luân phiên chuẩn trái. Ví dụ 2.3. Trên A = {ữ,ỏ}, cho X = {a,ba}, Y = {b,ab}. Khi đó (X, y) là mã luân phiên chuẩn trái nhưng không là mã luân phiên chuẩn phải. Nhận xét 2.1. Cho hai phân tích luân phiên khác nhau trên (X, y), chỉ có những trường họp sau xảy ra: [XX,XX](1) [yy,yy] (2) [xy,xy](3) [yx,yx](4) [xx,xy](5) [yy,yx] (6) [xx,yx](7) [xy,yy](8) [xy,yx] (9) [xx,yy](io) ở đây [xy, YX] kí hiệu là phân tích luân phiên thứ nhất bắt đầu với một từ thuộc X, kết thúc với một từ thuộc y, còn phân tích luân phiên thứ hai bắt đầu với một từ thuộc y, kết thúc với một từ thuộc X. Các khẳng định trong Bảng 2.1 là đúng, với + và — tưong ứng kí hiệu các lóp mã chấp nhận và không chấp nhận các phân tích có dạng (1),..., (10). Bảng 2.1: Quan hệ giữa phân tích luân phiên và mã luân phiên Lóp mã (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Ca — — — — + + + + + + ClA — — — — — — + + + + CrA — — — — + + — — + + CtA + + CnA — — — — + + + + — — ClnA — — — — — — + + — — CrnA — — — — + + — — — — CSA — Một trật tự của các lớp mã luân phiên Các kết quả dưới đây chỉ ra một số đặc trưng của các lóp mã luân phiên chuẩn (chuẩn trái, chuẩn phải) và mối quan hệ giữa mã luân phiên và các lóp con của chúng. Định lý 2.2. Các khẳng định sau là đúng (X, y) là mã luân phiên chuẩn khi và chỉ khi nó là mã luân phiên và (XYfi n (YXffi = ty; (X, Y) là mã luân phiên chuẩn trái khi và chỉ khỉ nó là mã luân phiên trái và (XYffi n (YXffi = $; (hi) (X, y) là mã luân phiên chuẩn phải khi và chỉ khi nó là mã luân phiên phải và (xy)+ n (yx)+ = 0. Định lý 2.3. Cho (X, y) là mã luân phiên trên A. Khi đó, Nếu XY là mã bifix (prefix, suffix) và Pref(X) p Pref(y) = 0 hoặc Suff(X) Cl Suff(y) = 0, thì (X, y) là mã luân phiên chặt (mã luân phiên chuẩn trái, mã luân phiên chuẩn phải); Nếu XY là mã bifix (prefix, suffix), thì (X. y) là mã luân phiên hai phía (mã luân phiên trái, mã luân phiên phải); Nếu Pref(X) n Pref(y) = 0 hoặc Suff (X) n Suff(y) = 0, thì (X, y) là mã luân phiên chuẩn. Chú ý rằng, Định lý 2.3 cung cấp một công cụ hữu hiệu cho phép kiểm tra một mã luân phiên (tổng quát hon, một cặp ngôn ngữ) cho trước có thuộc lóp con của mã luân phiên hay không. Ví dụ 2.4. Cho X = {a2b,ba2}, Y = {a2}, X1 = {bna I n > 1}, M = {a,aba}, X2 = {a,ba}, Y2 = {b, ab} và X3 = {aa, ab},Ys = {&&}. Theo Định lý 2.3, ta có (X,y) e CtA \ C,A, (Xi, Y1) e C„A, (V, y2) G Cị„a và (V, V) e CaA. Định lý 2.4. Trên bảng chữ có ít nhất hai chữ, cấc điều sau là đúng C.s-X ClnA, CSA cz CrnA, CSA c CCr c«x n CịA ClnA p CrA CrnA p CiA CịA n CnA n CrA ClnA c CịA CịA c CrnA CrnA c CịnA CịnA c CrnA c CịA, CinA p CiA, CịnA p CnA, CrnA p CrA, CrnA p CnA, CịA p ClAĩ CịA p CrAì CịnA Cịa c CnAì CrnA CrA n CnAì CịA CiA n CrA) CiA c Ca, CnA c Ca, CrA c Ca- Một trật tự của lóp mã luân phiên và các lóp con của chúng được minh họa trong Hình 2.2, với biểu thị cho quan hệ bao hàm chặt. Hình 2.2: Một trật tự của mã luân phiên và các lớp con của chúng Kiểm định mã luân phiên Định lý 2.5. Giả sử X, Y là cấc ngôn ngữ chính quy và m, n tương ứng là sô' trạng thái của các otomat hữu hạn đơn định đoán nhận X và Y. Khi đó, tồn tại thuật toán kiểm định cặp (X, y) là mã luân phiên hai phía với độ phức tạp cỡ 0{3m+n); mã luân phiên chuẩn (mã luân phiên chuẩn trái, mã luân phiên chuẩn phải) với độ phức tạp cỡ ỡ(16m+n). Các thuật toán sau đây cho phép kiểm tra một cặp ngôn ngữ chính quy cho trước (X, y) có là mã luân phiên hai phía (mã luân phiên chuẩn, mã luân phiên chuẩn trái, mã luân phiên chuẩn phải) hay không. Thuật toán 1: Kiểm định mã luân phiên hai phía If (X, y) ị Ca then goto Step 5. If {XY)+X~r n (xy)+ Ạ 0 then goto Step 5. If y_1(xy)+ n (AY)+ Ạ 0 then goto Step 5. (X, y) is a two-sided alt-code; STOP. (X, y) is not a two-sided alt-code; STOP. Thuật toán 2: Kiểm định mã luân phiên chuẩn If (X, y) ị Ca then goto Step 4. If (XP)+ n (yx)+ ị0 then goto Step 4. {X, y) is a normal alt-code; STOP. (X, y) is not a normal alt-code; STOP. Thuật toán 3: Kiểm định mã luân phiên chuẩn trái If (X, y) ị Ca then goto Step 5. If ÍXYỷX-1 n (xy)+ Ạ 0 then goto Step 5. If (xy)+ n (YXỴ- 4 0 then goto Step 5. (X, y) is a left normal alt-code; STOP. (X, y) is not a left normal alt-code; STOP. Thuật toán 4: Kiểm định mã luân phiên chuẩn phải If (X,Y) Ệ Ca then goto Step 5. If y_1(xy)+ n (%y)+ Ạ 0 then goto Step 5. If (xy)+ n (yx)+ Ạ 0 then goto Step 5. (X, Y) is a right normal alt-code; STOP. (X, y) is not a right normal alt-code; STOP. Ví dụ 2.5. Cho X = ab+ và Y = ba+ trên A = {a, b}. Thực hiện từng bước của Thuật toán 1, ta có (X, y) là mã luân phiên hai phía. Chương 3 MÃ CẨM SINH BỞI MÃ LUÂN PHIÊN Chương này giới thiệu và xét lóp mã cảm sinh và các lóp con của chúng. Một số tính chất đặc trưng và các thuật toán kiểm định một mã hữu hạn (chính quy) có là mã cảm sinh (tương ứng, mã cảm sinh mạnh) hay không được đề xuất. Bài toán nhúng cho một số lóp con đặc biệt của mã cảm sinh cũng được xem xét. Nội dung của chương này bao gồm các kết quả trong [HV,H3]. 3.1 Mã cảm sinh Mục này giới thiệu và xem xét một lóp mã mới hên quan đến mã luân phiên, được gọi là mã cảm sinh. Một số đặc trưng của các lóp mã cảm sinh prefix (suffix, bifix) cũng được đề xuất. Định nghĩa 3.1. Một tập con z của A+ được gọi là mã cảm sinh bởi mã luân phiên (hay mã cảm sinh) nếu có một mã luân phiên (X, y) trên A sao cho z = XY. Một ngôn ngữ z là mã cảm sinh prefix (suffix, bifix) nếu nó là mã cảm sinh và là mã prefix (suffix, bifix). Ví dụ 3.1. Xét X = {ab, abba] và Y = {b}. Khi đó z = XY = {abb, abbab} là mã suffix và là mã cảm sinh. Do đó, z là mã cảm sinh suffix. Phần còn lại của chương dành để trả lòi câu hỏi một mã cho trước khi nào là mã cảm sinh. Mệnh đề 3.1. Cho mã z trên A sao cho z = XY với 0 7^ X, y C A+. Nếu X là mã prefix hoặc Y là mã suffix thì z là mã cảm sinh. Hệ quả 3.1. Cho z Q A+ là mã sao cho tất cả cấc từ thuộc z có độ dài lớn hơn hoặc bằng 2. Khi đó, nếu tất cả cấc từ của z bắt đầu (kết thúc) với cùng một chữ thuộc bảng chữ A thì z là mã cảm sinh. Hệ quả 3.2. Cho z là mã trên A sao cho z = XY với $ Ạ X,Y C A+. Nếu |X| = 2 hoặc |yI = 2 thì z là mã cảm sinh. Mệnh đề 3.2. Nếu z C A+ là mã cảm sinh thì zn là mã cảm sinh với mọi sô' nguyên n > 1. Kết quả sau đây chỉ ra một số đặc trưng của các lóp mã cảm sinh prefix (suffix, bifix). Định lý 3.1. Cho X và Y là cấc tập con khác rỗng của A+. XY vàYX là mã cảm sinh prefix (mã cảm sinh prefix tối đại) khi và chỉ khi X và Y là mã prefix (mã prefix tối đại); XY vàYX là mã cảm sinh suffix (mã cảm sinh suffix tối đại) khi và chỉ khi X và Y là mã suffix (mã suffix tối đại); XY and YX là mã cảm sinh bifix (mã cảm sinh bifix tối dại mỏng) khi và chỉ khi X và Y là mã bifix (mã bifix tối dại mỏng). Chú ý rằng, Định lý 3.1 cung cấp một công cụ hữu hiệu để xây dựng các mã cảm sinh (mã cảm sinh tối đại). Ví dụ 3.3. Cho các mã prefix X = {anba I n > 1}, Y = {bma I m > 1} trên A = {ữ,ò}. Theo Định lý 3.1(i), XY = {anbabma I n,m> 1}, YX = {bmanba I n > 2,m > 1} là các mã cảm sinh prefix. Mã cảm sinh hữu hạn Mục này xét về các mã cảm sinh hữu hạn. Một số tính chất được đề xuất cho phép trả lòi câu hỏi khi nào một mã hữu hạn là mã cảm sinh. Thuật toán kiểm định một mã hữu hạn có là mã cảm sinh hay không cũng được thiết lập. Cho A = {ữi, Ơ2,..., ữk}, k > 2, và z C A+. Với mỗi 2, ta kí hiệu Zai là tập tất cả các từ trong z bắt đầu bởi chữ Ui, cụ thể Zữi = {w E z I w = UịU, u E Ẩ*} với i = 1, 2,... , k. Hiển nhiên, các tập khác rỗng Zai tạo thành một phân hoạch của z. Kết quả dưới đây sẽ được sử dụng trong Thuật toán FIC. Mệnh đề 3.5. Cho A = {ữi, (12,, ữ/c}, k > 2, và z c A+, z = u^=1 Zữi, Zai Ạ $,i = 1, 2,..., k. Nếu z = XY với 0 Ạ X,Y C A+, thì Vw E Zav Au E Pref(w) sao cho Y Qu 1Zữi,i = 1,2,..., k. Hơn nữa, Y = u~ỴZữi nếu X là mã prefix. Một mã z trên A, m > 2, được gọi là có dạng chuẩn nếu tất cả các từ của z có độ dài lớn hon hoặc bằng 2 và không xảy ra trường họp tất cả các từ của z bắt đầu (kết thúc) bởi cùng một chữ trong A. Định lý 3.2. Cho A = {ữi, ữ2,..., ữk}, k >2, và z C A+ là mã hữu hạn có dạng chuẩn, z = ỊJ^=1 Zữi. Nếu gcd(|Zữl|, |Zữ2|,..., |Zữfe|) = 1 thì z không là mã cảm sinh. Hệ quả 3.4. Nếu z là mã hữu hạn có dạng chuẩn trên A và \z\ là sô' nguyên tô' thì z không là mã cảm sinh. Thuật toán sau đây cho phép kiểm định một mã hữu hạn cho trước có là mã cảm sinh hay không. Khi z là một tập hữu hạn của A+, minZ kí hiệu là độ dài của từ ngắn nhất trong z. Thuật toán FIC (Kiểm định mã cảm sinh hữu hạn) Input: z là mã hữu hạn có dạng chuẩn và z = u^=1 Zai. Output: z là mã cảm sinh hay không. If gcd(|Zữl|, |Zữ21,..., |Zữfe|) = 1 then goto Step 4. Choose w E Zat, 1 <t < k, such that |w| = minZ; Set Pw = Pref(w) \ {ổ} and D = {d > 2 I d is a common divisor of |Zữl|, |Zữ21,..., |Zữfe|}. While pw 4 0 do { Take u E Pw\ Set s = u~rZat and Q = {U E 2s I \u\ E D}- While Q 4 0 do { Take Y e Ọ; Set p = nyGy Zy~x and R = {V e 2P I |V| = \Z\/\Y\}- While R Ạ 0 do { Take X e R; If z = XY then goto Step 5 else R:= R\X: } p,i: ■- p,i: \ W; } z is not an alt-induced code; STOP. z is an alt-induced code; STOP. Ví dụ 3.5. Cho z = {a3, a2b, ba2, b9} trên A = {a,5}. Rõ ràng, z là mã có dạng chuẩn, z = Zac Zb với Za = {a3,a2b} và Zb = {ba2,b9}. Thực hiện Thuật toán FIC theo từng bước ta có z không là mã cảm sinh. Định lý 3.3. Cho z là mã hữu hạn có dạng chuẩn trên A = {ữi,..., ak}, k > 2. Khi đó, có thể kiểm định được z là mã cảm sinh hay không với độ phức tạp cở O(m2nk+n), với m = min z và n = max{ I Zai I,..., I Zak I}. Mã cảm sinh mạnh Mục này xét một lóp mã con đặc biệt của mã cảm sinh gọi là mã cảm sinh mạnh. Một số đặc trưng và một thuật toán kiểm định một mã chính quy cho trước có là mã cảm sinh mạnh hay không được đề xuất. Định nghĩa 3.2. Cho X và Y là các tập con khác rỗng của A+. Mã luân phiên (V. y) được gọi là mã luân phiên mạnh nếu nó thỏa mãn các điều kiện: X-^XY) c Y (1), (yy)y-1 c X (2). Mã cảm sinh z trên A được gọi là mã cảm sinh mạnh nếu tồn tại mã luân phiên mạnh (X, y) sinh ra nó, z = XY. Ví dụ 3.7. Cho X = {anb I n > 1}, y = {b,bab} trên A = {ữ,5}. Khi đó XY là mã cảm sinh nhưng không là mã cảm sinh mạnh. Các kết quả sau chỉ ra đặc trưng của mã cảm sinh mạnh cũng như các lóp con đặc biệt của nó. Định lý 3.4. Cho X và Y là cấc tập con khác rỗng của A+. Cấc điều kiện sau là tương đương: XY là mã cảm sinh mạnh; (X, y) là mã luân phiên mạnh; X là mã prefix, Y là mã suffix và XY là mã. Ví dụ 3.8. Cho X = {anb I n > 1} và Y = {b,bba} trên A = {ữ,ò}. Khi đó, theo Định lý 3.4, (X, y) là mã luân phiên mạnh và XY là mã cảm sinh mạnh. Định lý 3.5. Cho X và Y là cấc tập con khác rỗng của A+. XY là mã cảm sinh mạnh prefix (mã cảm sinh mạnh prefix tối đại) khi và chỉ khi X là mã prefix (mã prefix tối đại) và Y là mã bifix (Y vừa là mã bifix vừa là mã prefix tối đại); XY là mã cảm sinh mạnh suffix (mã cảm sinh mạnh suffix tối đại) khi và chỉ khi X là mã bifix (X vừa là mã bifix vừa là mã suffix tối đại) và Y là mã suffix (mã suffix tối đại); (hi) XY là mã cảm sinh mạnh bifix (mã cảm sinh mạnh bifix tối đại mỏng) khi và chỉ khi X và Y mã bifix (mã bifix tối đại mỏng). Mệnh đề 3.8. Những điều sau là đúng Tích của hai mã cảm sinh (mã cảm sinh mạnh) prefix (suffix, bifix, p-infix, s-infix, infix, p-subinfix, s-subinfix, subinfix, hyper) là mã cảm sinh (mã cảm sinh mạnh) prefix (suffix, bifix, p-infix, s-infix, infix, p- subinfix, s-subinfix, subinfix, hyper). Tích của hai mã cảm sinh (mã cảm sinh mạnh) prefix (suffix, bifix, p-infix, s-infix, infix, p-subinfix, s-subinfix, subinfix, hyper) tối đại là mã cảm sinh (mã cảm sinh mạnh) prefix (suffix, bifix, p-infix, s-infix, infix, p-subinfix, s-subinfix, subinfix, hyper) tối đại. Trong ngữ cảnh lóp ngôn ngữ chính quy, mã cảm sinh mạnh có kết quả thú vị sau. Định lý 3.6. Nếu z Q A+ là mã cảm sinh mạnh chính quy thì chỉ có một số hữu hạn mã luân phiên mạnh sinh ra z. Thuật toán sau đây cho phép kiểm tra một mã chính quy cho trước có là mã cảm sinh mạnh hay không. Thuật toán RSIC (Kiểm định mã cảm sinh mạnh) Input: Mã chính quy z trên A. Output: z là mã cảm sinh mạnh hay không. Choose w E z, such that \w\ = minZ; Set p = Pref(w) \ {ổ}. While p Ạ 0 do { Take u E P\ Set Y = ư_1Z; If YY-1 = £ then { Take y eY', Set X = Zy~Ỵ\ If (X~ỴX = ổ) and (Z = XY) then goto Step 4; } P:=P\ } z is not a strong alt-induced code; STOP. z is a strong alt-induced code; STOP. Ví dụ 3.13. Cho z = {bna2bma I n,m > 1} trên A = {ữ,ò}. Thực hiện từng bước của Thuật toán RSIC ta có z = {bna}{abma}, n,m > 1} là mã cảm sinh mạnh. Định lý 3.7. Giả sử z là mã chính quy trên A với m là sô' trạng thái của otomat hữu hạn đơn định đoán nhận z. Khi đó, có thể kiểm định được z có là mã cảm sinh mạnh hay không với độ phức tạp cỡ O(m3fi Bài toán nhúng Mục tiêu của mục này là đề xuất các thuật toán để tìm một mã cảm sinh mạnh prefix (suffix, bifix) tối đại chính quy (hữu hạn) chứa một mã cảm sinh mạnh prefix (suffix, bifix) chính quy (hữu hạn) cho trước. Định lý 3.8. Mỗi mã cảm sinh mạnh prefix (suffix, bifix) chính quy được nhúng trong một mã cảm sinh mạnh prefix (suffix, bifix) tối đại chính quy. Ví dụ 3.16. Trên A = {ữ, b, c}, cho X = a + c, Y = c(a + bỴc và z = XY. Khi đó, X và Y là các mã biíỉx chính quy. Theo Định lý 3.5(iii), z là mã cảm sinh mạnh biíỉx chính quy. Dễ thấy rang Mx = A là mã biíỉx tối đại hữu hạn và My = a + b + c(a + bỴc là mã biíỉx tối đại chính quy. Do đó MỵMỵ là mã cảm sinh mạnh biíỉx tối đại chính quy chứa z. Một mã bifix hữu hạn X được gọi là nice nếu hoặc X là chưa đủ (insufficient) hoặc X là đủ (sufficient) và tất cả các từ vô hạn đầy đủ có cùng số n trong các biểu diễn (interpretation). Định lý 3.9. Cho z = XY là mã cảm sinh mạnh prefix (suffix, bifix) hữu hạn. Khi đó, z được nhúng trong một mã cảm sinh mạnh prefix (suffix, bifix) tối đại chính quy. Dặc biệt, z được nhúng trong một mã cảm sinh mạnh prefix (suffix, bifix) tối đại hữu hạn, nếu Y là mã nice bifix (X là mã nice bifix, X và Y là mã nice bifix). Ví dụ 3.19. Trên A = {ữ, &}, cho X = a + bbb, Y = b + aa và z = XY. Ta có X và Y là các mã bifix hữu hạn. Theo Định lý 3.5(iii), z là mã cảm sinh mạnh bifix hữu hạn. Không khó để kiểm chứng rằng Mx = ữ + ba*ba*b và My = b + ab*a là các mã bifix tối đại chính quy. Do đó, MỵMỵ là mã cảm sinh mạnh bifix tối đại chính quy chứa z. Chương 4 VỀ MÃ ĐỊNH BIÊN • Mã định biên (B-mã), một sự mở rộng của mã truyền thống, được giới thiệu và xét bởi H.N. Vinh và cộng sự năm 2009. Trong chưong này, chúng ta xét một số lóp mã con mới của B-mã. Các đặc trưng, quan hệ của B-mã, mã luân phiên với các lóp mã con của chúng sẽ được xem xét. Bài toán nhúng đối với các lóp B-mã prefix (B-mã suffix) được xét cho cả trường họp chính quy và hữu hạn. Chưong này được viết trên cơ sở các kết quả trong [H2,H4]. 4.1 B-mã và quan hệ với mã luân phiên Mục này giới thiệu và xét bốn lóp mã con mới của B-mã. Một số đặc trưng và quan hệ của B-mã, mã luân phiên với các lóp mã con của chúng được thiết lập. Định nghĩa 4.1. Một B-ngôn ngữ z được gọi là B-mã hai phía trên A nếu nó vừa là B-mã trái, vừa là B-mã phải. Ví dụ 4.1. Xét tập z = {(0, aab, 1), (0, baa, 1), (1, aa, 0)} trên A = {ữ,ò}. Khi đó z vừa là B-mã trái, vừa là B-mã phải, và do đó z là B-mã hai phía. Tuy nhiên, z không là B-mã chặt. Định lý 4.1. Giả sử X, Y là cấc tập con khác rỗng của A+ và z = x, ở đó X c A+. Khi đó, z là B-mã hai phía khi và chỉ khi (X, y) là mã luân phiên hai phía. Giả sử z là một tập con khác rỗng của Ag. Hai B-từ s và t được gọi là tương đương đối, kí hiệu là s G nếu Proj(s) = Proj(t), Pr(s) Ạ Pl(ì) và Pr(s) 7^ Pr(ì)- Hai phân tích s = S1Ổ2 ... sn và t = tiG • • -tm trên z được gọi là tương đương đối nếu s G ở đó Sị,tj G z,i = 1,... ,n, j = 1,.. .m. Một B-ngôn ngữ z được gọi là có dạng chuẩn nếu không có từ nào trong Ap có hai phân tích tưong đối khác nhau trên z. Định nghĩa 4.2. Một B-ngôn ngữ z được gọi là B-mã chuẩn (B-mã chuẩn trái, B-mã chuẩn phải) trên A nếu nó là B-mã (B-mã trái, B-mã phải) có dạng chuẩn. Lóp B-mã hai phía, B-mã chuẩn, B-mã chuẩn trái và B-mã chuẩn phải được kí hiệu tưong ứng là CtBi CnBi CinB và CrnB- Ví dụ 4.2. Xét z = {(1, a, 0), (1, aba, 0), (0, bna, 1) I ĨI > 1} trên A = {ữ, b}. Khi đó z là B-mã