Thuật toán mới xác định độ trễ giải mã của ngôn ngữ chính quy

t½ch Prod(A1,A2), nh¢n
cõa ÷íng i giúa hai tr¤ng th¡i k¸ ti¸p (fG, qi) v  (fG, qj) (ho°c (pi, f2) v  (pj , f2),
ho°c (s1, qi) v  (fG, qj), ho°c (pi, s2) v  (pj , f2)) l  tø thuëc L.
4. XC ffiÀNH ffiË TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY
Cho ngæn ngú ch½nh quy L ÷ñc o¡n nhªn bði ætæmat húu h¤n A, º x¡c ành ë tr¹
gi£i m¢ cõa L, tr÷îc h¸t ta gi£i quy¸t b i to¡n bê trñ tr¶n ç thà nh÷ d÷îi ¥y.
4.1. B i to¡n v· chu tr¼nh hñp l» tr¶n ç thà
Cho ç thà húu h¤n câ h÷îng (câ thº câ khuy¶n) G = (V,E) vîi hai ¿nh °c bi»t l  ¿nh
khði ¦u s v  ¿nh k¸t thóc f(s 6= f), tªp U ⊆ V gåi l  tªp ¿nh khâa (¿nh s v  f khæng
thuëc tªp U), c¡c ¿nh cán l¤i gåi l  ¿nh khæng khâa.
Cho ÷íng i pi gçm d¢y ¿nh v1, . . . , vj , . . . , vi, . . . , vk (vîi s = v1) tr¶n ç thà G. N¸u câ
1 < i < k sao cho vi ∈ U, vk = vj , 1 ≤ j ≤ i th¼ pi gåi l  chu tr¼nh hñp l» tr¶n ç thà G. ffi¿nh
vl, j ≤ l ≤ k gåi l  ¿nh trong cõa chu tr¼nh hñp l». ffi÷íng i pi gåi l  i qua ¿nh v, n¸u v
l  mët trong c¡c ¿nh vl, 2 ≤ l ≤ k. pi công ÷ñc gåi l  chùa ¿nh v, n¸u v l  mët trong c¡c
¿nh vl, 1 ≤ l ≤ k.
B i to¡n 1. Cho ç thà húu h¤n câ h÷îng G = (V,E) nh÷ ð tr¶n. Cho bi¸t tr¶n G câ tçn
t¤i chu tr¼nh hñp l» hay khæng.
ffiº gi£i b i to¡n tr¶n, tr÷îc h¸t ta x¥y düng ç thà sao ch²p G′ = (V ′, E′) tø ç thà
G = (V,E) nhí kß thuªt sao ch²p ç thà nh÷ sau:
i) Vîi v ∈ V sao ch²p th nh hai ¿nh (v, 1), (v, 2) cõa V ′.
ii) Vîi (u, v) ∈ E:
+ Sao ch²p th nh hai cung ((u, 1), (v, 1)), ((u, 2), (v, 2)) cõa E′;
+ N¸u u ∈ U th¼ bê sung cung ((u, 1), (v, 2)) v o E′;
H m x¥y düng ç thà sao ch²p G′ kþ hi»u l  XCopy(G), d÷îi ¥y l  gi£i thuªt:
Function XCopy(G)
146 ffiNG QUY˜T THNG, NGUY™N ffiœNH H…N, PHAN TRUNG HUY
Input: ffiç thà húu h¤n câ h÷îng G.
Output: ffiç thà sao ch²p G′ tø ç thà G.
{Gi£i thuªt dòng m£ng: key[q] = 1 khi v  ch¿ khi ¿nh q ∈ U}
1. V ′ = ∅;E′ = ∅;
2. for each u in V do
V ′ = V ′ ∪ {(u, 1), (u, 2)};
3. for each u in V do
4. for each v in Next(u) do
E′ = E′ ∪ {((u, 1), (v, 1)), ((u, 2), (v, 2))};
if key[u] = 1 then
E′ = E′ ∪ {((u, 1), (v, 2))};
5. return G′.
Nhªn x²t 4.1. i) ffiç thà sao ch²p G′ câ |V ′| = 2|V |, |E′| ≤ 3|E|.
ii) Tªp c¡c ¿nh d¤ng (v, k) c£m sinh trong G′ ç thà con Gk, k = 1, 2. Méi ç thà con Gk
·u ¯ng c§u vîi G. G′ thüc ch§t l  sü k¸t nèi câ chån låc cõa hai ç thà con G1, G2,
ch¿ câ c¡c cung i tø G1 ¸n G2 m  khæng câ chi·u ng÷ñc l¤i.
Hiºn nhi¶n ta câ bê · sau:
Bê · 4.1. Gi£i thuªt XCopy câ ë phùc t¤p thíi gian O(|V |+ |E|).
Vai trá cõa ç thà sao ch²p G′ trong vi»c x¡c ành chu tr¼nh hñp l» tr¶n G, ÷ñc cho bði
ành lþ sau:
ffiành lþ 4.1. Cho ç thà húu h¤n G = (V,E), câ ¿nh khði ¦u s ∈ V , ¿nh k¸t thóc
f ∈ V (s 6= f), vîi tªp ¿nh khâa U (¿nh s v  f khæng thuëc tªp U) v  G′ = XCopy(G).
Tr¶n G tçn t¤i chu tr¼nh hñp l» khi v  ch¿ khi tr¶n G′ tçn t¤i ÷íng i pi tø ¿nh (s, 1) ¸n
¿nh (v, 2) v  (v, 1) thuëc pi.
Chùng minh. (⇒) Tr¶n G tçn t¤i chu tr¼nh hñp l»: u1, . . . , uj , . . . , ui, . . . , uk, (vîi s = u1),
ta câ 1 < i < k sao cho ui ∈ U v  uj = uk, 1 ≤ j ≤ i. Theo c¡ch x¥y düng ç thà sao ch²p
G′, tr¶n nâ tçn t¤i ÷íng i pi sau:
(u1, 1), . . . , (uj , 1), . . . , (ui, 1), (ui+1, 2), . . . , (uk, 2),
ð â (s, 1) = (u1, 1), (uk, 2) = (v, 2). Do uj = v, 1 ≤ j ≤ i suy ra (v, 1) ∈ pi.
(⇐) Tr¶n G′ tçn t¤i ÷íng i pi tø ¿nh (s, 1) ¸n ¿nh (v, 2) v  (v, 1) ∈ pi. Theo c¡ch
x¥y düng ç thà sao ch²p G′, khi â ÷íng i pi câ d¤ng sau:
(u1, 1), . . . , (uj , 1), . . . , (ui, 1), (ui+1, 2), . . . , (uk, 2),
ð â (s, 1) = (u1, 1), (uk, 2) = (v, 2) v  ui ∈ U vîi 1 < i < k. Do (v, 1) ∈ pi, n¶n v = uj vîi 1 ≤
j ≤ i. T÷ìng ùng vîi ÷íng i pi, tr¶n G câ ÷íng i sau ¥y: u1, . . . , uj , . . . , ui, ui+1, . . . , uk,
ð â s = u1, uk = v, ui ∈ U vîi 1 < i < k, v  uk = uj vîi 1 ≤ j ≤ i. Hay tr¶n G câ chu tr¼nh
hñp l». 
ffiành lþ 4.1 l  cì sð cho ta x¥y düng gi£i thuªt x¡c ành câ chu tr¼nh hñp l» tr¶n G hay
khæng. Ta thüc hi»n tæ m u c¡c ¿nh tr¶n ç thà sao ch²p G′. Trong kß thuªt tæ m u, méi
THUŁT TON MÎI XC ffiÀNH ffiË TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY 147
¿nh câ thuëc t½nh mark º cho bi¸t ¿nh â ÷ñc tæ m u g¼, ta sû döng 4 m u nh÷ sau:
+ ffi¿nh (u, i) ÷ñc tæ m u WHITE (hay mark[(u, i)] = WHITE) º biºu di¹n ¿nh (u, i)
ch÷a ÷ñc th«m.
+ Tæ m u mët ¿nh ang x²t: N¸u nâ l  ¿nh d¤ng (u, 1) th¼ ÷ñc tæ m u BLUE, ng÷ñc
l¤i th¼ ÷ñc tæ m u GRAY. ffi°c bi»t khi mët ¿nh ang ÷ñc x²t (u, 1) ÷ñc tæ m u BLUE
th¼ ¿nh çng bë t÷ìng ùng (u, 2) công ÷ñc tæ m u BLUE. Tr¶n con ÷íng duy»t ç thà G′,
khði ¦u tø ¿nh (s, 1), n¸u ¸n ÷ñc ¿nh (u, 2) tæ m u BLUE th¼ theo ffiành lþ 4.1 tr¶n G
câ chu tr¼nh hñp l».
+ ffi¿nh ÷ñc tæ m u BLACK cho bi¸t ¿nh bà lo¤i.
Gi£i thuªt câ thº ÷ñc mæ t£ nh÷ sau:
i) Ban ¦u c¡c ¿nh tr¶n G′ ÷ñc tæ m u WHITE.
ii) Sau â ta gåi ¸n gi£i thuªt Visit tø mët ¿nh cho tr÷îc (s, 1), gi£i thuªt Visit ÷ñc
c£i ti¸n tø gi£i thuªt DFS (Depth First Search) (xem [15]) º tæ m u tr¶n G′.
Function Visit(graphG′, vertex (u, i))
1. if i = 1 then
mark[(u, 1)] = mark[(u, 2)] = BLUE
else mark[(u, i)] = GREY
2. for each (v, j) in Next((u, i)) do
if mark[(v, j)] = BLUE and j = 2 then return TRUE;
if mark[(v, j)]= WHITE then
if V isit(G′, (v, j)) then return TRUE
3. mark[(u, i)] = BLACK
if i = 1 and mark[(u, 2)] = BLUE then mark[(u, 2)] = WHITE
4. return FALSE
Function ContainsCycle(graphG′, vertex (u, i))
1. for each (u, 1) in V ′ do
mark[(u, 1)] = mark[(u, 2)] = WHITE
2. return V isit(G′, (u, i));
Nhªn x²t 4.2. i) Gi£i thuªt Visit ph¡t hi»n chu tr¼nh hñp l» (n¸u câ) tr¶n G.
ii) B÷îc thüc hi»n gi£i thuªt Visit ch¿ l  c£i ti¸n gi£i thuªt DFS, n¶n gi£i thuªt Contain-
sCycle câ ë phùc t¤p thíi gian l  O(|V ′|+ |E′|) = O(2|V |+ 3|E|) = O(|V |+ |E|).
4.2. Gi£i thuªt x¡c ành ë tr¹ gi£i m¢
B i to¡n 2. Cho ngæn ngú ch½nh quy L ⊆ Σ∗ ÷ñc o¡n nhªn bði ætæmat húu h¤n A.
H¢y x¥y düng gi£i thuªt x¡c ành ë tr¹ gi£i m¢ cõa L.
Gi£ sû A = (Q,Σ, E, I, F ) v  L = L(A). Ta x²t c¡c tr÷íng hñp sau:
148 ffiNG QUY˜T THNG, NGUY™N ffiœNH H…N, PHAN TRUNG HUY
a) N¸u L khæng l  m¢ th¼ k¸t thóc: Vi»c kiºm tra L câ l  m¢ hay khæng câ thº ¡p döng gi£i
thuªt cõa R. McCloskey (xem [1]). Ta kþ hi»u h m thüc hi»n kiºm tra l  CodeAlgo(A),
tr£ l¤i gi¡ trà TRUE n¸u L = L(A) l  m¢, ng÷ñc l¤i h m tr£ l¤i gi¡ trà FALSE, gi£i
thuªt câ ë phùc t¤p thíi gian O((|Q|+ |E|)2).
b) N¸u L l  m¢ th¼ L ⊆ Σ+: Ta x¥y düng A2 =Ex(Trim(D(A))) = (Q2,Σ, E2, s2, f2),
A1 =Graft(A2) = (Q1,Σ, E1, s1, f1) câ tr¤ng th¡i gh²p fG (ð â ta êi t¶n tr¤ng
th¡i gh²p tø f2 th nh fG, tr¤ng th¡i ¦u tø s2 th nh s1). L§y t½ch A1 vîi A2 ta câ
Prod(A1,A2).
Ta xem ε-ætæmat Prod(A1,A2) nh÷ mët ç thà húu h¤n câ h÷îng G(Prod(A1,A2) x¡c
ành mët ç thà câ h÷îng G), c¡c tr¤ng th¡i l  c¡c ¿nh cõa ç thà, câ ¿nh khði ¦u (s1, s2),
¿nh k¸t thóc (f1, f2), ¿nh (fG, f2) gåi l  ¿nh gh²p t½ch tr¶n ç thà G, tªp ¿nh khâa
U = {(fG, q) ∈ Q1 × Q2 | q 6= f2, s2}, mët cung cõa Prod(A1,A2) x¡c ành mët cung
cõa ç thà, cung i ¸n ¿nh khâa ÷ñc g¡n trång sè 1 c¡c cung cán l¤i ÷ñc g¡n trång sè 0.
H¼nh 4.1. T½nh ë tr¹ gi£i m¢ cõa L
Ph÷ìng ph¡p t½nh ë tr¹ gi£i m¢ câ thº mæ t£ nh÷ sau: L câ ë tr¹ gi£i m¢ d ≥ 0, khi â
d l  sè nguy¶n nhä nh§t sao cho:
∀x, x′ ∈ L,∀y ∈ Ld, ∀u ∈ Σ∗, xyu ∈ x′L∗ ⇒ x = x′
(hay d l  sè nguy¶n lîn nh§t m : ∃x, x′ ∈ L, x 6= x′, ∃y = y1y2 · · · yd−1 ∈ Ld−1, yi ∈ L,∃u ∈ Σ∗
sao cho xyu ∈ x′L∗ (ta công câ xyu = x′y′ vîi y′ = y′1y′2 . . . y′n ∈ L∗, y′i ∈ L)). Khi â, ta thüc
hi»n t½ch ε-ætæmat A1 o¡n nhªn L+Σ∗ vîi ε-ætæmat A2 o¡n nhªn L+. Tr¶n ç thà G x¡c
ành bði ε-ætæmat t½ch cõa A1 vîi A2, ta x¡c ành ÷íng i tø ¿nh khði ¦u ¸n ¿nh k¸t
thóc câ nhi·u ¿nh khâa (fG, qi) nh§t. Sè ¿nh khâa t¼m ÷ñc ch½nh l  ë tr¹ gi£i m¢ d cõa
L, nh÷ mæ t£ bði H¼nh 4.1.
Trong tr÷íng hñp L l  m¢, ta thi¸t lªp c¡c k¸t qu£ d÷îi ¥y:
Bê · 4.2. Cho ç thà G x¡c ành nh÷ ð tr¶n. N¸u tr¶n G câ chu tr¼nh hñp l» th¼ tçn t¤i
chu tr¼nh hñp l» thäa m¢n:
i) Khæng chùa ¿nh gh²p t½ch v  khæng i qua ¿nh khði ¦u.
ii) Tçn t¤i ¿nh trong ¸n ÷ñc ¿nh k¸t thóc.
Chùng minh. Tr¶n G câ chu tr¼nh hñp l» pi gçm d¢y ¿nh v1, . . . , vj , . . . , vi, . . . , vk vîi 1 <
i < k, vi ∈ U, vk = vj , 1 ≤ j ≤ i, hay pi câ d¤ng:
(p1, q1), . . . , (pj , qj), . . . , (fG, qi), . . . , (pk, qk),
vîi v1 = (p1, q1) = (s1, s2), vj = (pj , qj), vi = (fG, qi), vk = (pk, qk).
i) Khi â chu tr¼nh hñp l» pi khæng chùa ¿nh gh²p t½ch (fG, f2) v  khæng i qua ¿nh
khði ¦u (s1, s2), thªt vªy:
+ Gi£ sû pi i qua ¿nh khði ¦u vl = v1 vîi 1 < l ≤ j, khi â ta x²t chu tr¼nh hñp l» pi
b­t ¦u tø ¿nh khði ¦u vl.
THUŁT TON MÎI XC ffiÀNH ffiË TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY 149
+ Gi£ sû pi chùa ¿nh gh²p t½ch vl = (fG, f2) vîi 1 ≤ l ≤ j, tr¶n cì sð x¥y düng c¡c
ε-ætæmat A1, A2 v  ph²p t½ch ætæmat, ¿nh k¸ ti¸p câ thº i ¸n tø ¿nh gh²p t½ch (fG, f2)
tr¶n G, ch¿ câ thº l  ¿nh (f1, s2) ho°c ¿nh khði ¦u (s1, s2). ffi¿nh (f1, s2) khæng thº l 
¿nh k¸ ti¸p cõa ¿nh gh²p t½ch (fG, f2), v¼ tr¶n pi câ ¿nh khâa (fG, qi), m  tø ¿nh (f1, s2)
khæng thº ¸n ÷ñc ¿nh khâa (fG, qi). Vªy, k¸ ti¸p ¿nh gh²p t½ch (fG, f2) ch¿ câ thº l  ¿nh
(s1, s2), ta x²t chu tr¼nh hñp l» pi b­t ¦u tø ¿nh (s1, s2) n y.
+ Gi£ sû pi chùa ¿nh gh²p t½ch vl = (fG, f2) vîi j ≤ l ≤ k, khi â ta câ ÷íng i tr¶n
chu tr¼nh l :
(fG, f2)
x1−→ (fG, qi) x2−→ (pk, qk) x3−→ (fG, f2),
(ho°c (fG, f2)
x1−→ (pk, qk) x2−→ (fG, qi) x3−→ (fG, f2))
v¼ (fG, qi) l  ¿nh khâa n¶n qi 6= f2, s2. Tø Nhªn x²t 3.2 th¼ x1, x2x3 ∈ L+ (ho°c x1x2, x3 ∈
L+), suy ra, x¥u x1x2x3 câ hai ph¥n t½ch kh¡c nhau trong L, khi â L khæng l  m¢, i·u
n y tr¡i vîi gi£ thi¸t L l  m¢.
+ Gi£ sû pi i qua ¿nh khði ¦u vl = (s1, s2) vîi j ≤ l ≤ k, khi â ¿nh vl câ cung i
¸n nâ, tr¶n cì sð x¥y düng c¡c ε-ætæmat A1, A2 v  ph²p t½ch ætæmat th¼ ¿nh k¸ tr÷îc vl
trong chu tr¼nh pi l  ¿nh (fG, f2), nh÷ ph¥n t½ch ð tr¶n, i·u n y l  m¥u thu¨n.
ii) Chu tr¼nh pi câ ½t nh§t mët ¿nh trong ¸n ÷ñc ¿nh k¸t thóc (f1, f2) tr¶n G. Thªt
vªy, tr¶n pi câ ¿nh trong vl = (fG, qi) vîi j ≤ l ≤ k, qi 6= f2, s2, tr¶n cì sð x¥y düng c¡c
ε-ætæmat A1, A2 v  ph²p t½ch ætæmat, tø ¿nh (fG, qi) ta ¸n ÷ñc ¿nh (f1, qi) b¬ng mët
cung vîi nh¢n ε. Do A2 =Ex(Trim(D(A))), n¶n tø tr¤ng th¡i b§t ký qi tr¶n A2 ·u ¸n
÷ñc tr¤ng th¡i f2, v  tø f1 tr¶n A1 ch¿ câ c¡c cung ¸n ch½nh nâ vîi nh¢n l  kþ tü thuëc
Σ ∪ {ε}, vªy theo t½ch ætæmat th¼ tr¶n G ph£i câ ÷íng i tø (fG, qi) ¸n (f1, f2). 
ffiành lþ 4.2. Cho ngæn ngú ch½nh quy L ⊆ Σ+ l  m¢ ÷ñc o¡n nhªn bði ætæmat húu h¤n
A. Cho A1 = Graft(A2) câ tr¤ng th¡i gh²p fG vîi A2 = Ex(Trim(D(A))) v  Prod(A1,A2)
x¡c ành mët ç thà G nh÷ ð tr¶n.
i) L câ ë tr¹ gi£i m¢ væ h¤n khi v  ch¿ khi tr¶n G câ chu tr¼nh hñp l».
ii) L câ ë tr¹ gi£i m¢ d ≥ 0 khi v  ch¿ khi tr¶n G câ ÷íng i tø ¿nh khði ¦u ¸n ¿nh
k¸t thóc vîi trång sè lîn nh§t l  d.
Chùng minh. i) (⇒) L câ ë tr¹ gi£i m¢ væ h¤n, khi â x²t vîi mët sè nguy¶n khæng ¥m
b§t ký d, ta câ ∃x, x′ ∈ L, x 6= x′,∃y = y1y2 · · · yd ∈ Ld, yi ∈ L,∃u = u1u2 · · ·ul ∈ Σ∗, ui ∈ Σ
sao cho xyu ∈ x′L∗. Vîi tø xyu, trong A1 câ ÷íng i pi nh¢n xyu:
s1
x−→ fG ε−→ s1 y1−→ fG ε−→ s1 · · · s1 yd−→ fG ε−→ f1 u1−→ f1 · · · f1 ul−→ f1.
T÷ìng tü vªy, vîi xyu = x′y′1y′2 · · · y′n ∈ x′L∗, y′i ∈ L trong A2 câ ÷íng i θ nh¢n xyu:
s2
x′−→ f2 ε−→ s2 y
′
1−→ f2 ε−→ s2 · · · s2 y
′
n−→ f2.
Khi â, tr¶n ç thà G câ ÷íng i ρ ÷ñc t¤o n¶n tø pi v  θ, khði ¦u tø (s1, s2) v  k¸t
thóc l  (f1, f2) nh÷ sau:
(s1, s2), . . . , (fG, qi), . . . , (pj , f2), . . . , (f1, f2),
150 ffiNG QUY˜T THNG, NGUY™N ffiœNH H…N, PHAN TRUNG HUY
do L l  m¢ n¶n qi 6= f2, s2 v  pj 6= fG, s1, do ta câ thº chån d tòy þ õ lîn (ch¯ng h¤n d
lîn hìn sè tr¤ng th¡i cõa A1), sè tr¤ng th¡i cõa A1 l  húu h¤n, n¶n trong ρ ph£i tçn t¤i hai
¿nh (fG, qi) tròng nhau, hay nâi c¡ch kh¡c trong G câ chu tr¼nh hñp l».
(⇐) Tr¶n G câ chu tr¼nh hñp l» pi gçm d¢y ¿nh v1, . . . , vj , . . . , vi, . . . , vk vîi 1 < i <
k, vi ∈ U, vk = vj , 1 ≤ j ≤ i, hay pi l  ÷íng i câ nh¢n nh÷ sau:
(p1, q1)
x1−→ (pj , qj) x2−→ (fG, qi) x3−→ (pk, qk)
vîi v1 = (p1, q1) = (s1, s2), vj = (pj , qj), vi = (fG, qi) ∈ U, vk = (pk, qk).
Theo Bê · 4.2 ta câ pi khæng chùa ¿nh gh²p t½ch (fG, f2), khæng i qua ¿nh khði ¦u
(s1, s2) v  tçn t¤i ¿nh trong (fG, qi) ¸n ÷ñc ¿nh k¸t thóc (f1, f2) tr¶n G. Khi â tr¶n G
câ ÷íng i ρ câ nh¢n sau ¥y:
(s1, s2)
x1−→ (pj , qj) x2−→ (fG, qi) x3−→ (pj , qj) x2−→ (fG, qi) x3−→ · · ·
· · · x2−→ (fG, qi) x3−→ (pj , qj) x2−→ (fG, qi) ε−→ (f1, qi) u−→ (f1, f2),
ta công câ tr¶n ρ khæng chùa ¿nh (fG, f2), khæng i qua ¿nh (s1, s2). Khæng l m m§t
t½nh têng qu¡t, ta gi£ sû (fG, qi) l  ¿nh khâa ¦u ti¶n tr¶n ρ. Theo Nhªn x²t 3.2 th¼ ta câ
x3x2 ∈ L+. Vªy, vîi d lîn tòy þ, ∃x = x1x2, x 6= x′ ∈ L,∃y = (x3x2)d ∈ L+,∃u ∈ Σ∗ sao cho
xyu ∈ x′L∗, hay nâi c¡ch kh¡c L câ ë tr¹ gi£i m¢ væ h¤n.
ii) (⇒) N¸u L câ ë tr¹ gi£i m¢ d
+ Ta x²t vîi d = 0 th¼
∀x, x′ ∈ L,∀u ∈ Σ∗, xu ∈ x′L∗ ⇒ x = x′.
Tr¶n cì sð x¥y düng c¡c ε-ætæmat A1, A2 v  ph²p t½ch ætæmat. N¸u d = 0 th¼ tr¶n G,
måi ÷íng i tø ¿nh khði ¦u ¸n ¿nh k¸t thóc khæng câ ¿nh khâa, khi â måi cung tr¶n
c¡c ÷íng i n y ·u câ trång sè 0, vªy ÷íng i tø ¿nh khði ¦u ¸n ¿nh k¸t thóc câ
trång sè lîn nh§t l  d = 0.
+ Ta x²t vîi d > 0
∀x, x′ ∈ L,∀y ∈ Ld, ∀u ∈ Σ∗, xyu ∈ x′L∗ ⇒ x = x′,
hay d l  lîn nh§t thäa m¢n:
∃x, x′ ∈ L, x 6= x′,∃y = y1y2 · · · yd−1 ∈ Ld−1, yi ∈ L,∃u = u1u2 · · ·ul ∈ Σ∗, uj ∈ Σ
sao cho xyu ∈ x′L∗ (ta công câ xyu = x′y′ vîi y′ = y′1y′2 · · · y′n ∈ L∗, y′i ∈ L).
(4.2)
Vîi x¥u xyu trong A1 tçn t¤i ÷íng i pi nh÷ sau:
s1
x−→ fG ε−→ s1 y1−→ fG ε−→ s1 · · · s1 yd−1−−−→ fG ε−→ f1 u1−→ f1 · · · f1 ul−→ f1.
T÷ìng tü vªy, vîi x¥u x′y′ trong A2 tçn t¤i ÷íng i θ:
s2
x′−→ f2 ε−→ s2 y
′
1−→ f2 ε−→ s2 · · · s2 y
′
n−→ f2.
Khi â, theo t½ch ætæmat, trong ç thà G câ ÷íng i ρ ÷ñc t¤o l¶n tø pi v  θ, khði ¦u
tø (s1, s2) v  k¸t thóc l  (f1, f2) nh÷ sau:
(s1, s2)
x−→ (fG, q1) ε−→ (s1, q1) y1−→ (fG, q2) ε−→ (s1, q2) · · ·
(s1, qd−1)
yd−1−−−→ (fG, qd) ε−→ (f1, p1) u1−→ (f1, p2) · · · (f1, pl) ul−→ (f1, f2)
THUŁT TON MÎI XC ffiÀNH ffiË TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY 151
do x 6= x′ v  L l  m¢ n¶n qi 6= f2, s2, vîi måi i = 1, . . . , d. V¼ d l  lîn nh§t thäa m¢n 4.2 n¶n
÷íng i ρ tr¶n G tø ¿nh khði ¦u (s1, s2) ¸n ¿nh k¸t thóc (f1, f2) câ trång sè lîn nh§t
l  d.
(⇐) N¸u tr¶n G câ ÷íng i ρ tø ¿nh khði ¦u ¸n ¿nh k¸t thóc câ trång sè lîn nh§t
d.
+ Tr÷íng hñp d = 0. Khi â, tr¶n b§t ký mët ÷íng i tø ¿nh khði ¦u ¸n ¿nh k¸t
thóc khæng câ ¿nh khâa. Ta câ
∀x, x′ ∈ L,∀u ∈ Σ∗, xu ∈ x′L∗ ⇒ x = x′.
Hay ë tr¹ gi£i m¢ cõa L l  b¬ng 0.
+ Tr÷íng hñp d > 0. Khi â ÷íng i ρ câ d¤ng:
(s1, s2)
x−→ (fG, q1) y1−→ (fG, q2) y2−→ (fG, q3) · · · (fG, qd−1) yd−1−−−→ (fG, qd) ε−→ (f1, p1) u−→ (f1, f2)
ð â qi 6= f2, s2, vîi i = 1, . . . , d v  x, y1, . . . , yd−1 ∈ L, u ∈ Σ∗. T÷ìng ùng vîi ÷íng i ρ
tr¶n G th¼ tr¶n A1 tçn t¤i ÷íng i pi vîi nh¢n xyu = xy1 · · · yd−1u:
s1
x−→ fG y1−→ fG y2−→ fG · · · fG yd−1−−−→ fG ε−→ f1 u−→ f1
v  tr¶n A2 công tçn t¤i ÷íng i θ vîi nh¢n x′y′, x′ ∈ L, y′ ∈ L∗ sao cho xyu = x′y′:
s2
x′−→ f2 y
′
−→ f2.
Vªy d l  lîn nh§t m  ∃x, x′ ∈ L, x 6= x′, ∃y ∈ Ld−1,∃u ∈ Σ∗ sao cho xyu ∈ x′L∗, hay d l 
nhä nh§t sao cho: ∀x, x′ ∈ L,∀y ∈ Ld, ∀u ∈ Σ∗, xyu ∈ x′L∗ ⇒ x = x′, suy ra L câ ë tr¹ gi£i
m¢ d. 
D÷îi ¥y l  gi£i thuªt x¡c ành ë tr¹ gi£i m¢ cõa ngæn ngú ch½nh quy L ⊆ Σ∗.
Gi£i thuªt DecipheringDelay(A)
Input: Ætæmat húu h¤n A v  L = L(A) ⊆ Σ∗.
Output: Thæng b¡o trong tr÷íng hñp L khæng l  m¢ ho°c câ ë tr¹ gi£i m¢ væ h¤n,
ng÷ñc l¤i gi£i thuªt tr£ l¤i ë tr¹ gi£i m¢ cõa L.
1. if not CodeAlgo(A) then Return (L khæng l  m¢);
2. A2 = Ex(Trim(D(A))) = (Q2,Σ, E2, s2, f2);
A1 = Graft(A2) = (Q1,Σ, E1, s1, f1);
3. G = Prod(A1,A2); {cï |Q|2 tr¤ng th¡i v  |E|2 cung}
4. G′ = XCopy(G); {cï 2|Q|2 ¿nh v  3|E|2 cung}
5. if ContainsCycle(G′, ((s1, s2), 1)) then Return ("ffië tr¹ gi£i m¢ væ h¤n")
6. T¼m trång sè d i nh§t d cõa ÷íng i tø ¿nh (s1, s2) ¸n ¿nh (f1, f2) tr¶n G
7. Return d.
ffi¡nh gi¡ ë phùc t¤p thíi gian cõa gi£i thuªt: ffië phùc t¤p thíi gian cõa b÷îc 1 l 
O((|Q| + |E|)2), b÷îc 2 èi vîi h m D(A) l  O(|Q| + |E|), h m Trim l  O(|Q| + |E|), c¡c
h m Ex v  Graft l  O(1), b÷îc 3 l  O((|Q|+ |E|)2), b÷îc 4 v  b÷îc 5 l  O(|Q|2 + |E|2).
Ð b÷îc 6, G x¡c ành mët ç thà câ chu tr¼nh, c¡c cung i ¸n ¿nh khâa câ trång sè l 
1, c¡c cung cán l¤i câ trång sè l  0, do ç thà x¡c ành bði G khæng câ chu tr¼nh hñp l», cho
n¶n mët chu tr¼nh b§t ký l  khæng câ ¿nh khâa, vªy c¡c cung tham gia v o chu tr¼nh ·u câ
152 ffiNG QUY˜T THNG, NGUY™N ffiœNH H…N, PHAN TRUNG HUY
trång sè 0. ffiº thüc hi»n t¼m trång sè d i nh§t cõa ÷íng i tø ¿nh khði ¦u ¸n ¿nh k¸t
thóc ta g¡n c¡c cung câ trång sè l  1 th nh -1, rçi ¡p döng gi£i thuªt Bellman Ford (xem
[15]) t¼m ÷íng i ng­n nh§t tr¶n ç thà trång sè câ thº ¥m v  câ chu tr¼nh khæng ¥m, khi â
d l  gi¡ trà nhä nh§t t¼m ÷ñc th¼ d l  trång sè d i nh§t cõa ÷íng i tø ¿nh (s1, s2) ¸n
¿nh (f1, f2) tr¶n G. Thüc hi»n to n bë b÷îc 6 câ ë phùc t¤p thíi gian l  O(|Q|2|E|2).
Têng hñp l¤i gi£i thuªt câ ë phùc t¤p thíi gian O(|Q|2|E|2) = O(|E|3) = O((|E| +
|Q|)3) = O(n3), vîi n = |Q| + |E|, ð ¥y ta xem O(|E|) = O(|Q|2) (khi ætæmat d y cung
nh§t).
5. K˜T LUŁN
Nghi¶n cùu c¡c mæ h¼nh ætæmat n¥ng cao v  ùng döng cõa nâ l  mët trong c¡c xu h÷îng
nghi¶n cùu hi»n ¤i ÷ñc nhi·u nh  khoa håc - cæng ngh» quan t¥m. B i b¡o · xu§t gi£i
thuªt mîi x¡c ành ë tr¹ gi£i m¢ cõa ngæn ngú ch½nh quy, ÷ñc o¡n nhªn bði ætæmat húu
h¤n. ffi¥y l  b i to¡n câ þ ngh¾a v· lþ thuy¸t công nh÷ ùng döng thüc ti¹n.
T€I LI›U THAM KHƒO
[1] R. McCloskey, An O(n2) Time algorithm for deciding whether a regular language is a code,
Journal of Computing and Information 2 (1) (1996) 7989.
[2] J. Berstel, D. Perrin, Theory of Codes, Academic Press Inc., NewYork, 1985.
[3] J. Devolder, M. Latteux, I. Litovsky, L. Staiger, Codes and infinite words, Acta Cybernetica
11 (4) (1994) 241-256.
[4] G. Lallement, Semigroups and Combinational Applications, John Wiley & Sons, Inc, 1979.
[5] L. Staiger, On infinitary finite length codes, Informatique Theorique et Applications 20 (4)
(1986) 483494.
[6] M. Mohri, Edit-Distance of Weighted Automata: General Definitions and Algorithms, Interna-
tional Journal of Foundations of Computer Science 14 (6) (2003) 957982.
[7] M. Mohri, F. Pereira, M. Riley, Speech recognition with weighted finite-state transducers,
Springer Handbook of Speech Processing, Springer, 2007.
[8] K. Stavros, Transducers and the properties of errordetection, error-correction, and finite-delay
decodability. Journal of Universal Computer Science 8 (2) (2002) 278291.
[9] E. N. Gilbert, E. F. Moore, Variable length binary encodings, Bell System Technical Journal
38 (1959) 933967.
[10] V. I. Levenshtein, Some properties of coding and self-adjusting automata for decoding messages,
Problemy Kirbernet 11 (1964) 63121.
[11] M.-P. Schutzenberger, On a question concerning certain free submonoids, J. Combin. Theory
1 (1966) 437422.
THUŁT TON MÎI XC ffiÀNH ffiË TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY 153
[12] A. A. Markov, On alphabet coding Soviet. Phys. Dokl. 6 (1962) 553-554.
[13] C. Choffrut. Une caract²risation des codes   d²lai born² par leur fonction de d²codage. LITP,
1979 (4756).
[14] Phan Trung Huy, Vô Th nh Nam, Mët sè ë o nhªp nh¬ng cõa m¢, T¤p ch½ Tin håc v  ffii·u
khiºn håc 18 (3) (2002) 253261.
[15] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, (3rd ed.),
MIT Press and McGraw-Hill, 2009.
[16] Nguy¹n ffi¼nh H¥n, ffi°ng Quy¸t Th­ng, Hç Ngåc Vinh, T½nh to¡n ë tr¹ gi£i m¢ cõa ngæn ngú
b¬ng otomat, Kff y¸u Hëi th£o Quèc gia: Mët sè v§n · chån låc cõa cæng ngh» thæng tin
v  truy·n thæng, 8/2010 (321332).
[17] D.L. Van and I. Litovsky, On a family of code with bounded deciphering delay, Lecture Notes
of Computer Science 2450 (2003) 369380.
Ng y nhªn b i 28 - 3 - 2012
Nhªn l¤i sau sûa 20 - 8 - 2012