Đơn định và tối tiểu hoá otomat khoảng

a, d
s
a, d unionsq d′
s′
a) b)
a, d′
Hình 5. Ghép cung
δ̂(s, wa) = δ(δ̂(s, w), a) với δ(s, ε∞) = s. Khi cho trước otomat khoảng, một trong hai dạng
này sẽ đều được sử dụng và xem là tương đương nhau. Giống như otomat truyền thống, δ̂(q, w)
sẽ bao gồm tất cả các trạng thái p sao cho có thể đi đến được theo từ w, bao gồm cả việc đi
qua các cung ε∞.
Như vậy, với otomat đơn định, hàm chuyển xác định không quá một giá trị trạng thái,
tức là δ : S × (A,D) → S, trong khi với otomat đa định, hàm chuyển tương ứng này sẽ là
δN : S × (A,D)→ 2S . Hàm chuyển mở rộng cho otomat đa định cũng được định nghĩa tương
tự: δ̂N (s, wa) = δ̂N (δ̂N (s, w), a).
Hệ quả 2.1. Cho otomatM với hàm chuyển trạng thái δ. Nếu δ(s, (a, d′)) = s′ và δ(s, (a, d′′)) =
s′ mà d′ ⊆ d′′ thì việc loại bỏ quan hệ chuyển δ(s, (a, d′)) = s′ không thay đổi ngôn ngữ được
M đoán nhận.
Chứng minh. Do do mọi t-từ thoả d-từ chứa (a, d′) đều đã được chứa trong d-từ chứa (a, d′′)
nên việc loại bỏ không làm mất những t-từ được đoán nhận. Ngược lại, việc loại bỏ cung
không làm tăng các từ được đoán nhận. Vậy ngôn ngữ được M đoán nhận là không đổi. 
Hệ quả 2.2. Cho otomat M với hàm chuyển trạng thái δ. Nếu thay cặp quan hệ chuyển
δN (s, (a, d)) = s
′ và δN (s, (a, d′)) = s′, với d ∩ d′ 6= ∅ bằng quan hệ δN (s, (a, d unionsq d′)) = s′ thì
ngôn ngữ do otomat đoán nhận không thay đổi.
Chứng minh. Giả sử d = [l, u], d′ = [l′, u′]. Nếu khoảng thời gian ở cung hợp được tách
ra làm 3 khoảng nhỏ: d1 = d\d′ tức là khoảng gồm các giá trị thuộc d nhưng không thuộc d′,
d2 = d ∩ d′ là khoảng gồm các giá trị thuộc cả d và d′, và d3 = d′\d là khoảng gồm các giá
trị thuộc d′ nhưng không thuộc d. Như vậy, mỗi khi đi từ s đến s′ thì giá trị t của t-từ tương
ứng sẽ rơi vào một trong 3 khoảng vừa chia. Vậy việc hợp cung chỉ thu gọn số lượng cung của
otomat mà không làm thay đổi ngôn ngữ do otomat đoán nhận. 
ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG 155
s
s′
s′′
(a, d ′
)
(a
, d
)
d
d′
d\d′ d′\d
d ∩ d′
s
s′
s′′
(a, d ′\d)
(a,
d\d
′ )
(a,
d ∩ d
′ )
(a, d ∩ d ′)
Hình 6. Tách khoảng
Hệ quả 2.3. Cho otomat M với hàm chuyển trạng thái δ. Nếu thay mọi cặp quan hệ
δN (s, (a, d)) = s
′ và δN (s, (a, d′)) = s′′ với d ∩ d′ 6= ∅ và s′ 6= s′′ bằng các quan hệ:
e′1 : δN (s, (a, d\d′)) = s′, e′2 : δN (s, a, d ∩ d′) = s′,
e′3 : δN (s, (a, [d ∩ d′)) = s′′, e′4 : δN (s, (a, d′\d)) = s′′
thì otomat thu được đoán nhận cùng ngôn ngữ với otomat ban đầu.
Chứng minh. Các khoảng giao/chứa nhau được tách thành 3 khoảng rời rạc. Việc tách này
tạo ra các khoảng nhỏ hơn và mỗi t-từ thoả quan hệ chuyển trước khi tách có giá trị nhãn t
tương ứng chỉ thỏa một trong ba khoảng trong các quan hệ chuyển thay thế. Đồng thời, hợp
các giá trị t thỏa 3 khoảng mới tạo ra chính là d unionsq d′. Do đó, việc thay thế cung cũng không
làm thay đổi ngôn ngữ được đoán nhận.
Trong các quan hệ được thay vào ứng với các cặp quan hệ đa định, các quan hệ e′2, e′3
chính là các quan hệ làm cho otomat đa định: cùng hành động a, trùng nhãn thời gian và đi
đến hai trạng thái khác nhau. Tại mọi trạng thái, nếu δN (s, a, d) = s
′ và δN (s, a′, d′) = s′ thì
(a, d) 6= (a′, d′) và nếu δN (s, a, d) = s′ và δN (s, a, d) = s′′ thì s′ 6= s′′. 
2.3. Bài toán đơn định hoá otomat
Bài toán: Cho trước một otomat khoảng M . Đơn định hóa otomat đó.
So sánh với bài toán đơn định của otomat truyền thống, sau khi đã rời rạc hoá các khoảng
và tách, gộp cung, ta có thể coi nhãn (bộ hai thành phần) trong otomat khoảng như một nhãn
mới thì có thể sử dụng phương pháp như với otomat truyền thống để đơn định hoá. Trong
hình 6, hai cung (s, a, d∩ d′, s′) và (s, a, d∩ d′, s′′) chính là hai cung làm cho otomat đa định.
Thuật toán đơn định hoá otomat khoảng.
Input: Otomat khoảng không đơn định MN = 〈SN ,Σ,∇,4, qN , δN , FN 〉.
Output: Otomat khoảng đơn định MD = 〈SD,Σ,∇,4, Q0, δD, FD〉 đoán nhận cùng ngôn
ngữ với otomat M .
1. Kiểm tra nếu MN đơn định, thuật toán dừng.
2. Loại bỏ các quan hệ chuyển chứa nhau: Giả sử δN (s, a, d
′) = s′, δN (s, a, d′′) = s′ mà
d′ ⊆ d′′ thì loại bỏ quan hệ chuyển δN (s, a, d′) = s′ (Bổ đề 2.1).
3. Ghép các quan hệ chồng lặp: Với mọi cặp quan hệ chuyển δN (s, a, d) = s
′ và δN (s, a, d′) =
s′, nếu d ∩ d′ 6= ∅ thì thay hai quan hệ trên bằng quan hệ δN (s, a, d unionsq d′) = s′ (Bổ đề
2.2).
156 BÙI VŨ ANH
4. Tách các khoảng: Với mọi cặp quan hệ δN (s, a, d
′) = s′ và δN (s, a, d′′) = s′′ mà d′∩d′′ 6= ∅
và s′ 6= s′′ thì thay hai quan hệ này bằng các quan hệ như trong Bổ đề 2.3. Quá trình
tách này dừng khi không còn quan hệ cần tách.
5. Đơn định hoá:
(a) Gọi D là tập tất cả các d−nhãn của otomat MN sau khi tách và gộp các khoảng.
(b) Q0 = {qN} là trạng thái khởi đầu của MD. Xây dựng hàm T : 2SN × D → 2SN
như sau:
i. ∀s ∈ SN , ∀a ∈ D: T ({s}, a) = {s′ ∈ SN | s′ = δN (s, a)}.
ii. ∀B ⊆ SN , ∀a ∈ D: T (B, a) =
⋃
s∈B
T ({s}, a).
(c) Xây dựng các quan hệ chuyển: Đối với mỗi tập B ⊆ SN và với mọi d−nhãn a ∈ D,
nếu Q = T (B, a) 6= ∅ thì δD(B, a) = Q và đưa B,Q vào tập trạng thái SD (khởi
tạo rỗng).
(d) Trạng thái kết: FD = {Q ∈ SD | Q ∩ FN 6= ∅}.
Chứng minh. Để chứng minh tính đúng đắn của thuật toán, tức là L(MD) = L(MN ), ta
sẽ chứng minh δ˜D(Q0, w) = δ˜N (qN , w) với w là một d−từ. Hàm δD trả lại một tập các trạng
thái trong SN . Ta sẽ chứng minh quy nạp theo độ dài của w.
- Với độ dài |w| = 0, theo định nghĩa hàm chuyển mở rộng, ta có δ̂(qN , w) = qN . Mặt khác,
δ̂D(Q0, w) = δ̂D({qN}, w) = δ̂N (qN , w) = qN . Vậy khẳng định đúng.
- Giả sử khẳng định đúng với d−từ w có độ dài n, xét d−từ wa, với a là d−nhãn. Giả sử
δ̂N (qN , w) = {p1, . . . , pk}. Theo giả thiết quy nạp, δ̂D({qN}, w) = δ̂N (qN , w) = {p1, . . . , pk}.
Lại có, δ̂N (qN , wa) = δN (δ̂N (qN , w), a) =
⋃
i=1..k
δN (pi, a).
Mặt khác, δ̂D(Q0, wa) = δD(δ̂D({qN}, w), a) = δD({p1, . . . , pk}, a) =
⋃
i=1..k
δN (pi, a) (theo
cách xây dựng hàm T của thuật toán). Vậy δ̂D(Q0, wa) = δ̂N (pN , wa) và khẳng định đúng với
từ có độ dài n+ 1. Cả MN và MD chấp nhận d−từ w nếu tương ứng δ̂D(Q0, w) và δ̂N (pN , w)
chứa ít nhất một trạng thái kết thuộc FN . Theo quy nạp, thuật toán được chứng minh. 
Vậy ta có định lý.
Định lý 2.1. Lớp ngôn ngữ đoán nhận bởi otomat khoảng đơn định và otomat khoảng đa
định là trùng nhau.
Thuật toán tìm các trạng thái của otomat mới thông qua việc duyệt các tập con của không
gian các tập con của tập trạng thái của otomat ban đầu. Với mỗi tập con này, thuật toán xây
dựng các quan hệ chuyển dựa trên việc duyệt lần lượt các nhãn trên các cung. Trường hợp
xấu nhất phải vét tất cả các tập con của tập trạng thái SN và tất cả các nhãn (mỗi cung một
nhãn), nên độ phức tạp của thuật toán sẽ là O(2n ×m× |D|) với n là số trạng thái và m là
số nhãn của otomat ban đầu. Để tránh phải thực hiện tách cung nhiều lần, ta có thể chia các
khoảng ra thành các khoảng đơn vị trong quá trình tách, nghĩa là không có khoảng nào giao
với nhau khác rỗng. Tuy nhiên, thao tác tiền xử lý này không làm giảm bậc của độ phức tạp
thuật toán mà chỉ thay đổi thời gian chạy của thuật toán khi cài đặt, không phải tách lại trên
các khoảng đã tách.
Định nghĩa 2.5. (Thành phần không thời gian của DA) Cho otomatM = 〈Q,Σ,∇,4, q0, R, F 〉.
- Otomat không thời gian tương ứng với M là untime(M) = 〈Q,Σ,∇,4, q0, R′, F 〉 trong đó
ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG 157
R′ = {(s, a, s′) | ∃d ∈ D : (s, a, d, s′) ∈ R}.
- Từ không gắn thời gian của từ w˜ = (a1, d1)(a2, d2)(a3, d3) . . . (sn, dn) là a1a2a3 . . . an.
Như vậy, trong trường hợp xét thành phần không thời gian của DA thì các khái niệm d−từ
và t-từ trùng nhau và trở về khái niệm từ được định nghĩa cho otomat truyền thống.
2.4. Otomat khoảng tối tiểu
Định nghĩa 2.6. Hai trạng thái s và s′ của otomat M = 〈Q,Σ,∇,4, q0, δ, F 〉, được gọi là
tương đương, ký hiệu s ≈ s′ nếu với mọi d−từ w, δ(s, w) ∈ F ⇔ δ(s′, w) ∈ F . Hai trạng thái
không tương đương gọi là hai trạng thái phân biệt.
Như vậy, với hai trạng thái bất kỳ, nếu s ∈ F và s′ 6∈ F hoặc nếu ∃ d−nhãn a mà
δ(s, a) = p, δ(s′, a) = ∅ thì s và s′ đều là không tương đương. Khái niệm trạng thái tương
đương ở đây tương tự khái niệm trạng thái tương đương của otomat truyền thống.
Hệ quả 2.4. Quan hệ giữa các trạng thái trong Định nghĩa 2.6 là một quan hệ tương đương.
Chứng minh. Chứng minh suy ra từ Định nghĩa 2.6 về trạng thái không phân biệt.
- Phản xạ: q ≈ q.
- Đối xứng: q ≈ p ⇔ ∀w ∈ (A,D)∗, δ̂(q, w) ∈ F ⇔ δ̂(p, w) ∈ F ⇔ ∀w ∈ (A,D)∗, δ̂(p, w) ∈
F ⇔ δ̂(q, w) ∈ F ⇒ p ≈ q.
- Bắc cầu:
+ q ≈ p ⇔ ∀w ∈ (A,D)∗, δ̂(q, w) ∈ F ⇔ δ̂(p, w) ∈ F .
+ p ≈ r ∀w′ ∈ (A,D)∗, δ̂(p, w′) ∈ F ⇔ δ̂(r, w′) ∈ F
⇒ ∀w, w′ ∈ (A,D)∗, δ̂(q, ww′) ∈ F ⇔ δ̂(r, ww′) ∈ F . 
Hệ quả 2.5. Cho δ(p, a) = p′, δ(q, a) = q′ với a là một d−nhãn. Khi đó nếu p′ và q′ là phân
biệt thì p và q cũng phân biệt.
Chứng minh. Do p′, q′ phân biệt nên tồn tại d−từ w: δ̂(q′, w) ∈ F và δ̂(p′, w) 6∈ F (hoặc
ngược lại). Khi đó δ̂(q, aw) ∈ F và δ̂(p, aw) 6∈ F (hoặc ngược lại) nên q và p phân biệt. 
Định nghĩa 2.7. Cho d−ngôn ngữ L 6= ∅. Otomat khoảng có số trạng thái ít nhất đoán
nhận L được gọi là otomat khoảng tối tiểu đoán nhận L.
Định nghĩa 2.8.
- Một trạng thái s của otomat khoảng M = 〈Q,Σ,∇,4, q0, δ, F 〉 được gọi là đến được nếu
tồn tại một d−từ thoả được x˜, sao cho δ̂(q0, x˜) = s trong đó δ̂ là hàm mở rộng của hàm
chuyển trạng thái. Ngược lại, trạng thái gọi là không đến được.
- Trạng thái s được gọi là trạng thái treo nếu nó không phải là trạng thái kết và dãy các phép
chuyển theo mọi d−từ vào thoả được sẽ dừng ở đó, tức là s 6∈ F và ∀x˜ ∈ (A×D)∗, δ(s, x˜) = ∅
hoặc δ(s, x˜) = s.
Dễ thấy các trạng thái không đến được (có thể là trạng thái kết) và những trạng thái treo
không là trạng thái kết chỉ làm gia tăng số trạng thái của otomat nhưng không làm thay đổi
ngôn ngữ do otomat đoán nhận. Do đó, ta có thể loại bỏ các trạng thái này mà không ảnh
hưởng đến ngôn ngữ do otomat đoán nhận. Ta có bổ đề sau.
158 BÙI VŨ ANH
si sj
w
Trạng thái đến được
sj
Trạng thái treo kết
sj
Trạng thái không đến được và trạng thái treo
sj
d d′
d ∩ d′ = ∅
Hình 7. Trạng thái đến được và trạng thái treo
s0
δ(., (a, d)Rp Rc T
s s
′
R
δ(., (a′, d′)
Hình 8. Loại trạng thái không đạt được
Hệ quả 2.6. Otomat khoảng tối tiểu không chứa các trạng thái không đến được và trạng
thái treo không kết.
Bổ đề 2.6 cho ta điều kiện để thực hiện bước tiền xử lý trước khi tìm một otomat tối
tiểu. Do đó, ta có thể giả thiết tất cả các trạng thái của otomat đều là đến được và không
là trạng thái treo không là trạng thái kết khi tiến hành tối tiểu hóa otomat. Lưu ý là trạng
thái kết cũng có thể là trạng thái không đến được. Trạng thái đến được và trạng thái treo
được minh hoạ ở Hình 7. Đồng thời, otomat untime(M) có các trạng thái không đến được
và trạng thái treo không kết thì những trạng thái tương ứng này trong otomat khoảng cũng
là các trạng thái không đến được và trạng thái treo không kết. Những trạng thái này cũng sẽ
không tham gia trong việc xác định ngôn ngữ mà otomat khoảng đoán nhận. Do đó, trong
quá trình tìm otomat tối tiểu, ta có thể sử dụng thuật toán tựa thuật toán Hopcroft [9] trên
otomat untime(M) xác định các trạng thái thuộc cùng lớp tương đương của otomat không
thời gian.
Ý tưởng loại bỏ các trạng thái không đạt được minh hoạ trong Hình 8. Khởi đầu, q0 là
trạng thái đến được thuộc Rp và tập Rc các trạng thái đến được (có cung trực tiếp) từ q0.
Đây là các trạng thái đến được (R). Với mỗi trạng thái trong Rp có cung đến Rc và có thể đi
tiếp được đến một trạng thái s′ (không nằm trong tập đã đến được) thì trạng thái mới này
là đến được, ta bổ sung vào R và được đưa vào phần gia tăng ở mỗi bước lặp T (xoá rỗng T
sau mỗi lần thử trạng thái thuộc Rp). Sau đó ta đổi vai trò của Rc thành Rp và T thành Rc.
Khi ở một bước lặp, phần gia tăng T là rỗng tức là không thể bổ sung thêm các trạng thái
đến được, thuật toán dừng. Quá trình này dừng do tập trạng thái của otomat là hữu hạn và
quá trình thực hiện không bị lặp lại trên các trạng thái đã được xét là đến được. Ta chỉ giữ
lại các trạng thái có trong R cùng các cung nối các trạng thái trong R.
Thuật toán loại các trạng thái không đạt được.
ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG 159
Input: Otomat khoảng đơn định M = 〈S,Σ,∇,4, q0, δ, F 〉.
Output: Otomat khoảng chứa các trạng thái đạt được.
1. D = {(a, d) : ∃s, s′ ∈ S, δ(s, a, d) = s′};
2. Rp = {q0};
3. Rc = ∅; for (a, d) ∈ D Rc = Rc ∪ {δ(q0, (a, d))};
4. Rc = Rc\Rp;
5. R = Rp ∪Rc;
6. done=1;
7. while (done)
8. { done=0;
9. for s ∈ Rp
10. { T = ∅;
11. for (a, d) ∈ D
12. if δ(s, (a, d)) 6= ∅
13. { for (a′, d′) ∈ D
14. if δ(δ(s, (a, d)), (a′, d′)) 6= ∅
15. { s′ = δ(δ(s, (a, d)), (a′, d′))
16. if (s′ 6∈ S −R) && (d ∩ d′ 6= ∅)
17. { R = R ∪ {s′};
18. T = T ∪ {s′};
19. done=1; }
20. }
21. }
22. }
23. Rp = Rc;
24. Rc = T ;
25. }
Độ phức tạp của thuật toán: O(|D|2×|S|) với D là tập các nhãn có trên các cung của otomat.
Tiếp theo, ta sẽ loại các trạng thái treo. Trong Hình 9, từ các trạng thái không bị treo
(xuất phát từ tập trạng thái kết F ) dò ngược trở lại tìm các trạng thái có cung đi đến các
trạng thái này và đưa chúng vào tập trạng thái không treo (và là phần gia tăng New). Quá
trình dò như vậy đến khi tìm được hết các trạng thái mà từ đó tồn tại một dãy các cung dẫn
đến được trạng thái kết. Các trạng thái không được đưa vào NotDied sẽ là các trạng thái
treo và sẽ loại các trạng thái này cùng các cung đến đó. Thuật toán dừng khi phần bổ sung
thêm New ở một bước là rỗng. Quá trình này dừng do không lặp lại các trạng thái đã bổ
sung (duyệt theo cung) và tập trạng thái là hữu hạn.
Thuật toán loại bỏ các trạng thái treo.
Input: Otomat khoảng đơn định M = 〈S,Σ,∇,4, q0, δ, F 〉 có các trạng thái đều đạt được.
Output: Otomat khoảng không chứa các trạng thái treo không kết M ′.
1. NotDied = F ;
2. New = F ;
3. done = 1;
4. while (done)
160 BÙI VŨ ANH
New
NotDied
(a, d)
δ−1(s, (a, d)
s
FT
Hình 9. Loại trạng thái treo không kết
5. { done = 0;
6. T = ∅;
7. for (s ∈ New)
8. { for ((a, d) ∈ D)
9. if(δ−1(s, (a, d))! = ∅) && δ−1(s, (a, d)) 6∈ NotDied
10. { T = T ∪ δ−1(s, (a, d));
11. done = 1; }
12. }
13. New = T\NotDied;
14. NotDied = NotDied ∪New;
15. }
Độ phức tạp của thuật toán: O(|S|2|D|).
Hệ quả 2.7. Otomat khoảng đơn định có các trạng thái đến được là tối tiểu khi và chỉ khi
tất cả các cặp trạng thái của nó là phân biệt.
Chứng minh. Do otomat là đơn định nên không tồn tại d ⊆ d′,∀s, s′ ∈ S mà (s, a, d, s′) và
(s, a, d′, s′) đều thuộc quan hệ chuyển δ. Nếu ta đặt lại các nhãn trên các cung trong otomat
khoảng đơn định bởi các nhãn mới thì otomat mới thu được chính là otomat truyền thống.
Do đó việc chứng minh định lý này có thể dùng lại chứng minh của Hopcroft. 
Bài toán: Cho d−ngôn ngữ được biểu diễn bởi DA đơn định M = 〈Q,Σ,∇,4, q0, δ, F 〉. Tối
tiểu hóa M .
Nhận xét: Ta có thể sử dụng cải biên của thuật toán Hopcroft [8] để áp dụng cho otomat
khoảng. Thuật toán này sẽ phân lớp các trạng thái tương đương vào cùng một lớp tương đương
và xây dựng otomat tối tiểu dựa vào các lớp tương đương này. Với otomat khoảng, nhãn dùng
để phân lớp tương đương tương tự như với thuật toán Hopcroft, nhưng gồm hai thành phần
là nhãn và khoảng thay vì chỉ là một nhãn đơn.
Thuật toán tối tiểu hoá otomat khoảng.
Input: Otomat khoảng đơn định M = 〈S,Σ,∇,4, q0, δ, F 〉.
Output: Otomat khoảng tối tiểu Mt = 〈St,Σ,∇,4, s0, δt, Ft〉 mà L(Mt) = L(M).
1. Loại bỏ trạng thái không đến được (sử dụng một thuật toán duyệt các trạng thái).
2. Loại bỏ các trạng thái treo không là trạng thái kết.
3. Gọi D là danh sách tất cả các d−nhãn có trên các cung còn lại của otomat (sau bước
1, 2).
ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG 161
4. P = {F,Q\F}
5. W := {F}
6. while (W 6= ∅) do
7. { get(A,W ) /* lấy tập A ra khỏi W * /
8. for (a, d) ∈ D do
9. { X = {q : δ(q, (a, d)) ∈ A}
10. for {Y ∈ P : X ∩ Y 6= ∅, Y 6⊆ X} do
11. { thay thế Y trong P bởi X ∩ Y và Y \X
12. if Y ∈W
13. thay Y trong W bởi X ∩ Y và Y \X
14. else
15. if |X ∩ Y | ≤ |Y \X| thêm X ∩ Y vào W else thêm Y \X vào W
16. }
17. }
18. }
Phần tối tiểu otomat có độ phức tạp tương ứng là O(|S| × log|S|), tương tự như [8, 9], tuy
nhiên do cần loại trạng thái treo và trạng thái không đến được nên độ phức tạp của thuật
toán tối tiểu hoá là max{O(|S| ×D), O(|D| × S2), O(|S| × log|S|)}. Khi số lượng nhãn (hai
thành phần) là hằng số, có thể coi độ phức tạp cỡ O(|S| × log|S|). Khi lập trình, có thể sử
dụng kỹ thuật trong [2] để tránh trường hợp xấu nhất khi tìm otomat tối tiểu.
Định lý 2.2. Thuật toán tìm otomat khoảng tối tiểu là đúng đắn.
Chứng minh. Ngôn ngữ được đoán nhận không thay đổi khi loại bỏ trạng thái không đến
được và trạng thái treo không kết vì các d−từ dẫn đến các trạng thái này không thể dẫn tiếp
đến các trạng thái được đoán nhận. Nếu coi các nhãn kép của otomat khoảng thu được sau
khi loại các trạng thái không đến được và trạng thái treo không kết là một nhãn đơn (thông
qua phép đặt lại tên chẳng hạn) thì otomat khoảng trở thành otomat truyền thống và việc
chứng minh otomat này là otomat tối tiểu sẽ tương tự như chứng minh cho otomat truyền
thống. 
3. KẾT LUẬN
Bài báo trình bày bài toán đơn định và tối tiểu trên otomat khoảng. Đây là hai bài toán
kinh điển và được đặt lại cho mô hình otomat khoảng, đồng thời đưa ra thuật toán để có thể
giải hai bài toán trên. Tương tự như [12], bài toán tìm siêu tối tiểu (hyper-minimizing) cho
otomat khoảng, phương pháp làm giảm độ phức tạp của thuật toán đơn định và tối tiểu... là
vấn đề thú vị có thể tiếp tục nghiên cứu. Ngoài ra, liệu ta có thể song song hoá thuật toán
đơn định (có độ phức tạp cao) như trong [6], hay sử dụng các kỹ thuật đặc biệt trong lập
trình [6] để có thể tối ưu về mặt thời gian thực hiện thuật toán.
TÀI LIỆU THAM KHẢO
[1] Rajeev. Alur and David L. Dill, A theory of timed automata, Proceedings of 17th International
Colloquium on Automata, Languages, and Programming, and Proceedings of the REX
162 BÙI VŨ ANH
workshop “Realtime: theory in practice” , 1991; Theoretical Computer Science 126 (1994),
183–235.
[2] Andrei Păun, Mihaela Păun, Alfonso Rodríguez-Patón, Hopcroft’s Minimization Technique:
Queues or Stacks?, CIAA 2008, LNCS 5148, Springer-Verlag Berlin Heidelberg, 2008, 78–91.
[3] Bui Vu Anh, Nondeterministic duration automata in modeling priority network, Proceedings
of National Conference on Discovering Knowledge from Data, Vietnam, August 5-6, 2009,
210156B00, 315–325.
[4] Bui Vu Anh, Duration automaton in scheduling programs for a cluster computer system, Journal
of Computer Science and Cybernetics 27(3) (2011), 218–228.
[5] Bui Vu Anh, Phan Trung Huy, Ứng dụng một tích khoảng mới trong bảo mật, Journal of
Computer Science and Cybernetics 29(2) (2013), 149–158.
[6] Ambuj Tewari, Utkarsh Srivastava, and P. Gupta,A Parallel DFA Minimization Algorithm,
LNCS 2552, Springer-Verlag Berlin Heidelberg, 2002, 34–40.
[7] Deepak D’Souza, P.S. Thiagarajan, “Distributed Interval Automata: a subclass of Time Au-
tomata”, Internal Report, Theoretical Computer Science TCS-98-3 (1998).
[8] J.E. Hopcroft, An n log n algorithm for minimizing states in a finite automaton, Theory of
Machines and Computations 35 (1971), 189–196 (Academic Press).
[9] J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computa-
tion, Addison Wesley, 1979.
[10] Dang Van Hung, Bui Vu Anh, Model checking component based systems with black-box testing,
Proceeding of 11th IEEE International Conference on Embedded and Real-Time Com-
puting Systems and Applications (RTCSA’05), United Nation University, Macao (ISBNĨSSN:
1533-2306, 0-7695-2346-3), 2005, 76–79.
[11] Nancy Lynch and Mark Tuttle, An Introduction to Input/Output automata, CWI-Quarterly
2(3) (1989), 219–246.
[12] Markus Holzer, Andreas Maletti, An n log n algorithm for hyper-minimizing a (minimized)
deterministic automaton, Theoretical Computer Science 411 (2010) 3404–3413,
Ngày nhận bài 17 - 12 - 2013
Nhận lại sau sửa ngày 01 - 04 - 2014