Thuật toán xác định tính chất mã của ngôn ngữ chính quy

một phương pháp tính tốn tổ hợp kiểm tra tính chất mã của một tập các từ cho trước.
Cho đến nay, phương pháp này vẫn được sử dụng rộng rãi như một tiêu chuẩn kiểm tra tính
chất mã của ngơn ngữ. Một số cơng trình nghiên cứu theo hướng mở rộng phương pháp đĩ
cho các lớp mã mới như mã zigzag (M. Anselmo [1], và D.L. Van, B. Lesae¨c, I. Litovsky [2]),
Pcodes (F. Blanchet-Sadri, M. Margaret [3]), T-V codes (F.L. T¸iplea và các tác giả khác
[4]), mã với từ định biên (H.N. Vinh, P.T. Huy, Đ.L. Vân [5]) và mã nhị phân (D. Macro
[6]), hoặc để tính tốn một số độ đo của mã như độ khơng nhập nhằng (P.T. Huy, N.Đ.
Hân, P.M. Chuẩn [7]) và độ trễ giải mã (H.N. Vinh, N.Đ. Hân, P.T. Huy [8]). Một số tác giả
đề xuất thuật tốn kiểm tra mã kiểu Sardinas-Patterson sử dụng kỹ thuật otomat như M.
Robert [9], W. Andreas, H. Tom [10] và J. Falucskai [11]. Khi ngơn ngữ được cho bởi một
otomat hữu hạn, thuật tốn kiểm tra mã trong [9] cĩ độ phức tạp cỡ O(n2), với n là tổng số
trạng thái và số phép chuyển của otomat hay cỡ O(l2.k4), với l là số chữ của bảng chữ cái
và k là số trạng thái của otomat đĩ.
Trong bài này, chúng tơi cải biên phương pháp tổ hợp của Sardinas và Patterson, đề xuất
một thuật tốn kiểm tra mã. Khi cho ngơn ngữ chính quy X được đốn nhận bởi một đồng
cấu đại số α : A∗ →M , với M là một vị nhĩm hữu hạn, ta nhận được một thuật tốn kiểm
tra X cĩ là mã khơng. Nhờ sử dụng phương pháp đại số, cho phép đánh giá tính hiệu quả
rõ rệt của thuật tốn này, với độ phức tạp cỡ O(k), với k là chỉ số tương đẳng cú pháp của
X , hơn hẳn độ phức tạp của thuật tốn Sardinas-Patterson, được biết cĩ cỡ O(22.k).
2 NGUYỄN ĐÌNH HÂN, HỒ NGỌC VINH, PHAN TRUNG HUY, ĐỖ LONG VÂN
Trước hết, chúng tơi nhắc lại một số ký hiệu và khái niệm được sử dụng trong bài báo,
chi tiết xem trong [12, 13]. Cho A là bảng hữu hạn các chữ cái. A∗ là vị nhĩm tự do của tất
cả các từ hữu hạn sinh bởi A. Từ rỗng được ký hiệu là ε và A+ = A∗−{ε}. Mỗi tập con của
A∗ được gọi là một ngơn ngữ trên A. Một tập X ⊆ A+ được gọi là mã trên A nếu mọi từ w
thuộc A+ cĩ nhiều nhất một cách phân tích thành tích của các từ trongX . Giả sử X, Y ⊆ A∗,
ta gọi thương trái (thương phải) của X với Y là ngơn ngữ Y −1X (tương ứng XY −1) được
xác định bởi Y −1X = {w ∈ A∗ | yw ∈ X, y ∈ Y } và XY −1 = {w ∈ A∗ | wy ∈ X, y ∈ Y }. Ký
hiệu u−1X , Xu−1 được sử dụng khi tập Y = {u} chỉ cĩ một phần tử.
Cho X ⊆ A∗, ta nĩi rằng X thỏa bởi đồng cấu vị nhĩm α : A∗ →M nếu tồn tại B ⊆M
sao cho X = α−1(B). Trong trường hợp X là ngơn ngữ chính quy, ta luơn xây dựng được
một vị nhĩm cú pháp hữu hạn MX và đồng cấu cú pháp αX : A∗ → MX thỏa X . Khi đĩ,
ta gọi k = |MX | là chỉ số tương đẳng cú pháp của X .
2. THỦ TỤC SARDINAS-PATTERSON XÁC ĐỊNH TÍNH CHẤT MÃ
CỦA NGƠN NGỮ
Cho tập X của các từ trên bảng chữ A, dựa vào định nghĩa của mã, thủ tục Sardinas-
Patterson [12] đưa ra cách tính tốn các tập thương để tìm hai phân tích khác nhau của
một xâu w bất kỳ trong X , w ∈ A∗. Thủ tục Sardinas-Patterson xác định các tập thương
Ui, i = 0, 1, ... được xác định một cách đệ quy như sau:
U0 = X
−1X − {ε}
Ui+1 = U
−1
i X ∪X
−1Ui, i ≥ 0
(2.1)
Tính đúng đắn của thủ tục Sardinas-Patterson dựa trên Định lý 2.1 sau đây:
Định lý 2.1. ([12]). Tập X ⊆ A+ là mã khi và chỉ khi các tập Ui được xác định theo cơng
thức (2.1) khơng chứa từ rỗng.
Chứng minh của Định lý 2.1 dựa trên Bổ đề 2.1 sau đây:
Bổ đề 2.1. ([12]). Cho X ⊆ A+ và (Ui)i≥0 được định nghĩa theo cơng thức (2.1). Với ∀i > 0
và k ∈ {0, ..., i}, chúng ta cĩ ε ∈ Ui khi và chỉ khi tồn tại một từ w ∈ Ui và m, n ≥ 0 sao cho
wXm ∩Xn 6= ∅, m+ n+ k = i.
Mệnh đề sau đây khẳng định sự tồn tại của thuật tốn Sardinas-Patterson khi X là tập
đốn nhận được.
Mệnh đề 2.1. ([12]). Nếu X là một tập đốn nhận được, thì tập tất cả các Ui (i ≥ 0) là
hữu hạn.
Nhận xét 2.1. Mệnh đề 2.1 khẳng định Định lý 2.1 cung cấp một thuật tốn kiểm tra một
ngơn ngữ chính quy X bất kỳ cĩ là mã khơng.
Ví dụ 2.1. Cho A = {a, b} và X = {b, abb, abbba, bbba, baabb}. Tập X khơng là mã vì tồn tại
từ w = abbbabbbaabb, w cĩ hai phân tích khác nhau trong X :
w = (abbba)(bbba)(abb) = (abb)(b)(abb)(baabb).
Sử dụng thuật tốn kiểm tra mã, ta cĩ:
U0 = {ba, aabb, bba} , U1 = {a, ba, abb} , U2 = {ε, a, ba, bb, bbba, abb}.
Vì ε ∈ U2, suy ra X khơng là mã.
THUẬT TỐN XÁC ĐỊNH TÍNH CHẤT MÃ CỦA NGƠN NGỮ CHÍNH QUY 3
Nhận xét 2.2. Từ thuật tốn xác định tính chất mã của một ngơn ngữ ở trên, ta cĩ nhận
xét: Các tập Ui sẽ nhận được sau mỗi bước tính tốn nhờ áp dụng hữu hạn các phép ∪, ∩,
−, các phép cắt trái, phải. Nếu X là ngơn ngữ chính quy thì theo kết quả kinh điển, tồn
tại một vị nhĩm hữu hạn P và một đồng cấu vị nhĩm ϕ : A∗ → P thỏa X và các tập Ui,
i = 0, 1, ... Nghĩa là số các tập Ui khơng vượt quá số tập con của P (bằng 2|P |) (xem [12]).
Mệnh đề và hệ quả sau đây khẳng định điều này.
Mệnh đề 2.2. Cho X, Y ⊆ A∗ là hai ngơn ngữ chính quy, và hai đồng cấu vị nhĩm α :
A∗ → M và β : A∗ → N lần lượt thỏa X và Y , từ đĩ ta luơn xây dựng được một đồng cấu
(tồn cấu) vị nhĩm ϕ : A∗ → P , với P là một vị nhĩm hữu hạn, thỏa đồng thời cả X và Y .
Ví dụ 2.2. Cho vị nhĩm U1 = {0, 1}, với phần tử đơn vị là 1 và phần tử zero là 0, A là bảng
chữ hữu hạn khác rỗng và cho ngơn ngữ X thỏa bởi một đồng cấu vị nhĩm α : A∗ → M ,
ngơn ngữ Y = {ε} thỏa bởi đồng cấu vị nhĩm β : A∗ → U1, được xác định bởi: β(ε) = 1,
∀u ∈ A∗, β(u) = 0. Dễ thấy rằng, cả X và Y cùng thỏa bởi tồn cấu ϕ : A∗ → P , với
P ⊆ M × U1, được xác định bởi: ∀u ∈ A∗, ϕ(u) = (α(u), β(u)). Khi đĩ, P là vị nhĩm được
sinh bởi ϕ(u), ∀u ∈ A∗. Nếu |M | là hữu hạn thì |P | ≤ 2.k, với k = |M | là chỉ số tương đẳng
cú pháp của X .
Từ Mệnh đề 2.2, ta cĩ Hệ quả 2.1 sau đây.
Hệ quả 2.1. Cho X, Y ⊆ A∗ là hai ngơn ngữ chính quy. Nếu X và Y cùng thỏa bởi tồn
cấu vị nhĩm ϕ : A∗ → P , với P là một vị nhĩm hữu hạn, thì ϕ cũng thỏa mọi L ∈ A(X, Y )
trong đĩ A là lớp ngơn ngữ sinh bởi X , Y nhờ sử dụng hữu hạn các phép ∪, ∩, −, các phép
cắt trái, cắt phải.
Chứng minh. Theo giả thiết X = ϕ−1(B), Y = ϕ−1(C), với B,C ⊆ P . Với mọi x ∈ X ∪ Y ,
ϕ(x) ∈ B hoặc ϕ(x) ∈ C, suy ra
X ∪ Y = ϕ−1(B ∪C) = ϕ−1(B) ∪ ϕ−1(C).
Do đĩ ϕ thỏa ngơn ngữ X ∪ Y . Lập luận tương tự với phép ∩ và phép −.
Theo định nghĩa: B−1C = {m ∈ P | ∃b ∈ B : bm = c ∈ C} ⇒ X−1Y = ϕ−1(B−1C). Do
đĩ ϕ thỏa ngơn ngữ X−1Y . Lập luận tương tự với phép XY −1. 
Nhận xét 2.3. Nếu X ⊆ A+ là ngơn ngữ chính quy và với mọi tập Vi, i = 0, 1, ... thỏa bởi
tồn cấu vị nhĩm ϕ : A∗ → P , với P là một vị nhĩm hữu hạn, và các tập Vi cĩ tính
chất V0 ⊆ V1 ⊆ . . . ⊆ A∗ thì tồn tại Ki ⊆ P sao cho Vi = ϕ−1(Ki), i = 0, 1, .... Khi đĩ
K0 ⊆ K1 ⊆ . . . ⊆ P . Nghĩa là số tập Vi khơng vượt quá số phần tử của P . Nhận xét này là
cơ sở để ta xây dựng thuật tốn kiểm tra mã trong phần tiếp theo.
3. THUẬT TỐN XÁC ĐỊNH TÍNH CHẤT MÃ CỦA NGƠN NGỮ
CHÍNH QUY
Dựa trên các nhận xét trên, chúng tơi đề xuất một thủ tục mới để kiểm tra một ngơn
ngữ chính quy X ⊆ A+ cho trước cĩ là mã khơng bằng phương pháp tổ hợp mới để tính
tốn các tập thương Vi, i = 0, 1, ... một cách đệ quy như sau:
V0 = X
−1X − {ε}
Vi+1 = (V
−1
i X ∪X
−1Vi) ∪ Vi, i ≥ 0
(3.1)
4 NGUYỄN ĐÌNH HÂN, HỒ NGỌC VINH, PHAN TRUNG HUY, ĐỖ LONG VÂN
Tính đúng đắn của thủ tục dựa trên Định lý 3.1 và các Bổ đề sau đây.
Bổ đề 3.1. Cho X ⊆ A+ và (Vi)i≥0 được xác định theo cơng thức (3.1). Với mọi i ≥ 0,
z ∈ A∗ nếu z ∈ Vi thì tồn tại n,m ≥ 1, x1, x2, ..., xn, y1, y2, ..., ym ∈ X sao cho
x1x2 ... xnz = y1y2 ... ym, x1 6= y1.
Chứng minh. Ta chứng minh quy nạp theo i điều khẳng định trên.
+ Với i = 0 : Từ z ∈ V0 ta phải chứng minh tồn tại n,m ≥ 1, x1, x2, ..., xn, y1, y2, ..., ym ∈ X
sao cho x1x2 ... xnz = y1y2 ... ym, x1 6= y1.
Từ định nghĩa V0 = X−1X − {ε}, z ∈ V0, suy ra z ∈ X−1X − {ε}, nghĩa là tồn tại
x1, y1 ∈ X sao cho x1z = y1. Vì ε /∈ V0 suy ra x1 6= y1.
Vậy, điều khẳng định đúng với i = 0.
+ Bước quy nạp, giả sử điều khẳng định đã đúng với i = k, ta chứng minh nĩ cũng đúng
với trường hợp i = k + 1.
Với i = k+1, từ z ∈ Vi ta phải chứng minh tồn tại n,m ≥ 1, x1, x2, ..., xn, y1, y2, ..., ym ∈
X sao cho x1x2 ... xnz = y1y2 ... ym, x1 6= y1.
Theo định nghĩa: Vk+1 = (V −1k X ∪ X
−1Vk) ∪ Vk. Khi đĩ, với z ∈ Vk+1, suy ra z ∈ Vk
(trường hợp 1) hoặc z ∈ V −1
k
X (trường hợp 2) hoặc z ∈ X−1Vk (trường hợp 3).
Ta xét các trường hợp như sau:
- Trường hợp 1: z ∈ Vk, theo giả thiết quy nạp, điều khẳng định đúng.
- Trường hợp 2: z ∈ V −1
k
X , suy ra tồn tại z′ ∈ Vk, x ∈ X sao cho z′z = x. Vì z′ ∈ Vk, theo
giả thiết quy nạp, tồn tại l, s ≥ 1, x1, x2, ..., xl, y1, y2, ..., ys ∈ X sao cho
x1x2 ... xlz
′ = y1y2 ... ys, x1 6= y1.
Nhân z vào hai vế của biểu thức trên, ta cĩ:
x1x2 ... xlz
′z = y1y2 ... ysz, x1 6= y1.
Thay z′z = x vào trên ta cĩ:
x1x2 ... xlx = y1y2 ... ysz, x1 6= y1.
- Trường hợp 3: z ∈ X−1Vk, suy ra tồn tại x ∈ X, z′ ∈ Vk sao cho xz = z′. Vì z′ ∈ Vk, theo
giả thiết quy nạp, tồn tại l, s ≥ 1, x1, x2, ..., xl, y1, y2, ..., ys ∈ X sao cho
x1x2 ... xlz
′ = y1y2 ... ys, x1 6= y1.
Thay z′ = xz vào biểu thức trên, ta cĩ:
x1x2 ... xlxz = y1y2 ... ys, x1 6= y1.
Vậy, điều khẳng định đúng với mọi i ≥ 0. 
Bổ đề 3.2. Cho X ⊆ A+ và (Vi)i≥0 được xác định theo cơng thức (3.1). Với mọi x1, x2, ..., xn,
y1, y2, ..., ym ∈ X , n,m ≥ 1 và ∀z ∈ A∗: |z| < |ym|, nếu x1x2 ... xnz = y1y2 ... ym, x1 6= y1
thì tồn tại i ≥ 0 sao cho z ∈ Vi.
Chứng minh. Ta chứng minh quy nạp theo n điều khẳng định trên.
+ Với n = 0, từ dãy x1z = y1y2 ... ym, |z| < |ym|, x1 6= y1 ta phải chứng minh tồn tại i ≥ 0
sao cho z ∈ Vi. Theo giả thiết x1 6= y1, ta xét 2 trường hợp sau:
- Trường hợp 1: |x1| < |y1|. Theo giả thiết x1 6= ε, |z| < |ym|, suy ra m = 1. Khi đĩ, ta cĩ
thể viết x1z = y1, x1 6= y1. Vậy, z ∈ (X−1X − {ε}) = V0.
- Trường hợp 2: |x1| > |y1|. Vì |z| < |ym|, suy ra tồn tại u ∈ A+ sao cho ym = uz. Từ đẳng
thức x1z = y1y2 ... ym, x1 6= y1, suy ra x1z = y1y2 ... ym−1uz, x1 6= y1. Khi đĩ:
y−1
1
x1 = y2y3 ... ym−1u ∈ V0
THUẬT TỐN XÁC ĐỊNH TÍNH CHẤT MÃ CỦA NGƠN NGỮ CHÍNH QUY 5
⇒ y−1
2
V0 = y3 ... ym−1u ∈ V1
. . .
⇒ y−1m−1Vm−2 = u ∈ Vm−1, ⇒ u
−1ym = z ∈ Vm
Vậy điều khẳng định đúng với n = 0.
+ Giả sử điều khẳng định đúng với n = k, ta chứng minh nĩ cũng đúng với n = k + 1. Từ
đẳng thức x1x2 ... xkxk+1z = y1y2 ... ym, x1 6= y1, ta chứng minh tồn tại i ≥ 0 sao cho z ∈ Vi.
Xét xâu xk+1z, ta cĩ ba trường hợp sau xảy ra:
- Trường hợp 1: |xk+1z| < |ym|, suy ra xk+1z ∈ Vi (theo quy nạp). Do đĩ, x−1k+1Vi = z ∈ Vi+1
- Trường hợp 2: xk+1z = ym, suy ra x−1k+1ym = z. Nếu z 6= ε thì z ∈ V0 = (X
−1X − {ε}).
Ngược lại, nếu z = ε thì ε ∈ Vi nào đĩ.
Thật vậy, theo giả thiết ta cĩ x1x2 ... xk+1z = y1y2 ... ym, x1 6= y1. Vì xk+1z = ym, suy
ra x1x2 ... xk = y1y2 ... ym−1, x1 6= y1 hay x1x2 ... xkε = y1y2 ... ym−1, x1 6= y1. Theo giả thiết
quy nạp, suy ra ε ∈ Vi nào đĩ.
- Trường hợp 3: |xk+1z| > |ym|. Theo giả thiết |z| < |ym|, suy ra tồn tại u ∈ A+ sao cho
ym = uz. Từ |xk+1z| > |ym| và ym = uz, suy ra tồn tại u′ ∈ A+, ys ∈ X , 1 ≤ s ≤ m − 1,
|u′| < |ys| sao cho xk+1 = u′ys+1ys+2 . . . ym−1u.
Hơn nữa theo giả thiết quy nạp x1x2 ... xkxk+1z = y1y2 ... ym, x1 6= y1. Thay ym = uz và
xk+1 = u
′ys+1ys+2 ... ym−1u vào trên ta cĩ: x1x2 ... xku′ys+1ys+2 ... ym−1uz = y1y2 ... ym−1uz,
x1 6= y1. Suy ra x1x2 ... xku′ = y1y2 ... ys, x1 6= y1.
Theo quy nạp, suy ra u′ ∈ Vi với i nào đĩ. Do đĩ, ta cĩ :
u′−1xk+1 = ys+1ys+2 ... ym−1u ∈ Vi+1 = V
−1
i X
⇒ y−1s+1Vi+1 = ys+2 ... ym−1u ∈ Vi+2
. . .
⇒ y−1m−1Vi+m−1 = u ∈ Vi+m ⇒ u
−1ym = z ∈ Vi+m+1.
Vậy điều khẳng định đúng với mọi n ≥ 0. 
Định lý 3.1. Cho X ⊆ A+ và (Vi)i≥0 được xác định theo cơng thức (3.1). Khi đĩ, X là mã
khi và chỉ khi ε /∈ Vi, với mọi i ≥ 0.
Chứng minh. (⇒) X là mã thì ε /∈ Vi với mọi i ≥ 0.
Ta chứng minh bằng phản chứng. Giả sử tồn tại i ≥ 0 sao cho ε ∈ Vi. Khi đĩ, theo Bổ
đề 3.1, tồn tại n,m ≥ 1, x1, x2, . . . , xn, y1, y2, . . . , ym ∈ X sao cho x1x2 ... xnε = y1y2 ... ym,
x1 6= y1 hay x1x2 ... xn = y1y2 ... ym, x1 6= y1, đây là hai phân tích khác nhau của một từ
trong X . Suy ra X khơng là mã, mâu thuẫn.
(⇐) Ta chứng minh ε /∈ Vi với mọi i ≥ 0 thì X là mã.
Ta chứng minh bằng phản chứng. Giả sử X khơng là mã. Khi đĩ, tồn tại w ∈ A∗ cĩ hai
phân tích: w = x1x2 ... xn = y1y2 ... ym, x1 6= y1, xi, yj ∈ X , i = 1, .., n, j = 1, .., m. Hay ta
cĩ thể viết x1x2 ... xnε = y1y2 ... ym, x1 6= y1, xi, yj ∈ X . Vì |yj| > |ε|, j = 1, .., m, suy ra tồn
tại i ≥ 0 sao cho ε ∈ Vi (theo Bổ đề 3.2), mâu thuẫn. Vậy, X là mã. 
Hệ quả 3.1. Cho X ⊆ A+ và (Vi)i≥0 được xác định theo cơng thức (3.1). Nếu Vi = ∅ thì X
là mã.
Chứng minh. Ta chứng minh nếu Vi = ∅ thì X là mã. Thật vậy, theo cách xác định Vi như
trên, nếu cĩ Vi = ∅ ⇒ Vi−1 = ∅ ⇒ . . . ⇒ V0 = ∅ hay Vi = ∅, với mọi i ≥ 0. Do đĩ, ta
cĩ ε /∈ Vi, với mọi i ≥ 0. Theo Định lý 3.1, suy ra X là mã. 
6 NGUYỄN ĐÌNH HÂN, HỒ NGỌC VINH, PHAN TRUNG HUY, ĐỖ LONG VÂN
Hệ quả 3.2. Cho X ⊆ A+ và (Vi)i≥0 được xác định theo cơng thức (3.1). Nếu tồn tại i ≥ 0
sao cho Vi+1 = Vi và ε /∈ Vs, với i ≥ s ≥ 0 thì X là mã.
Chứng minh. Ta phải chứng minh nếu ε /∈ Vs, với mọi s ≤ i, Vi+1 = Vi thì X là mã. Thật
vậy, theo định nghĩa:
Vi+2 = (V
−1
i+1X ∪ X
−1Vi+1) ∪ Vi+1
Nếu cĩ Vi+1 = Vi, thì thay Vi+1 bởi Vi ta cĩ:
Vi+2 = (V
−1
i X ∪ X
−1Vi) ∪ Vi = Vi+1 = Vi
Tương tự, ta cĩ Vn = Vi, với mọi n ≥ 0. Vì ε /∈ Vs, suy ra ε /∈ Vn = Vs, với mọi i ≥ s ≥ 0.
Do đĩ, ta cĩ ε /∈ Vs, với mọi i ≥ s ≥ 0. Theo Định lý 3.1, suy ra X là mã. 
Với một ngơn ngữ bất kỳ thuộc lớp ngơn ngữ chính quy, số các tập Vi, i = 0, 1, ... xác
định như trên là hữu hạn. Từ thủ tục, ta nhận được một thuật tốn mới để kiểm tra một
ngơn ngữ chính quy cĩ là mã hay khơng:
* Thuật tốn ESP (the Extension of Sardinas and Patterson Algorithm)
Input: Cho X ⊆ A+, X là ngơn ngữ chính quy.
Output: Kết luận X là mã hoặc khơng.
Bước_1. V0 = X−1X − {ε} , n = 0
If V0 = ∅ Then goto Bước_4
Bước_2. (Loop)
Vn+1 = (V
−1
n X ∪ X
−1Vn) ∪ Vn
Bước_3. If ε ∈ Vn+1 Then goto Bước_5
If Vn = Vn+1 Then goto Bước_4
Else n = n+ 1, Loop
Bước_4. Thơng báo "X là mã" và Kết thúc.
Bước_5. Thơng báo "X khơng là mã" và Kết thúc.
Nhận xét 3.1. Cho X là ngơn ngữ chính quy thỏa bởi đồng cấu đại số α : A∗ → M , với M
là một vị nhĩm hữu hạn, và ngơn ngữ Y = {ε}. Theo Hệ quả 2.1, |A(X, Y )| cĩ cỡ 22.k và |P |
cĩ cỡ 2.k, với k là chỉ số tương đẳng cú pháp của X . Khi đĩ, thuật tốn Sardinas-Patterson
sẽ cho câu trả lời khẳng định sau tối đa 22.k bước, với mỗi bước là một bước tính Ui+1 từ
Ui theo cơng thức (2.1) (là số tối đa các tập Ui ⊆ A(X, Y ) khác nhau, ∀i ≥ 0). Thuật tốn
mở rộng ESP được đề xuất trên đây đưa ra câu trả lời với số bước tối đa chỉ là 2.k, với mỗi
bước là một bước tính Vi+1 từ Vi theo cơng thức (3.1).
Ví dụ 3.1. Cho A = {a, b, c, d},X = {a, ab, bc, cb, abd}. Theo thuật tốn Sardinas-Patterson,
ta cĩ: U0 = {b, bd, d}, U1 = {c}, U2 = {b}, U3 = {c}. Vì U3 = U1, suy ra X là mã. Theo
thuật tốn ESP, ta cĩ: V0 = {b, bd, d}, V1 = V2 = {b, c, bd, d}. Vì V2 = V1, suy ra X là mã.
Ví dụ 3.1 minh họa một trường hợp đặc biệt, do tính chất bao hàm của các tập Vi, thuật
tốn ESP dừng sau khi tính V2, cịn thuật tốn Sardinas-Patterson phải tiếp tục tính U3 vì
các tập Ui khác nhau, 2 ≥ i ≥ 0.
THUẬT TỐN XÁC ĐỊNH TÍNH CHẤT MÃ CỦA NGƠN NGỮ CHÍNH QUY 7
Tổng quát, theo thuật tốn Sardinas-Patterson, các tập Ui sẽ được xác định nhờ áp dụng
hữu hạn các phép ∪, ∩, −, các phép cắt trái, cắt phải. Theo Hệ quả 2.1, ϕ thỏa tất cả các
tập Ui, nghĩa là số các tập Ui khơng vượt quá số tập con của P (bằng 22.k). Trong trường
hợp xấu nhất, thuật tốn kiểm tra tính chất mã theo Sardinas-Patterson cĩ độ phức tạp cỡ
hàm mũ O(22.k) theo số bước đã nêu.
Bây giờ ta sẽ xem xét thuật tốn ESP với các tập Vi, i = 0, 1, ... được định nghĩa theo
cơng thức (3.1). Vì Vi thỏa bởi ϕ, đặt V0 = ϕ−1(K0), V1 = ϕ−1(K1), . . . , Vi = ϕ−1(Ki),
trong đĩ Ki ⊆ P . Vì V0 ⊆ V1 ⊆ . . . ⊆ Vi ⊆ A∗ nên ta cĩ khẳng định sau đây:
Nếu các tập Vi khác nhau với mọi i, khi đĩ: K0 ⊆ K1 ⊆ . . . ⊆ Ki ⊆ P . Số tập Ki là hữu
hạn và khơng vượt quá |P | tập, suy ra số các tập Vi khơng vượt quá |P | tập. Ngược lại, nếu
cĩ sự lặp lại của các tập Vi thì số tập Ki khác nhau như trên và khơng vượt quá |P | tập. Do
đĩ, số các bước thực hiện để tính tốn các tập Vi là hữu hạn và khơng vượt quá |P | bước.
Như vậy, ta cĩ thể kết luận: nếu ta chỉ quan tâm đến số các tập Vi khác nhau như trong
thuật tốn Sardinas-Patterson thì thuật tốn ESP cĩ độ phức tạp cỡ O(|P |) ≈ O(k).
Mặt khác, nếu độ phức tạp của mỗi bước tính Vi+1 từ Vi kể đến từng phép tính trên
vị nhĩm P , cĩ cỡ (|P |.|P |+ |P |.|P |) và xây dựng vị nhĩm P địi hỏi tối đa |P |3 phép tính
trên vị nhĩm M nhờ thuật tốn loang dần, thì độ phức tạp của thuật tốn kiểm định mã
ESP theo số bước và các phép tính cơ sở trên vị nhĩm P trong trường hợp xấu nhất là
O(|P |3) ≈ O(k3). Lưu ý rằng nếu X cho bởi một otomat hữu hạn cĩ k trạng thái, thuật
tốn kiểm định mã theo [9] cĩ độ phức tạp cỡ O(l2.k4) như đề cập trong phần mở đầu. Điều
này cho thấy vai trị cải tiến của thuật tốn ESP.
Ví dụ 3.2. Cho A = {a, b}, X = {aa, baa, ba}. Theo thuật tốn trên ta cĩ:
V0 = {a}, V1 = {a}. Ta cĩ V0 = V1, suy ra X là mã.
Ví dụ 3.3. Cho A = {a, b, c}, X = {ba, bac, cb}. Theo thuật tốn trên ta cĩ:
V0 = {c}, V1 = {c, b}, V2 = {c, b, a, ac},
V3 = {c, b, a, ac},
Ta cĩ V2 = V3, suy ra X là mã.
Ví dụ 3.4. Cho A = {a, b}, X = {aa, aab, baa, baab}. Theo thuật tốn trên ta cĩ:
V0 = {b}, V1 = {b, aa, aab}, V2 = {ε, b, aa, aab}
Vì ε ∈ V2, suy ra X khơng là mã.
Ví dụ 3.5. Cho A = {a, b}, X = {a∗b}. Ta cĩ: V0 = ∅, suy ra X là mã.
4. KẾT LUẬN
Trong bài báo, chúng tơi giới thiệu chi tiết thuật tốn xác định tính chất mã của một
ngơn ngữ bất kỳ theo hướng mở rộng thuật tốn Sardinas-Patterson truyền thống. Kết quả
áp dụng đối với lớp ngơn ngữ chính quy cho thấy sự cải tiến khi đưa ra được thuật tốn chỉ
cĩ độ phức tạp tuyến tính thay vì độ phức tạp cỡ hàm mũ. Kết quả này sẽ được phát triển
trong nghiên cứu lý thuyết mã.
8 NGUYỄN ĐÌNH HÂN, HỒ NGỌC VINH, PHAN TRUNG HUY, ĐỖ LONG VÂN
TÀI LIỆU THAM KHẢO
[1] M. Anselmo, On zigzag codes and their decidability, Theory Computer Science 74
(1990) 341-354.
[2] D.L. Van, B. Lesae¨c and I. Litovsky, On coding morphisms for zigzag codes, Informatique
Théorique et Applications 26 (6) (1992) 565-580.
[3] F. Blanchet-Sadri and M. Margaret, Pcodes of Partial Words, Retrieved Jan 2011, from
University of North Carolina, Department of Mathematical Sciences, 2005.
[4] F.L. T¸iplea, E. Ma¨kinen, D. Trincă, and C. Enea, Characterization Results for Time-
Varying Codes, Fundamenta Informaticae 53 (2) (2002) 185-198.
[5] Hồ Ngọc Vinh, Phan Trung Huy, Đỗ Long Vân, Mở rộng mã và thuật tốn kiểm định
mã luân phiên và mã của các từ định biên Tạp chí Tin học và Điều khiển học 26 (4)
(2010) 301 - 311.
[6] D. Macro, “New techniques for Signal Representation and Coding”, Doctoral dissertation
No. ING-INF/03, Universitas Studiorum Brixiỉ, 2006.
[7] Phan Trung Huy, Nguyễn Đình Hân và Phạm Minh Chuẩn, Mã luân phiên chẵn - Phân
bậc độ nhập nhằng và tiêu chuẩn kiểm tra, Kỷ yếu Hội thảo quốc gia lần thứ XII, Một
số vấn đề chọn lọc của cơng nghệ thơng tin và truyền thơng, Biên Hịa, 5-6/8, 2009
(171-185).
[8] Hồ Ngọc Vinh, Nguyễn Đình Hân, Phan Trung Huy, Mã với tích biên và độ trễ giải mã
Tạp chí Cơng nghệ Thơng tin và Truyền thơng V-1 (4) (24) (2010) 46-56.
[9] M. Robert, An O(n2) Time Algorithm for Deciding Whether a Regular Language is a
Code, Journal of Computing and Information 2 (1) (1996) 79-89.
[10] W. Andreas and H. Tom, The finest homophonic partition and related code concepts.
Lecture Notes in Computer Science 841 (1994) 618-628.
[11] J. Falucskai, On equivalence of two tests for codes, Acta Mathematica Academiae Paed-
agogicae Nyíregyháziensis 24 (2008) 249-256.
[12] J. Berstel, D. Perrin and C. Reutenauer, Theory of Codes, Academic Press Inc.,
NewYork, 1985.
[13] G. Lallement, Semigroups and Combinational Applications, John Wiley and Sons, Inc.,
1979.
Ngày nhận bài 24 - 2 - 2011